Á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 agregamos 2, así que se convierte en [1, 3, 4, 5, 2]. ¡Ahora tenemos que ordenar todo el array de nuevo! Podemos mejorar esto si nos damos cuenta de que solo necesitamos hacer espacio para el nuevo elemento [1, nil, 3, 4, 5] y luego agregarlo en ese espacio. Pero esto todavía nos obliga a desplazar muchos elementos una posición.

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

Un árbol binario de búsqueda está formado por 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, a su vez, tienen otros nodos 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 agregáramos el dato 2, nuestro árbol se vería así:

      4
     /
    2

Si luego agregáramos 6, se vería así:

      4
     / \
    2   6

Si luego agregáramos 3, se vería así

       4
     /   \
    2     6
     \
      3

Y si luego agregáramos 1, 5 y 7, se vería así

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

Créditos

Las imágenes fueron creadas por habere-et-dispertire usando 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 después de crearlos. Esta inmutabilidad significa que, en lugar de actualizar un nodo del árbol directamente, hay que crear una nueva versión del árbol cada vez que lo modificas.

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

       1
      / \
     2   3

Ahora supongamos que queremos agregar 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 agregar 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 cada nodo de ese camino ahora apunta a un subárbol nuevo o modificado.

Así es como se vería el proceso:

1. Agregar el nodo 4 al nodo 2:

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

       2'
      / 
     4   
   

2. Actualizar el nodo raíz:

   • Como el nodo 1 originalmente apuntaba 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 al nodo 3 a la derecha.

       1'
      / \
     2'  3
   

Así, el árbol resultante queda:

       1'
      / \
     2'  3
    /
   4

Este nuevo árbol (1') todavía se parece al original, pero con un camino actualizado. El punto clave es que tuvimos que volver a crear cada nodo a lo largo del camino (1 hasta 2) para preservar la inmutabilidad, ya que los nodos existentes no se pueden modificar en el mismo lugar. El árbol original todavía existe (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 volverse costoso, ya que cada nueva modificación requiere recrear un camino de nodos desde la raíz hasta el nodo actualizado, incluso si en realidad solo cambia una pequeña parte del árbol.