Operaciones con árboles binarios de búsqueda

Ahora que ya sabemos como funcionan los árboles binarios de búsqueda, vamos a estudiar como trabajar con ellos. 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
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 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:

Flujo para la insercción de un nodo
Flujo para la insercció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
Á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
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
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
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
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
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
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
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
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
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
Subárbol derecho promocionado

NOTA:

Este post es parte de la colección “Sistemas de acceso y almacenamiento de datos”. Puedes ver el índice de esta colección aquí.