Árbol binario de búsqueda explicado: cómo funciona, código y complejidad

Qué problema resuelve un árbol binario de búsqueda

Un arreglo ordenado permite búsqueda binaria rápida, pero insertar un elemento nuevo desplaza todo lo que sigue. Una tabla hash busca e inserta rápido, pero no mantiene orden, así que no puede responder "¿cuál es la menor clave mayor que 42?" ni "lista todas las claves entre 10 y 20". Un árbol binario de búsqueda mantiene las claves ordenadas y aun así permite insertar y eliminar con rapidez. Es la base de los mapas y conjuntos ordenados como TreeMap de Java y std::map de C++, que usan variantes autobalanceadas.

La regla en palabras sencillas

Cada nodo tiene una clave, un hijo izquierdo opcional y un hijo derecho opcional. Para 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: ve a la izquierda si la clave es menor, a la derecha si es mayor, y detente si es igual o si te sales del árbol.

Ejemplo resuelto: construir y buscar en un árbol

Inserta 8, 3, 10, 1, 6, 14, 4 en este orden. Cada clave nueva baja desde la raíz y se convierte en hoja donde se sale del árbol.

Buscar el 4 compara con 8, 3, 6 y luego 4: cuatro comparaciones en un árbol de siete claves. Buscar el 7 compara con 8, 3, 6 y luego no encuentra hijo derecho del 6, así que el 7 no está.

Implementación en Python

Insertar y buscar son bucles cortos. Eliminar tiene tres casos: el nodo no tiene hijos (se quita), tiene un hijo (se reemplaza por él) o tiene dos hijos (se copia su sucesor inorder, la clave menor del subárbol derecho, y luego se elimina ese sucesor).

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

Complejidad temporal y espacial

El peor caso es real, no teórico: insertar claves ya ordenadas (1, 2, 3, ...) en un BST simple deja a cada nodo solo con hijo derecho, y el árbol se convierte en una lista enlazada. Los órdenes de inserción aleatorios dan una altura esperada de O(log n).

Variantes balanceadas y errores comunes

Los árboles autobalanceados mantienen la altura en O(log n) reestructurándose con rotaciones tras insertar y eliminar.

• Validar un BST comprobando solo padre e hijo. Pasa en su lugar un rango válido (low, high) hacia abajo.
• Olvidar devolver la raíz (posiblemente nueva) en la inserción y eliminación recursivas, de modo que los cambios se pierden.
• Recursión profunda en un árbol degenerado: el límite de recursión por defecto de Python es de unos 1000, así que una cadena de 5000 nodos hace fallar el código recursivo. Usa bucles o mantén el árbol balanceado.
• Política de duplicados indefinida: decide si los duplicados se ignoran, se cuentan o van siempre hacia un lado.

Cuándo usar un BST y preguntas típicas de entrevista

Usa un BST balanceado cuando necesites datos ordenados con inserciones y eliminaciones frecuentes: consultas por rango, búsquedas floor y ceiling, estadísticos de rango u orden, o iterar en orden. Usa una tabla hash cuando solo necesites buscar una clave exacta. En Python, la biblioteca estándar no trae un mapa en árbol; las opciones comunes son una lista ordenada con el módulo bisect para datos pequeños o casi estáticos, o el paquete de terceros sortedcontainers.

Preguntas típicas de entrevista: validar un BST, encontrar el k-ésimo elemento menor (recorrido inorder), ancestro común más bajo, convertir un arreglo ordenado en un BST balanceado (elige el medio como raíz) y hallar el sucesor inorder de un nodo.