Operaciones con árboles binarios de búsqueda
Las operaciones con árboles binarios de búsqueda que podemos realizar son: Búsqueda,
inserción y eliminación de un nodo.
Búsqueda de un nodo
Cuando queremos recuperar datos de nuestra estructura de árbol binario de búsqueda,
sacaremos provecho de que estas estructuras están ordenadas. Básicamente, empezaríamos
comprobando el nodo raíz, y si este es el que buscamos, ya hemos acabado. Si no lo es, nos
moveríamos a su hijo izquierdo o al derecho, dependiendo de si el dato que buscamos es
menor o mayor del que contiene el nodo padre. Y así proseguiríamos hasta encontrar el
dato o terminar de recorrer el árbol sin encontrarlo.
Este proceso es recursivo, ya que cuando nos movemos a un nodo hijo, podemos considerar
a este como el nodo raíz de un nuevo árbol. El proceso de búsqueda podría expresarse
como:
Flujo para la búsqueda de un nodo
Que también podríamos representar en seudocódigo de la siguiente manera:
Encontrado (Arbol, buscado){
Si no existe Arbol -> No encontrado
Si existe Arbol {
Si valor Raiz= buscado ->Encontrado
Si valor Raiz <> buscado{
Si valor Raiz >buscado{
árbol = nodo izquierdo
Encontrado(Arbol, buscado)
}
Si valor Raiz < buscado{
árbol = nodo derecho
Encontrado(Arbol, buscado)
}
}
}
}
Analizando como buscamos datos en un árbol binario de búsqueda, podemos imaginar el
tremendo ahorro frente a la búsqueda en una tabla indexada secuencialmente. Si tomamos
el ejemplo del archivo proveedores con 1.000 proveedores, la media de registros que
tendríamos que recorrer en nuestras búsquedas sería de 500, mientras que en el árbol
binario, asumiendo que está equilibrado, como máximo tendremos que recorrer 10, uno por
nivel(0-9).
Inserción de un nodo
Para insertar un nodo en un árbol binario de búsqueda, recorremos este de forma similar a
como lo hacíamos en el proceso de búsqueda, y cuando lleguemos a un “hueco” libre
insertaremos hay nuestro nodo.
El proceso sería el siguiente:
Flujo para la inserción de un nodo
Eliminación de un nodo
Esta es la operación más complicada de las tres que estamos viendo para los árboles
binarios de búsqueda. En primer lugar, para eliminar un nodo, hay que localizarlo en la
estructura del árbol, lo cual ya sabemos hacer, es la primera operación que vimos.
Una vez hemos localizado el nodo, tendremos que actuar de distinta manera para eliminarlo
dependiendo del número de hijos que tenga. Básicamente nos podemos encontrar con tres
situaciones:
• Que el nodo no tenga hijos, es una hoja: Sencillamente eliminamos el nodo y
ponemos a null la referencia que tenía el padre apuntando a dicho nodo.
• Que tenga 1 hijo: Haremos que el nodo padre del nodo a eliminar, apunte al único
hijo que tiene el nodo a eliminar, y luego eliminamos el nodo.
• Que tenga 2 hijos: Este es el caso más complejo. Al eliminar el nodo, ¿Qué nodo de
sus dos subárboles promocionamos al hueco que ha dejado el nodo eliminado? .
Pues bien, tenemos dos opciones:
1. Seleccionar del subárbol izquierdo el nodo que ocupara el sitio del nodo eliminado.
Buscaríamos el nodo de mayor valor de todo el subárbol izquierdo, que debe ser el
que se encuentre más a la derecha.
2. Seleccionar del subárbol derecho el nodo que ocupara el sitio del nodo eliminado.
Buscaríamos el nodo de menor valor de todo el subárbol derecho, que debe ser el
que se encuentre mas a la izquierda
Ejemplo de operaciones con árboles binarios de
búsqueda
En este apartado, vamos a ver ejemplos de las operaciones con árboles binarios. Voy a usar
un árbol binario con números porque entiendo que es más intuitivo, nos resulta más fácil de
ordenar y nos va a resultar más fácil de seguir.
Paso 1: El árbol
Vamos a usar un árbol binario con valores numéricos en los nodos, porque entiendo que es
mucho más visual y se podrá seguir la explicación más fácilmente. Resulta más sencillo
ordenar números que nombres.
Nuestro árbol de partida sería el siguiente:
Árbol binario
Paso 2: Búsqueda de un nodo
Imaginemos que queremos localizar el nodo con valor 24. El camino que recorreríamos es
el que se pinta en rojo:
Búsqueda de un nodo
Empezamos a recorrer el árbol por la raíz, que es con el primer nodo con el que
comparamos. Seguiríamos los siguientes pasos:
• Comparamos el valor buscado (24) con el del nodo raíz (18), como el valor buscado
es mayor, de existir en el árbol, estaría a la derecha.
• Nos movemos al hijo derecho del nodo raíz. Comparamos el valor buscado (24) con
el valor del nodo (25), como el primero es menor, de existir en el árbol, estaría en el
subárbol izquierdo.
• Nos movemos al hijo izquierdo de 25, que es 23.
• Comparamos el valor buscado (24) con el valor del nodo (23). Como el primero es
mayor, de existir, estaría a la derecha.
• Nos movemos al hijo derecho de 23, que es 24. Hemos llegado al nodo buscado.
Paso 3: Búsqueda de un nodo que no existe
Supongamos ahora que buscamos el nodo de valor 27, que podemos comprobar que no
existe en nuestro árbol. Básicamente, el proceso de búsqueda no cambia con respecto al
explicado en el Paso 2, sin embargo, en este caso no vamos a encontrar el nodo, llegaremos
a un hueco donde podría estar el nodo buscado, pero no está.
Búsqueda de nodo que no existe
Empezamos a recorrer el árbol por la raíz, que es con el primer nodo con el que
comparamos. Seguiríamos los siguientes pasos:
• Comparamos el valor buscado (27) con el del nodo raíz (18), como el valor buscado
es mayor, de existir en el árbol, estaría a la derecha.
• Nos movemos al hijo derecho del nodo raíz. Comparamos el valor buscado (27) con
el valor del nodo (25), como el primero es mayor, de existir en el árbol, estaría en el
subárbol derecho.
• Por tanto, nos movemos al hijo derecho del nodo 25 y damos con el nodo 29. El
valor buscado (27) es menor que el valor del nodo (29), con lo que de existir el nodo
con valor 27, estaría a la izquierda del nodo de valor 29.
• Intentamos movernos al hijo izquierdo del nodo 29 pero vemos que el puntero
correspondiente apunta a null, luego el nodo 29 no tiene hijo izquierdo.
• Concluimos que el nodo de valor 27 no existe en nuestro árbol.
Paso 4: Inserción de un nodo
Supongamos que queremos insertar el nodo de valor 30 en nuestro árbol. Lo primero que
hay que hacer es recorrer el árbol buscando el nodo que se quiere insertar, siguiendo el
proceso de búsqueda ya explicado en los dos pasos anteriores.
Si encontramos el nodo con el valor que queremos insertar, daríamos un mensaje de error
diciendo que el nodo ya existe, puesto que no se admiten duplicados.
Por el contrario, si en el proceso de búsqueda llegamos a un hueco, insertamos el nodo en
dicho hueco.
El proceso de inserción para un nodo que no existe, por ejemplo el nodo 30, se muestra en
la imagen siguiente, marcando en rojo el camino seguido.
Inserción de un nodo
Sin embargo, si el nodo que queremos insertar ya existe, al realizar el proceso de búsqueda
daremos con él y entonces emitiremos el correspondiente mensaje de error, indicando que
el nodo ya existe y por tanto no se puede insertar. En la imagen siguiente puede verse esta
situación para el caso de que el nodo a insertar tuviera un valor de 8.
Intento de inserción de un nodo existente
Paso 5: Eliminación de un nodo hoja
Habíamos dicho que el proceso de eliminación de un nodo era el más complicado y que
adoptábamos estrategias distintas dependiendo de los hijos que tuviera el nodo a eliminar.
El caso más sencillo es cuando el nodo no tiene ningún hijo, es decir, cuando es un nodo
hoja.
Eliminación de un nodo hoja
En este caso, sencillamente buscábamos el nodo y lo eliminábamos. Además, hacíamos que
el nodo del padre que le apuntaba, pasara a apuntar a null.
Paso 6: Eliminación de un nodo con un hijo
Para eliminar un nodo que tenga un hijo, primero lo localizamos, luego hacemos que el
puntero que apunta al nodo a eliminar, pase a apuntar al nodo hijo de este.
El proceso se puede observar en la figura siguiente:
Eliminación de un nodo con un hijo
• Empezamos localizando el nodo a eliminar, en este caso, aquel con el valor 12.
• Comparamos con el nodo raíz, como 12 es menor que 18, nos movemos al nodo
hijo izquierdo.
• El hijo izquierdo tiene el valor 9, que es menor que 12, luego nos movemos al hijo
derecho de este, y en ese nodo ya encontramos el nodo que buscábamos.
• El nodo con valor 12, tiene un único hijo, el izquierdo, con el valor 11..
• Hacemos que el puntero que apuntaba al nodo a eliminar, puntero ubicado en el
padre del nodo a eliminar, apunte al hijo de este. Es decir, el nodo con valor 9 pasa
a tener un hijo derecho con valor 11.
• Ahora ya podemos borrar el nodo 12.
Paso 7: Eliminación de un nodo con dos hijos, promocionando un valor del
subárbol izquierdo
Habíamos visto que cuando queremos eliminar un nodo que tiene dos hijos, tenemos dos
posibilidades para rellenar el hueco que este nodo deja: Podemos tomar el nodo de su
subárbol izquierdo que tenga un valor mayor, o el nodo de su subárbol derecho que tenga
un valor menor.
Veamos el primer caso con el ejemplo de la siguiente figura:
Promocionando el subárbol izquierdo
• Queremos eliminar nada más ni nada menos que el nodo raíz, con valor 18.
• El nodo raíz tiene dos subárboles, el de la izquierda con nodo raíz con valor 9, y el
de la derecha con nodo raíz de valor 25.
• Al eliminar el nodo de valor 18, tendremos que reemplazarlo por otro nodo del
árbol, que pasaría a ocupar la posición de este en la estructura. En esta ocasión,
vamos a buscar dicho nodo en el subárbol izquierdo.
• Como buscamos el nodo en el subárbol izquierdo, tenemos que buscar el nodo de
mayor valor, que por como construimos el árbol, coincidirá con el nodo que este
más a la derecha. En nuestro caso, el nodo de valor 12.
• Substituimos el nodo de valor 18 por el de valor 12.
• Eliminamos el nodo inicial de valor 12 que previamente hemos copiado en el nodo
de valor 18. El nodo inicial con valor 12 no puede tener dos hijos, ya que si tuviera
un hijo a la derecha, no sería el nodo mayor del subárbol izquierdo. Así es que este
nodo podrá tener un hijo o ninguno. La eliminación de un nodo en ambos casos, la
he explicado en los pasos 6 y 5 respectivamente.
Tras realizar estas operaciones, nos queda el siguiente árbol binario:
Subárbol izquierdo promocionado
Paso 8: Eliminación de un nodo con dos hijos, promocionando un valor del
subárbol derecho
En esta ocasión, al eliminar un nodo con dos hijos, vamos a buscar en el subárbol derecho,
el nodo más pequeño, el que tenga el menor valor.
Para ver como procederíamos, usamos el mismo ejemplo que en el caso anterior, sólo que
recorreremos el subárbol derecho y buscaremos el valor menor de todos los nodos.
En la siguiente figura, podemos apreciar el proceso:
Promocionando el subárbol derecho
• Queremos eliminar el nodo raíz, con valor 18.
• Buscamos en el subárbol derecho, el nodo que contenga el menor valor, que
coincidirá con aquel que este más a la izquierda en el subárbol derecho. Este nodo
es el nodo con valor 21.
• Substituimos el nodo de valor 18 por el de valor 21.
• Eliminamos el nodo inicial de valor 21 que previamente hemos copiado en el nodo
de valor 18.
Tras realizar estas operaciones, nos queda el siguiente árbol binario:
Subárbol derecho promocionado
