Esta entrada presenta la implementación de un ABB en base a dos enfoques respecto a la inserción de elementos:
- Enfoque recursivo.
- Enfoque iterativo.
Ambas implementaciones se utiliza la clase Nodo_ABB definida en el Ejemplo abb, por lo que será la primera clase que se describirá. Esta clase define un nodo capaz de almacenar objetos
genéricos. Cada nodo definido por la clase tiene la forma de cada uno de
los nodos de la siguiente figura:
 |
| Árbol binario de búsqueda (ABB) conformado por objetos de la clase Nodo_ABB. |
Con base en lo anterior, observe que cada objeto instanciado tendrá dos referencias a
objetos como él, las cuales representarán referencias hacia el subárbol
izquierdo (nodo_izquierdo) y hacia el subárbol derecho (nodo_derecho).
Los detalles restantes deberían resultar familiares al lector, ya que en esencia se refieren a un constructor y a los métodos de tipo set y get para cada uno de los atributos. Asegúrese de comprender los detalles de la clase Nodo_ABB en su totalidad antes de continuar.
Los detalles restantes deberían resultar familiares al lector, ya que en esencia se refieren a un constructor y a los métodos de tipo set y get para cada uno de los atributos. Asegúrese de comprender los detalles de la clase Nodo_ABB en su totalidad antes de continuar.
Enfoque recursivo.
Probablemente el enfoque más común para la implementación de un ABB
debido a la naturaleza inherente a la definición de dicha estructura de
datos, sea el enfoque basado en la recursividad.
El Ejemplo abb muestra la definición de la clase ABB (líneas 18-138), la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la sección ABB (representación y diseño).
El estudio y la comprensión de la implementación de los métodos recursivos de recorrido para un árbol binario de búsqueda (líneas 41-66), se dejan como ejercicio para el lector.
El método inserta_recursivo (líneas 125-130), crea la raíz del árbol (línea 127) si el ABB está vacío (línea 126), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo inserta_recursivo (línea 129).
El Ejemplo abb muestra la definición de la clase ABB (líneas 18-138), la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la sección ABB (representación y diseño).
El estudio y la comprensión de la implementación de los métodos recursivos de recorrido para un árbol binario de búsqueda (líneas 41-66), se dejan como ejercicio para el lector.
El método inserta_recursivo (líneas 125-130), crea la raíz del árbol (línea 127) si el ABB está vacío (línea 126), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo inserta_recursivo (línea 129).
Por su parte, la idea principal del método privado inserta_recursivo (líneas 68-80) es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:
Finalmente, se realizan también los tres recorridos más convencionales definidos para un ABB (líneas 168-179). Es ampliamente recomendable que el lector realice varias ejecuciones del programa y corrobore la salida con inserciones y recorridos realizados en papel y lápiz.
- Si elemento es menor (línea 69), debe ser insertado en el subárbol izquierdo.
- Si el subárbol izquierdo está vacío o disponible (línea 70), se crea un nuevo nodo con elemento como dato y se asigna como subárbol izquierdo (línea 71). Si no está vacío (línea 72), se recorre el subárbol izquierdo de manera recursiva (línea 73) para encontrar la posición apropiada para elemento dentro dicho subárbol.
- Si elemento es mayor (línea 74), debe ser insertado en el subárbol derecho.
- Si el subárbol derecho está vacío o disponible (línea 75), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 76). Si no está vacío (línea 77), se recorre el subárbol derecho de manera recursiva (línea 78) para encontrar la posición apropiada para elemento dentro del correspondiente subárbol.
Finalmente, se realizan también los tres recorridos más convencionales definidos para un ABB (líneas 168-179). Es ampliamente recomendable que el lector realice varias ejecuciones del programa y corrobore la salida con inserciones y recorridos realizados en papel y lápiz.
Enfoque iterativo.
Un enfoque alternativo para la implementación de la operación de
inserción en un árbol binario de búsqueda, es utilizar un ciclo en lugar
de recursividad.
El enfoque propuesto es casi tan compacto como el recursivo pero mucho más eficiente. La implementación sin recursividad del ABB se encuentra también en el Ejemplo abb. Al igual que antes, el estudio y la comprensión de la implementación de los métodos de recorrido (líneas 41-66), se dejan como ejercicio para el lector.
El método inserta (líneas 101-123), crea la raíz del árbol (línea 103) si el ABB está vacío (línea 102), i.e. no existe. En caso contrario (línea 104), se genera una referencia alterna (línea 105) para recorrer el árbol (línea 107).
Al igual que antes, la idea es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:
El enfoque propuesto es casi tan compacto como el recursivo pero mucho más eficiente. La implementación sin recursividad del ABB se encuentra también en el Ejemplo abb. Al igual que antes, el estudio y la comprensión de la implementación de los métodos de recorrido (líneas 41-66), se dejan como ejercicio para el lector.
El método inserta (líneas 101-123), crea la raíz del árbol (línea 103) si el ABB está vacío (línea 102), i.e. no existe. En caso contrario (línea 104), se genera una referencia alterna (línea 105) para recorrer el árbol (línea 107).
Al igual que antes, la idea es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:
- Si elemento es menor (línea 108), debe ser insertado en el subárbol izquierdo.
- Si el subárbol izquierdo está vacío o disponible (línea 109), se crea un nuevo nodo con elemento como dato, se asigna como hijo izquierdo (línea 110) y el método termina. Si no está vacío (línea 112), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol izquierdo (línea 113) para encontrar la posición apropiada para elemento dentro del árbol.
- Si elemento es mayor (línea 114), podría ser insertado en el subárbol derecho.
- Si el subárbol derecho está vacío o disponible (línea 115), se crea un nuevo nodo con elemento como dato, se asigna como hijo derecho (línea 116) y el método termina. Si no está vacío (línea 118), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol derecho (línea 119) para encontrar la posición apropiada para elemento dentro del ABB.
- Finalmente, si el elemento no fue menor ni mayor, entonces por tricotomía de los números no le queda otra más que ser igual, en cuyo caso no hay nada por hacer mas que terminar (líneas 120 y 121).
La función main que pone a prueba para la inserción iterativa
(línea 151) se encuentra en las líneas (143-182). Note que, al igual que antes, se utilizan
números aleatorios dentro de un rango
específico (líneas 146 y 149) mismos que, además de presentarse en la
salida estándar (línea
150), representa el valor a ser insertado dentro del árbol binario de
búsqueda (línea 151).
Finalmente, se realizan también los tres recorridos más
convencionales definidos para un ABB (líneas 155-166). Una vez más, es ampliamente
recomendable que el lector realice varias ejecuciones del programa y
corrobore la salida con inserciones y recorridos realizados en papel y
lápiz. Una posible salida del ejemplo descrito en esta sección se muestra a continuación:
Números a insertar (0-50):
29 42 30 6 9 9 30 42 5 50
******** ABB1 ********
Recorrido en preorden:
29 6 5 9 42 30 50
Recorrido en orden:
5 6 9 29 30 42 50
Recorrido en postorden:
5 9 6 30 50 42 29
******** ABB2 ********
Recorrido en preorden:
29 6 5 9 42 30 50
Recorrido en orden:
5 6 9 29 30 42 50
Recorrido en postorden:
5 9 6 30 50 42 29
29 42 30 6 9 9 30 42 5 50
******** ABB1 ********
Recorrido en preorden:
29 6 5 9 42 30 50
Recorrido en orden:
5 6 9 29 30 42 50
Recorrido en postorden:
5 9 6 30 50 42 29
******** ABB2 ********
Recorrido en preorden:
29 6 5 9 42 30 50
Recorrido en orden:
5 6 9 29 30 42 50
Recorrido en postorden:
5 9 6 30 50 42 29
No hay comentarios.:
Publicar un comentario