Árbol binario de búsqueda

Instrucciones

Inserta y busca números en un árbol binario.

Cuando necesitamos representar datos ordenados, un array no es una buena estructura de datos.

Supongamos que tenemos el array [1, 3, 4, 5] y le añadimos 2, de modo que se convierte en [1, 3, 4, 5, 2]. ¡Ahora tenemos que volver a ordenar todo el array! Podemos mejorar esto si nos damos cuenta de que solo necesitamos hacer sitio para el nuevo elemento [1, nil, 3, 4, 5] y luego añadirlo en el hueco que hemos creado. Pero esto sigue obligándonos a desplazar muchos elementos una posición hacia abajo.

Los árboles binarios de búsqueda, sin embargo, pueden operar sobre datos ordenados de forma mucho más eficiente.

Un árbol binario de búsqueda consta de una serie de nodos conectados. Cada nodo contiene un dato (por ejemplo, el número 3), una variable llamada left y una variable llamada right. Las variables left y right apuntan a nil o a otros nodos. Como esos otros nodos tienen, a su vez, otros nodos por debajo, decimos que las variables left y right apuntan a subárboles. Todos los datos del subárbol izquierdo son menores o iguales que el dato del nodo actual, y todos los datos del subárbol derecho son mayores que el dato del nodo actual.

Por ejemplo, si tuviéramos un nodo que contiene el dato 4 y añadiéramos el dato 2, nuestro árbol tendría este aspecto:

      4
     /
    2

Si después añadiéramos 6, tendría este aspecto:

      4
     / \
    2   6

Si después añadiéramos 3, tendría este aspecto

       4
     /   \
    2     6
     \
      3

Y si después añadiéramos 1, 5 y 7, tendría este aspecto

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

Créditos

Las imágenes fueron creadas por habere-et-dispertire con PGF/TikZ de Till Tantau.

Implementación

Implementar una estructura de árbol eficiente y modificable en Cairo (o en cualquier lenguaje puramente funcional con memoria inmutable) es todo un reto, porque estos lenguajes están diseñados para evitar cambiar los datos una vez creados. Esta inmutabilidad implica que, en lugar de actualizar directamente un nodo del árbol, hay que crear una nueva versión del árbol cada vez que lo modificas.

Para ver por qué ocurre esto, imagina una estructura de árbol binario sencilla en la que cada nodo tiene un hijo izquierdo y un hijo derecho. Supongamos que partimos de un árbol pequeño como este:

       1
      / \
     2   3

Ahora supongamos que queremos añadir un nuevo nodo 4 como hijo izquierdo del nodo 2. En un lenguaje puramente funcional (como Cairo o Haskell), la memoria es inmutable, así que no podemos simplemente añadir el nodo 4 directamente a 2. En su lugar, tenemos que crear una nueva versión de cada nodo a lo largo del camino desde la raíz hasta el nodo modificado, porque ahora cada nodo de ese camino apunta a un subárbol nuevo o modificado.

El proceso sería más o menos así:

1. Añadir el nodo 4 al nodo 2:

   • Crea una nueva versión del nodo 2, que ahora tiene 4 como hijo izquierdo.

       2'
      / 
     4   
   

2. Actualizar el nodo raíz:

   • Como el nodo 1 apuntaba originalmente al antiguo 2, creamos una nueva versión del nodo raíz 1' que ahora apunta al nodo actualizado 2' a la izquierda y mantiene el nodo 3 a la derecha.

       1'
      / \
     2'  3
   

Así, el árbol resultante queda así:

       1'
      / \
     2'  3
    /
   4

Este nuevo árbol (1') sigue pareciéndose al original, pero con un camino actualizado. La clave está en que tuvimos que recrear cada nodo a lo largo del camino (1 hasta 2) para preservar la inmutabilidad, ya que los nodos existentes no se pueden modificar in situ. El árbol original sigue existiendo (por ejemplo, para todas las referencias a su raíz original 1), mientras que este nuevo árbol representa el estado modificado.

En árboles grandes, este enfoque puede resultar costoso, ya que cada nueva modificación obliga a recrear un camino de nodos desde la raíz hasta el nodo actualizado, aunque solo cambie en realidad una pequeña parte del árbol.