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.
Para ambas implementaciones se utiliza la clase NodoABB definida en el Ejemplo NodoABB, por lo que será la primera clase que se describirá.
La clase NodoABB 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:
La clase NodoABB 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 NodoABB. |
Observe además que cada objeto instanciado tendrá dos referencias a objetos como él, las cuales representarán referencias hacia el subárbol izquierdo (nodoIzquierdo) y hacia el subárbol derecho (nodoDerecho).
Los detalles restantes deberían resultarle 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 el Ejemplo NodoABB en su totalidad antes de continuar.
Los detalles restantes deberían resultarle 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 el Ejemplo NodoABB 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 ABBr muestra la definición de la clase ABBr, la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la entrada ABB (representación y diseño).
El estudio y la comprensión de la implementación de los métodos de recorrido para un árbol binario de búsqueda (líneas 34-68), se dejan como ejercicio para el lector.
El método inserta (líneas 13-18), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo insertaR (línea 17).
El Ejemplo ABBr muestra la definición de la clase ABBr, la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la entrada ABB (representación y diseño).
El estudio y la comprensión de la implementación de los métodos de recorrido para un árbol binario de búsqueda (líneas 34-68), se dejan como ejercicio para el lector.
El método inserta (líneas 13-18), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo insertaR (línea 17).
Por su parte, la idea del método insertaR (líneas 21-32) 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 22), debe ser insertado en el subárbol izquierdo.
- Si el subárbol izquierdo está vacío o disponible (línea 23), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 24). Si no está vacío (línea 25), se recorre el subárbol izquierdo de manera recursiva (línea 26) para encontrar la posición apropiada para elemento dentro del subárbol.
- Si elemento es mayor (línea 27), debe ser insertado en el subárbol derecho.
- Si el subárbol derecho está vacío o disponible (línea 28), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 29). Si no está vacío (línea 30), se recorre el subárbol derecho de manera recursiva (línea 31) para encontrar la posición apropiada para elemento dentro del correspondiente subárbol.
La clase PruebaArbol del Ejemplo PruebaArbol utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico; el cual, además de presentarse en la salida estándar (línea 15), representa el valor a ser insertado dentro del árbol binario de búsqueda (línea 16).
Finalmente, el Ejemplo PruebaArbol realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Es ampliamente recomendable que el lector realice varias ejecuciones de la clase PruebaArbol y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.
Finalmente, el Ejemplo PruebaArbol realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Es ampliamente recomendable que el lector realice varias ejecuciones de la clase PruebaArbol y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.
 |
| Una posible salida de los Ejemplos PruebaArbol y Prueba ABB. |
Una posible salida para el Ejemplo PruebaArbol se muestra en la figura anterior.
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 representado en el diagrama de clase de la entrada ABB (representación y diseño) se presenta 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 34-68), se dejan como ejercicio para el lector.
El método inserta (líneas 13-32), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, se genera una referencia alterna (línea 17) para recorrer el árbol (línea 18).
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 representado en el diagrama de clase de la entrada ABB (representación y diseño) se presenta 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 34-68), se dejan como ejercicio para el lector.
El método inserta (líneas 13-32), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, se genera una referencia alterna (línea 17) para recorrer el árbol (línea 18).
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 19), debe ser insertado en el subárbol izquierdo.
- Si el subárbol izquierdo está vacío o disponible (línea 20), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 21). Si no está vacío (línea 22), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol izquierdo (línea 23) para encontrar la posición apropiada para elemento dentro del árbol.
- Si elemento es mayor (línea 24), debe ser insertado en el subárbol derecho.
- Si el subárbol derecho está vacío o disponible (línea 25), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 26). Si no está vacío (línea 27), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol derecho (línea 28) 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 29 y 30).
La clase de prueba para la clase ABB del Ejemplo ABB se muestra en el Ejemplo PruebaABB.
Al igual que antes, la clase PruebaABB del Ejemplo PruebaABB utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico, el cual además de presentarse en la salida estándar (línea 15), representa el valor que será insertado dentro del árbol binario de búsqueda (línea 16).
Finalmente, el Ejemplo PruebaABB también realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Una vez más, se recomienda ampliamente que el lector realice varias ejecuciones de la clase PruebaABB y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.
Finalmente, el Ejemplo PruebaABB también realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Una vez más, se recomienda ampliamente que el lector realice varias ejecuciones de la clase PruebaABB y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.
