Árbol de búsqueda binaria (BST)

Al finalizar este tema

Podrás explicar las reglas fundamentales del árbol de búsqueda binaria, implementar la inserción y la búsqueda mediante código, y obtener datos ordenados mediante el recorrido inorden.

Limitaciones de los arreglos

La búsqueda binaria en un arreglo ordenado es rápida, con una complejidad de O(log n). Sin embargo, la inserción y la eliminación son lentas, ya que insertar un valor en medio requiere desplazar los elementos restantes:

[2, 5, 8, 12, 15]
     ↑ Para insertar 7 aquí
[2, 5, 7, 8, 12, 15]  ← Hay que desplazar 8, 12, 15 a la derecha (O(n))

Se necesita una estructura de datos con búsquedas e inserciones rápidas. Este es el árbol binario de búsqueda.

Reglas clave

Un árbol binario de búsqueda (BST) sigue una única regla:

Hijo izquierdo < Padre < Hijo derecho

8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

En cualquier nodo, todos los valores del subárbol izquierdo son menores que su propio valor, y todos los valores del subárbol derecho son mayores que su propio valor.

Implementación de nodos

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Cada nodo contiene un valor y dos punteros que apuntan a sus hijos izquierdo y derecho.

Inserción

Al insertar un nuevo valor, se comienza desde la raíz y se desciende siguiendo las reglas:

def insert(root, value):
    if root is None:
        return Node(value)

    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)

    return root

# Crear árbol
root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)

Si el valor es menor que el del nodo actual, se desplaza hacia la izquierda; si es mayor, hacia la derecha. Al encontrar un espacio vacío, se crea un nuevo nodo en esa posición.

Búsqueda

def search(root, target):
    if root is None:
        return False

    if target == root.value:
        return True
    elif target < root.value:
        return search(root.left, target)
    else:
        return search(root.right, target)

print(search(root, 7))   # True
print(search(root, 5))   # False

Funciona bajo el mismo principio que la búsqueda binaria. Al descartar la mitad en cada paso, la complejidad es O(log n) en un árbol equilibrado.

Proceso de búsqueda (al buscar el 7):

8 → 7 < 8, izquierda
3 → 7 > 3, derecha
6 → 7 > 6, derecha
7 → ¡Encontrado!

Recorrido in-order — Resultado ordenado

Al visitar el árbol en el orden "izquierda → actual → derecha", se obtienen los valores en orden ascendente. Esto se denomina recorrido in-order (in-order traversal).

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.value] + inorder(root.right)

print(inorder(root))  # [1, 3, 4, 6, 7, 8, 10, 13, 14]

Siguiendo la regla del BST (izquierda < padre < derecha), al recorrer desde la izquierda se obtiene de forma natural un orden ascendente. Esto permite obtener datos ordenados sin necesidad de un algoritmo de ordenación adicional.

Tres tipos de recorrido

def preorder(root):   # Preorden: raíz → izquierda → derecha
    if root is None: return []
    return [root.value] + preorder(root.left) + preorder(root.right)

def postorder(root):  # Postorden: izquierda → derecha → raíz
    if root is None: return []
    return postorder(root.left) + postorder(root.right) + [root.value]

print(preorder(root))   # [8, 3, 1, 6, 4, 7, 10, 14, 13]
print(inorder(root))    # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(postorder(root))  # [1, 4, 7, 6, 3, 13, 14, 10, 8]

Peor caso

El rendimiento de un BST depende del equilibrio del árbol:

# Árbol equilibrado (O(log n))     # Árbol sesgado (O(n)) — esencialmente una lista enlazada
        8                    1
       / \                    \
      3   10                   2
     / \    \                   \
    1   6    14                  3
                                  \
                                   4

Insertar datos ordenados secuencialmente produce un árbol desequilibrado. Para solucionar este problema, existen árboles autoequilibrados como el árbol AVL o el árbol Rojo-Negro. Python utiliza este tipo de árboles equilibrados internamente en su sorted(), y Java lo hace en su TreeMap.

Resumen de la complejidad temporal

Eliminación en BST — Tres casos

La eliminación es la operación más compleja en un BST:

def delete(root, value):
    if root is None:
        return None

    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        # Caso 1: Sin hijos (hoja) — simplemente eliminar
        if root.left is None and root.right is None:
            return None
        # Caso 2: Un hijo — el hijo reemplaza la posición
        elif root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # Caso 3: Dos hijos — reemplazar con el sucesor
        else:
            successor = find_min(root.right)
            root.value = successor.value
            root.right = delete(root.right, successor.value)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

Al eliminar un nodo con dos hijos, se reemplaza por el valor mínimo del subárbol derecho (sucesor inorden). De este modo, se mantiene la propiedad de orden de un BST.

¿Se utiliza BST directamente en la práctica?

Python no tiene un módulo integrado para BST. En su lugar:

from bisect import insort, bisect_left

sorted_list = []
insort(sorted_list, 5)   # insertar manteniendo el orden
insort(sorted_list, 3)
insort(sorted_list, 7)
print(sorted_list)  # [3, 5, 7]

idx = bisect_left(sorted_list, 5)  # búsqueda binaria
print(sorted_list[idx])  # 5

bisect proporciona una búsqueda de O(log n) similar a un BST en listas ordenadas. La inserción es O(n) (desplazamiento de elementos en el array), por lo que, si las inserciones son frecuentes, se recomienda utilizar bibliotecas de terceros como SortedContainers.

BST vs. Tabla hash vs. Array ordenado

Aunque las tablas hash son más rápidas, los BST son ventajosos cuando se requiere un "orden de clasificación". Un ejemplo representativo son los índices de bases de datos que requieren consultas de rango, como "valores entre 100 y 200".

Los BST son adecuados cuando es necesario "mantener datos ordenados dinámicamente". Es una estructura de datos que combina las ventajas de los arrays y las listas enlazadas.