Árbol de Búsqueda Binaria (BST) en Python

En este artículo descubrirás qué es un árbol de búsqueda binaria, cómo implementarlo paso a paso en Python 3.12+, y cómo usarlo en escenarios reales. Incluimos ejemplos de inserción, eliminación, recorridos, balanceo, comparativas de rendimiento y buenas prácticas para producción.

1. Conceptos básicos

• Definición: Un árbol de búsqueda binaria (BST) es una estructura de datos jerárquica en la que cada nodo contiene una clave y cumple la regla key(left) < key(node) < key(right).
• Propiedades clave:
  • Los sub‑árboles izquierdo y derecho son también BST.
  • Operaciones típicas (búsqueda, inserción, borrado) tienen complejidad O(h), donde h es la altura del árbol.
  • En el peor caso (árbol degenerado) h = n → O(n). En el mejor caso (árbol balanceado) h = log₂ n → O(log n).
• Usos habituales: índices de bases de datos, diccionarios en memoria, sistemas de archivos, autocompletado y algoritmos de compresión.

2. Implementación en Python

Utilizaremos dataclasses para una definición clara y tipada. El código está preparado para Python 3.12 y sigue las recomendaciones de PEP‑8 y PEP‑484 (type hints).

from __future__ import annotations
from dataclasses import dataclass, field
from typing import Optional, Generator, Any
@dataclass
class Node:
    key: Any
    value: Any = None
    left: Optional[Node] = field(default=None, repr=False)
    right: Optional[Node] = field(default=None, repr=False)
    parent: Optional[Node] = field(default=None, repr=False)
class BinarySearchTree:
    def __init__(self) -> None:
        self.root: Optional[Node] = None
        self._size = 0
    # ------------------------------------------------------------------
    #  Métodos públicos
    # ------------------------------------------------------------------
    def insert(self, key: Any, value: Any = None) -> Node:
        """Inserta  con  y devuelve el nodo creado.
        Si la clave ya existe, actualiza su valor.
        """
        if self.root is None:
            self.root = Node(key, value)
            self._size = 1
            return self.root
        return self._insert_rec(self.root, key, value)
    def find(self, key: Any) -> Optional[Node]:
        """Busca la clave y devuelve el nodo o  si no está.
        """
        return self._find_rec(self.root, key)
    def delete(self, key: Any) -> bool:
        """Elimina el nodo con . Retorna  si se eliminó.
        """
        node = self.find(key)
        if node is None:
            return False
        self._delete_node(node)
        self._size -= 1
        return True
    def inorder(self) -> Generator[Node, None, None]:
        """Recorrido  (izquierda, raíz, derecha)."""
        yield from self._inorder_rec(self.root)
    def preorder(self) -> Generator[Node, None, None]:
        """Recorrido 
 (raíz, izquierda, derecha)."""
        yield from self._preorder_rec(self.root)
    def postorder(self) -> Generator[Node, None, None]:
        """Recorrido  (izquierda, derecha, raíz)."""
        yield from self._postorder_rec(self.root)
    def height(self) -> int:
        """Devuelve la altura del árbol (0 para árbol vacío)."""
        return self._height_rec(self.root)
    def size(self) -> int:
        return self._size
    # ------------------------------------------------------------------
    #  Métodos internos (recursivos)
    # ------------------------------------------------------------------
    def _insert_rec(self, current: Node, key: Any, value: Any) -> Node:
        if key < current.key:
            if current.left is None:
                current.left = Node(key, value, parent=current)
                self._size += 1
                return current.left
            return self._insert_rec(current.left, key, value)
        elif key > current.key:
            if current.right is None:
                current.right = Node(key, value, parent=current)
                self._size += 1
                return current.right
            return self._insert_rec(current.right, key, value)
        else:
            # clave duplicada → actualizamos valor
            current.value = value
            return current
    def _find_rec(self, current: Optional[Node], key: Any) -> Optional[Node]:
        if current is None:
            return None
        if key == current.key:
            return current
        return self._find_rec(current.left if key < current.key else current.right, key)
    def _delete_node(self, node: Node) -> None:
        # Caso 1: nodo hoja
        if node.left is None and node.right is None:
            self._replace_node_in_parent(node, None)
        # Caso 2: un solo hijo
        elif node.left is None:
            self._replace_node_in_parent(node, node.right)
        elif node.right is None:
            self._replace_node_in_parent(node, node.left)
        # Caso 3: dos hijos → usamos sucesor in‑order
        else:
            successor = self._min_node(node.right)
            node.key, node.value = successor.key, successor.value
            self._delete_node(successor)
    def _replace_node_in_parent(self, node: Node, new_child: Optional[Node]) -> None:
        if node.parent:
            if node is node.parent.left:
                node.parent.left = new_child
            else:
                node.parent.right = new_child
            if new_child:
                new_child.parent = node.parent
        else:
            # node es raíz
            self.root = new_child
            if new_child:
                new_child.parent = None
    def _min_node(self, current: Node) -> Node:
        while current.left:
            current = current.left
        return current
    # ------------------------------------------------------------------
    #  Recorridos (generadores)
    # ------------------------------------------------------------------
    def _inorder_rec(self, node: Optional[Node]) -> Generator[Node, None, None]:
        if node:
            yield from self._inorder_rec(node.left)
            yield node
            yield from self._inorder_rec(node.right)
    def _preorder_rec(self, node: Optional[Node]) -> Generator[Node, None, None]:
        if node:
            yield node
            yield from self._preorder_rec(node.left)
            yield from self._preorder_rec(node.right)
    def _postorder_rec(self, node: Optional[Node]) -> Generator[Node, None, None]:
        if node:
            yield from self._postorder_rec(node.left)
            yield from self._postorder_rec(node.right)
            yield node
    def _height_rec(self, node: Optional[Node]) -> int:
        if node is None:
            return -1  # altura de árbol vacío = -1, árbol con raíz = 0
        return 1 + max(self._height_rec(node.left), self._height_rec(node.right))

Tip: El árbol anterior es no balanceado. Para producción se recomienda usar variantes auto‑balanceadas (AVL, Red‑Black) o la librería bisect de Python cuando el conjunto de datos es estático.

3. Ejemplos de uso práctico

A continuación se muestra cómo emplear la clase BinarySearchTree en un script real.

if __name__ == "__main__":
    bst = BinarySearchTree()
    # Insertar valores aleatorios
    for k in [50, 30, 70, 20, 40, 60, 80]:
        bst.insert(k, f"valor-{k}")
    print("Altura del árbol:", bst.height())
    print("Recorrido in‑order (ordenado):")
    print([node.key for node in bst.inorder()])
    # Búsqueda
    nodo = bst.find(60)
    print("Encontrado:", nodo.key, nodo.value if nodo else None)
    # Borrado de un nodo con dos hijos
    bst.delete(30)
    print("In‑order después de borrar 30:")
    print([node.key for node in bst.inorder()])

4. Comparativa con otras estructuras de datos

Si tu aplicación requiere garantías de rendimiento logarítmico en todo momento, opta por una variante auto‑balanceada (AVL o Red‑Black) o por la clase sortedcontainers.SortedDict de la biblioteca sortedcontainers.

5. Extensiones avanzadas

5.1. Balanceo con rotaciones (Árbol AVL)

Implementar rotaciones simples (left‑rotate, right‑rotate) permite mantener la altura ⌊log₂ n⌋. A continuación un fragmento de código de rotación derecha:

def _right_rotate(self, y: Node) -> Node:
    x = y.left
    T2 = x.right
    # Rotación
    x.right = y
    y.left = T2
    # Actualizar padres
    x.parent = y.parent
    y.parent = x
    if T2:
        T2.parent = y
    # Si x era raíz, actualizar referencia
    if x.parent is None:
        self.root = x
    return x

Integra estas rotaciones dentro de insert y delete para obtener un AVL completo. La librería bintrees ya provee AVLTree listo para usar.

5.2. Persistencia con pickle y json

Para guardar y cargar el árbol entre ejecuciones:

import pickle
def save_tree(bst: BinarySearchTree, path: str) -> None:
    with open(path, "wb") as f:
        pickle.dump(bst, f)
def load_tree(path: str) -> BinarySearchTree:
    with open(path, "rb") as f:
        return pickle.load(f)

Si necesitas interoperabilidad con otros lenguajes, exporta a JSON usando un recorrido inorder y reconstruye con insert en el otro entorno.

6. Buenas prácticas y troubleshooting

• Validar claves duplicadas: Decidir si sobrescribir, lanzar excepción o mantener una lista de valores.
• Control de recursión: Para árboles con >10⁶ nodos, usa versiones iterativas o aumenta sys.setrecursionlimit con cautela.
• Pruebas unitarias: Usa pytest y hypothesis para generar árboles aleatorios y verificar invariantes (left.key < node.key < right.key).
• Perfilado de rendimiento: cProfile muestra que la mayor parte del tiempo se gasta en comparaciones de claves; considera usar claves numéricas o functools.total_ordering para reducir overhead.
• Seguridad: Nunca confíes en datos externos sin sanitizarlos; una clave maliciosa que cause una cadena de recursión profunda puede provocar stack overflow. Limita la profundidad máxima o usa una implementación iterativa.

7. Rendimiento y escalabilidad

En entornos de alta concurrencia (p. ej., microservicios) se recomienda:

1. Utilizar read‑write locks (threading.RLock) para proteger operaciones de inserción/borrado.
2. Persistir en una base de datos en memoria como Redis Sorted Set cuando el árbol debe ser compartido entre procesos.
3. Para big data, sustituir el BST por estructuras de índice B‑Tree o LSM‑Tree (p. ej., RocksDB).

Benchmarks aproximados (Python 3.12, CPU i7‑12700K):