Ahora que ya sabemos como funcionan los árboles binarios de búsqueda, vamos a estudiar las principales operaciones que realizaríamos con ellos.

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:

Diagrama de la búsqueda de un nodo en un árbol binario

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 búscamos 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:

Proceso de inserción de un nodo en un árbol binario

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 de partida

 

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 del nodo de valor 24

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 del nodo de valor 27

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 del nodo de valor 30

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.

Insercción del nodo de valor 8

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 del nodo de valor 8

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 del nodo de valor 12

  • 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:

Eliminación del nodo de valor 18 - promocionando el subarbol 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:

árbol binario de búsqueda resultante

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:

Eliminación del nodo de valor 18 - promocionando el subarbol 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:

árbol binario de búsqueda resultante

NOTA:

Este post es parte de la colección “Arquitectura de Datos” que reproduce los apuntes de la clase que imparto sobre el tema en ESIC. Puedes ver el índice de esta colección aquí.