Árbol binario de búsqueda

Instrucciones

Insertar y buscar 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 agregar el elemento en el espacio que creamos. Pero esto igual nos obliga a desplazar muchos elementos una posición hacia abajo.

Sin embargo, los árboles de búsqueda binaria pueden operar sobre datos ordenados de forma mucho más eficiente.

Un árbol de búsqueda binaria consiste en 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 estos otros nodos, a su vez, tienen otros nodos debajo de ellos, decimos que las variables left y right apuntan a subárboles. Todos los datos del subárbol izquierdo son menores o iguales que los datos del nodo actual, y todos los datos del subárbol derecho son mayores que los datos 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.