Un árbol binario de búsqueda es un tipo de árbol binario en el que se verifica para todo nodo que las claves de su subárbol izquierdo son menores que las de dicho nodo y las claves de su subárbol derecho son mayores. La figura 1.10. muestra un ejemplo.
Figura 1.7. Ejemplo de árbol binario de búsqueda.
La utilización de árboles binarios de búsqueda implica en términos generales las siguientes consideraciones:
3.1. Algoritmos de consulta.
En caso de búsqueda de alguna clave el proceso resulta de mayor eficiencia que en el caso general, dado que el encaminamiento se produce de forma dirigida (por la derecha si arbol.clave < dato y por la izquierda si arbol.clave > dato). La condición de finalización pesimista es alcanzar un extremo del árbol (arbol == null) que en caso de alcanzarse (una sola vez, no varias como podría suceder para árboles binarios genéricos) implicaría que no se ha encontrado la clave buscada y el proceso finalizaría.
La terminación anticipada (no es necesario hacer más llamadas recursivas) se produce cuando se encuentra la clave buscada (arbol.clave == dato). A continuación se muestra como ejemplo el método busqueda que devuelve un puntero al nodo que contiene la clave coincidente con el argumento dato y null en caso de que no exista dicha clave.
En caso de no buscar una clave determinada el recorrido del árbol binario de búsqueda no ofrece ninguna particularidad respecto al árbol binario genérico, pudiendo realizarse dicho recorrido en cualquier modalidad: orden central, preorden o postorden, así como en amplitud.
No obstante, cuando se desea recuperar el conjunto de claves del árbol ordenadas, el recorrido deberá ser en orden central (de izquierda a derecha para secuencia ascendente y de derecha a izquierda para secuencia descendente).
A continuación se muestra como ejemplo el método booleano esBusqueda que devuelve true si el arbol binario, que se pasa como argumento, es de búsqueda y false en caso contrario. Consiste en verificar que la secuencia de claves es ascendente, por lo que habrá que hacer un recorrido en orden central (de izquierda a derecha) y comparar el valor de cada clave con la anterior (ant) que, debidamente inicializada, deberá pasarse como argumento en las sucesivas llamadas recursivas. Es necesario identificar el primer elemento de la lista (no tiene elemento anterior con el que comparar la clave), con una variable auxiliar booleana (primero), inicializada a true desde fuera de el método.
3.2. Algoritmos de modificación.
3.2.1. Inserción.
Se trata de crear un nuevo nodo en la posición que le corresponda según el criterio de árbol binario de búsqueda. A continuación se muestra el algoritmo.
3.2.2. Eliminación.
La eliminación de un nodo en un árbol binario de búsqueda implica una reorganización posterior del mismo con el objeto de que una vez eliminado el nodo el árbol mantenga su naturaleza de búsqueda. Para ello se procede de la manera siguiente:
Figura 1.8. Árbol binario de búsqueda
Primero localizamos el nodo a eliminar. Una vez encontrado, tenemos tres posibles casos:
1. Tenemos que borrar un nodo hoja: procedemos a borrarlo directamente. Por ejemplo, si en el árbol de la figura 1.11, queremos borrar la clave 13, el resultado sería la figura 1.12.
Figura 1.9. Borrado de un nodo hoja en un árbol binario de búsqueda
Hay que borrar un nodo con un único descendiente: ascendemos a su descendiente. Por ejemplo, si en el árbol de la figura 1.12, queremos borrar la clave 17, el resultado sería la figura 1.13.
Figura 1.10. Borrado de un nodo con un solo hijo en un árbol binario de búsqueda
3. El nodo que queremos borrar tiene dos hijos. En este caso, sustituimos la clave a borrar por la clave del mayor de sus descendientes menores (el nodo más a la derecha del subárbol izquierdo), y borramos el nodo que tenía anteriormente dicha clave. Para poder hacer esto:
- Nos situamos en la raíz del subárbol izquierdo de dicho nodo.
- Se desciende por la derecha de dicho subárbol hasta encontrar un nodo (n) sin descendiente derecho.
- Se sustituye la clave a eliminar por la del nodo n.
- Se elimina el nodo
. Por ejemplo, si se desea eliminar la clave 10 del árbol representado en la figura 1.13., sustituiremos dicha clave por la mayor de sus descendientes menores (el 7), y borraremos el nodo con la clave 7 (el nodo que deberemos borrar ahora será en este caso un nodo hoja, aunque también podríamos encontrarnos con un nodo con un solo descendiente). Como resultado, obtendremos el árbol que se muestra en la figura 1.14.
Figura 1.11. Borrado de un nodo con dos hijos en un árbol binario de búsqueda.
A continuación se muestra el código del algoritmo de eliminación.
3.3. Ejemplo.
Dado un árbol binario de búsqueda y una lista enlazada por medio de punteros, implementar un algoritmo en Java que, recibiendo al menos un árbol y una lista ordenada ascendentemente, determine si todos los elementos del árbol están en la lista.
Implementaremos un método booleano con el arbol y la lista como argumentos. Como la lista está ordenada ascendentemente, y el árbol binario es de búsqueda, realizaremos un recorrido del árbol en orden central, parando en el momento en que detectemos algún elemento que existe en el árbol, pero no en la lista.
No hay comentarios:
Publicar un comentario