Árboles binarios de búsqueda

Un árbol binario de búsqueda equilibrado de 1023 claves encuentra cualquiera de ellas en 10 comparaciones como máximo; construido a partir de datos ordenados, las mismas claves pueden llevar 1023.

La búsqueda binaria, incorporada a la forma

La búsqueda binaria en un arreglo ordenado encuentra una clave en unas log₂ n comprobaciones, pero insertar en un arreglo ordenado mueve valores. Una tabla hash inserta rápido, pero olvida el orden: no puede decirte con facilidad cuál es la clave más pequeña ni cuál es la siguiente después de 40. Un árbol binario de búsqueda (ABB, o BST en inglés) busca las dos cosas. Está hecho de nodos, como una lista enlazada, pero cada nodo tiene dos punteros, left y right. El nodo de arriba es la raíz; un nodo sin hijos es una hoja.

Una sola regla lo convierte en un árbol de búsqueda: en cada nodo, todas las claves de su subárbol izquierdo son menores y todas las de su subárbol derecho son mayores. Para buscar una clave, empieza en la raíz y compara. Si es igual, la encontraste. Si es menor, ve a la izquierda; si es mayor, a la derecha. Cada comparación descarta un subárbol entero, igual que la búsqueda binaria descarta la mitad de la lista. Buscar 60 en el árbol 50, 30, 70, 20, 40, 60, 80 compara con 50, luego con 70 y luego con 60: 3 comparaciones.

Insertar sigue el mismo camino. Ve a la izquierda o a la derecha hasta que el puntero que necesitas esté vacío, y cuelga ahí el nodo nuevo. Insertar 45 compara con 50 (a la izquierda), 30 (a la derecha) y 40 (a la derecha), y 40 no tiene hijo derecho, así que 45 pasa a serlo. Eliminar un nodo que no es hoja requiere una idea más: las notas del MIT intercambian su elemento con la clave siguiente o anterior en orden y eliminan desde ahí. La regla de conteo del laboratorio es una comparación por cada nodo del camino.

La altura lo es todo

¿Cuántas comparaciones puede llevar una búsqueda? Como máximo una por nivel, así que el costo depende de la altura del árbol, el número de aristas del camino más largo desde la raíz hasta una hoja. Las notas del MIT lo dicen así: las operaciones del árbol se ejecutan en tiempo O(h). El árbol 50, 30, 70, 20, 40, 60, 80 tiene altura 2, así que ninguna búsqueda necesita más de 3 comparaciones. Un árbol perfectamente equilibrado con 1023 nodos tiene altura 9 y necesita 10 como máximo.

Pero la forma depende del orden de inserción. Inserta 10, 20, 30, 40, 50, 60, 70 en orden y cada clave es mayor que todas las anteriores, así que cada nodo nuevo va a la derecha del último. El árbol se convierte en una cadena de altura 6, y buscar 70 lleva 7 comparaciones: una lista enlazada con punteros de más. Con 1023 claves ordenadas, la peor búsqueda lleva 1023 comparaciones en lugar de 10.

Los árboles equilibrados lo resuelven reorganizándose después de cada inserción o eliminación. El primer esquema fue el árbol AVL, de Georgy Adelson-Velsky y Evgenii Landis en 1962, que trata la clase 7 del MIT. En cada nodo mantiene las alturas de los dos subárboles con una diferencia de 1 como máximo, y repara cualquier desequilibrio con pequeños movimientos locales llamados rotaciones. Así la altura se mantiene en O(log n), y buscar, insertar y eliminar siguen siendo O(log n) sea cual sea el orden en que lleguen las claves.

Las claves en orden, sin costo extra

Un ABB guarda algo más que la pertenencia. Visita el subárbol izquierdo, luego el nodo y luego el subárbol derecho, de forma recursiva, y las claves salen ordenadas. Este recorrido en orden (in-order; el MIT lo llama orden de recorrido) es la forma en que un ABB responde "clave más pequeña", "clave más grande" y "siguiente clave después de 40", las operaciones de orden de la interfaz Set del MIT que una tabla hash no puede hacer rápido.