El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Árboles Binarios de Búsqueda

Siguiente ►
►

Esta es la lección donde el módulo paga sus deudas. El hash del módulo 5 enmudecía ante "dame las tareas ordenadas por id" y "las de prioridad entre 1 y 3"; el inorden de 06-03 salía misteriosamente ordenado. Ambas cosas tienen la misma explicación: el árbol binario de búsqueda (ABB, o BST en inglés), un árbol binario con una regla de colocación — menores a la izquierda, mayores a la derecha — que convierte cada comparación en un descarte de medio árbol. Aquí implementarás la clase ArbolBusqueda completa (insertar, buscar, mínimo/máximo, borrar con sus tres casos, recorrido ordenado y búsqueda por rango), la usarás como índice de tareas de TaskFlow, y descubrirás también su talón de Aquiles: con datos que llegan ya ordenados, el ABB degenera en lista y todo se vuelve O(n) — el problema que motivará la siguiente lección.

Contenido

  1. La propiedad ABB: una regla, todas las consecuencias
  2. Buscar e insertar: descender comparando
  3. Mínimo, máximo y el inorden que sale ordenado
  4. Borrar: los tres casos
  5. Búsqueda por rango: la deuda del módulo 5, saldada
  6. El coste es O(altura): la demo del árbol degenerado
  7. dict vs ABB: cada uno a lo suyo

La propiedad ABB: una regla, todas las consecuencias

Un árbol binario de búsqueda es un árbol binario donde, para todo nodo con clave k:

  • Todas las claves de su subárbol izquierdo son menores que k.
  • Todas las claves de su subárbol derecho son mayores que k.
graph TD
    A((10)) --> B((6))
    A --> C((15))
    B --> D((3))
    B --> E((8))
    C --> F((12))
    C --> G((20))

El árbol de 06-03 era esto. Comprueba la propiedad en la raíz: a la izquierda del 10 están {6, 3, 8}, todos menores; a la derecha, {15, 12, 20}, todos mayores. Y ojo al adverbio todas: no basta con que cada hijo respete a su padre — el 8 es hijo derecho del 6 (correcto: 8 > 6), pero además debe ser menor que 10, porque vive en el subárbol izquierdo de la raíz. Esta distinción entre "regla local" y "regla sobre el subárbol entero" es el error clásico al validar un ABB, y lo cazaremos en 06-08.

La consecuencia operativa: parado en cualquier nodo, una sola comparación te dice en qué mitad seguir — igual que la búsqueda binaria del módulo 1, pero sobre una estructura enlazada que además admite inserciones y borrados baratos (el array ordenado buscaba en O(log n) pero insertaba en O(n) desplazando elementos). El ABB es, conceptualmente, la búsqueda binaria hecha estructura de datos.

Buscar e insertar: descender comparando

Construyamos la clase completa. Cada nodo guardará una clave (por la que se ordena) y un valor (la tarea de TaskFlow), como en la TablaHash:

class NodoABB:
    def __init__(self, clave, valor):
        self.clave = clave
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

class ArbolBusqueda:
    """Índice ordenado: clave -> valor, con recorridos y rangos."""

    def __init__(self):
        self.raiz = None

    def buscar(self, clave):
        """Devuelve el valor asociado a la clave, o None si no está. O(altura)."""
        nodo = self.raiz
        while nodo is not None:
            if clave == nodo.clave:
                return nodo.valor
            elif clave < nodo.clave:
                nodo = nodo.izquierdo      # lo menor solo puede estar a la izquierda
            else:
                nodo = nodo.derecho        # lo mayor, a la derecha
        return None

buscar es el descenso del árbol de decisión de 06-02, con la pregunta "¿la clave buscada es menor que la mía?". Cada comparación baja un nivel y descarta el otro subárbol entero: por eso el coste es O(altura), no O(n). Insertar sigue el mismo camino — la posición de una clave nueva es exactamente donde la búsqueda se habría caído del árbol:

    def insertar(self, clave, valor):
        """Inserta el par (o actualiza el valor si la clave ya existe). O(altura)."""
        if self.raiz is None:
            self.raiz = NodoABB(clave, valor)
            return
        nodo = self.raiz
        while True:
            if clave == nodo.clave:
                nodo.valor = valor                       # clave repetida: actualizar
                return
            elif clave < nodo.clave:
                if nodo.izquierdo is None:
                    nodo.izquierdo = NodoABB(clave, valor)
                    return
                nodo = nodo.izquierdo
            else:
                if nodo.derecho is None:
                    nodo.derecho = NodoABB(clave, valor)
                    return
                nodo = nodo.derecho

Montemos el índice de tareas por id (usamos ids enteros para comparar cómodamente):

indice = ArbolBusqueda()
tareas = [
    (10, {"id": 10, "titulo": "Desplegar API", "prioridad": 2, "estado": "pendiente"}),
    (6,  {"id": 6,  "titulo": "Revisar login", "prioridad": 1, "estado": "en curso"}),
    (15, {"id": 15, "titulo": "Copia de seguridad", "prioridad": 3, "estado": "pendiente"}),
    (3,  {"id": 3,  "titulo": "Arreglar CSS", "prioridad": 2, "estado": "pendiente"}),
    (8,  {"id": 8,  "titulo": "Migrar datos", "prioridad": 1, "estado": "bloqueada"}),
    (12, {"id": 12, "titulo": "Optimizar consultas", "prioridad": 2, "estado": "pendiente"}),
    (20, {"id": 20, "titulo": "Documentar API", "prioridad": 3, "estado": "pendiente"}),
]
for id_tarea, tarea in tareas:
    indice.insertar(id_tarea, tarea)

print(indice.buscar(8)["titulo"])    # Migrar datos
print(indice.buscar(99))             # None

El orden de inserción (10 primero, luego 6, 15...) ha construido exactamente el árbol del diagrama. Guarda este dato: la forma del ABB depende del orden de llegada de las claves. Volverá a mordernos en la sección 6.

Mínimo, máximo y el inorden que sale ordenado

La propiedad ABB regala tres operaciones que el hash ni sueña:

    def minimo(self):
        """La clave más pequeña: todo a la izquierda. O(altura)."""
        if self.raiz is None:
            return None
        nodo = self.raiz
        while nodo.izquierdo is not None:
            nodo = nodo.izquierdo
        return nodo.clave

    def maximo(self):
        """La clave más grande: todo a la derecha. O(altura)."""
        if self.raiz is None:
            return None
        nodo = self.raiz
        while nodo.derecho is not None:
            nodo = nodo.derecho
        return nodo.clave

    def en_orden(self):
        """Todas las (clave, valor) en orden ascendente de clave. O(n)."""
        resultado = []
        self._en_orden(self.raiz, resultado)
        return resultado

    def _en_orden(self, nodo, resultado):
        if nodo is None:
            return
        self._en_orden(nodo.izquierdo, resultado)
        resultado.append((nodo.clave, nodo.valor))
        self._en_orden(nodo.derecho, resultado)
print(indice.minimo(), indice.maximo())        # 3 20
print([clave for clave, _ in indice.en_orden()])   # [3, 6, 8, 10, 12, 15, 20]

Y aquí se cumple el anuncio de 06-03: el inorden de un ABB devuelve las claves ordenadas, siempre. La demostración cabe en dos líneas: el inorden visita izquierda → nodo → derecha; por la propiedad ABB, todo lo de la izquierda es menor que el nodo y todo lo de la derecha mayor; aplicando el mismo argumento recursivamente a cada subárbol, la salida completa queda ascendente. "Dame las tareas ordenadas por id" — la primera pregunta que dejó muda a la TablaHash — es ahora una llamada a en_orden(), en O(n) y sin ordenar nada: el árbol mantiene el orden como invariante permanente, no lo calcula bajo demanda como haría sorted() (O(n log n) cada vez).

Borrar: los tres casos

Borrar es la operación delicada: hay que quitar el nodo sin romper la propiedad para los demás. Tres casos, de fácil a difícil:

Caso Situación Solución
1 El nodo es hoja Desengancharlo del padre, sin más
2 Tiene un solo hijo El hijo ocupa su lugar (como saltarse un nodo en la lista enlazada)
3 Tiene dos hijos Sustituirlo por su sucesor y borrar el sucesor

El caso 3 merece explicación. No podemos dejar un hueco con dos subárboles colgando; necesitamos un sustituto que mantenga "izquierda menor, derecha mayor". El candidato perfecto es el sucesor inorden: la menor clave del subárbol derecho (el nodo que saldría justo después en en_orden). Es mayor que todo el subárbol izquierdo (está a la derecha) y menor que el resto del subárbol derecho (es su mínimo) — encaja exactamente. Y borrarlo de su posición original es fácil: siendo el mínimo de un subárbol, no tiene hijo izquierdo (caso 1 o 2 garantizado). El simétrico (máximo del subárbol izquierdo, el predecesor) funciona igual de bien.

graph TD
    subgraph "Borrar 10 (dos hijos)"
        A((10)) --> B((6))
        A --> C((15))
        C --> F((12))
        C --> G((20))
    end
    subgraph "El sucesor 12 lo sustituye"
        A2((12)) --> B2((6))
        A2 --> C2((15))
        C2 -.borrado.-> F2((12))
        C2 --> G2((20))
    end

La implementación recursiva es la más limpia — cada llamada devuelve la raíz (quizá nueva) de su subárbol, y el padre la reengancha; el mismo patrón "reconstruir al volver" que usaremos en el AVL:

    def borrar(self, clave):
        self.raiz = self._borrar(self.raiz, clave)

    def _borrar(self, nodo, clave):
        if nodo is None:
            return None                              # clave no encontrada: nada que hacer
        if clave < nodo.clave:
            nodo.izquierdo = self._borrar(nodo.izquierdo, clave)
        elif clave > nodo.clave:
            nodo.derecho = self._borrar(nodo.derecho, clave)
        else:
            # Encontrado. Casos 1 y 2: cero o un hijo
            if nodo.izquierdo is None:
                return nodo.derecho                  # puede ser None (caso hoja)
            if nodo.derecho is None:
                return nodo.izquierdo
            # Caso 3: dos hijos -> sucesor = mínimo del subárbol derecho
            sucesor = nodo.derecho
            while sucesor.izquierdo is not None:
                sucesor = sucesor.izquierdo
            nodo.clave, nodo.valor = sucesor.clave, sucesor.valor   # copiar el sucesor aquí
            nodo.derecho = self._borrar(nodo.derecho, sucesor.clave) # y borrarlo de allí
        return nodo
indice.borrar(10)     # la raíz, con dos hijos: el caso difícil
print([c for c, _ in indice.en_orden()])   # [3, 6, 8, 12, 15, 20] — sigue ordenado
print(indice.raiz.clave)                   # 12: el sucesor ocupó la raíz

Léelo dos veces, que lo merece: los casos 1 y 2 se resuelven devolviendo el hijo (o None) para que el padre lo adopte; el caso 3 no borra el nodo físico sino que le copia dentro los datos del sucesor y delega el borrado real en un caso fácil. Coste total: O(altura) — un descenso para encontrar, otro parcial para el sucesor.

Búsqueda por rango: la deuda del módulo 5, saldada

La pregunta que el hash no podía ni plantearse: "todas las tareas con clave entre a y b". En el ABB, la propiedad permite podar: si la clave de un nodo ya es menor que a, su subárbol izquierdo entero queda fuera del rango — ni lo visitamos.

    def rango(self, desde, hasta):
        """Pares (clave, valor) con desde <= clave <= hasta, en orden. O(altura + k)."""
        resultado = []
        self._rango(self.raiz, desde, hasta, resultado)
        return resultado

    def _rango(self, nodo, desde, hasta, resultado):
        if nodo is None:
            return
        if nodo.clave > desde:                 # puede haber candidatos a la izquierda
            self._rango(nodo.izquierdo, desde, hasta, resultado)
        if desde <= nodo.clave <= hasta:       # ¿este nodo entra?
            resultado.append((nodo.clave, nodo.valor))
        if nodo.clave < hasta:                 # puede haber candidatos a la derecha
            self._rango(nodo.derecho, desde, hasta, resultado)

Es un inorden con dos frenos: solo entra en un subárbol si el rango puede alcanzarlo. El coste es O(altura + k), con k resultados: bajar hasta el rango cuesta la altura, y a partir de ahí solo se pisa lo que se devuelve (más una franja de frontera). Comparado con el hash: allí la única opción era recorrer TODO y filtrar, O(n) siempre.

¿Y "prioridad entre 1 y 3"? La prioridad no es única (muchas tareas comparten prioridad) y nuestro ABB quiere claves distintas. El truco profesional, el mismo del (prioridad, contador, tarea) de la BandejaUrgencias del módulo 4: una clave compuesta (prioridad, id) — las tuplas se comparan lexicográficamente, así que ordena por prioridad y desempata por id, y cada par es único:

por_prioridad = ArbolBusqueda()
for id_tarea, tarea in tareas:
    por_prioridad.insertar((tarea["prioridad"], id_tarea), tarea)

# La deuda del módulo 5: tareas con prioridad entre 1 y 3
urgentes = por_prioridad.rango((1, 0), (3, float("inf")))
for (prio, id_t), tarea in urgentes:
    print(prio, id_t, tarea["titulo"])
# 1 6  Revisar login
# 1 8  Migrar datos
# 2 3  Arreglar CSS
# ...ordenadas por (prioridad, id), de la 1 a la 3

Los extremos (1, 0) y (3, float("inf")) acotan "cualquier id con prioridad 1" por abajo y "cualquier id con prioridad 3" por arriba. Consulta respondida, ordenada de propina, y podando todo lo que no toca. Esta es la fila de la tabla de 06-01 que quedaba en blanco.

El coste es O(altura): la demo del árbol degenerado

Todo lo anterior cuesta O(altura) y hemos ido insinuando que la altura puede traicionarnos. Toca provocar el desastre. ¿Qué pasa si las claves llegan ya ordenadas — el caso más natural del mundo: ids autoincrementales, tareas creadas en orden?

secuencial = ArbolBusqueda()
for i in range(1, 8):
    secuencial.insertar(i, f"tarea {i}")

Cada clave nueva es mayor que todas las anteriores, así que siempre baja por la derecha:

graph TD
    A((1)) --> B((2))
    B --> C((3))
    C --> D((4))
    D --> E((5))
    E --> F((6))
    F --> G((7))

El árbol degenerado de 06-02: una lista enlazada con nombre de árbol. Altura n−1, y toda la tabla de costes se hunde:

Operación ABB equilibrado ABB degenerado
buscar O(log n) O(n)
insertar O(log n) O(n)
borrar O(log n) O(n)
minimo / maximo O(log n) O(n)

Midámoslo con timeit, como en el módulo 1 — construir el índice con 2 000 ids ordenados frente a los mismos ids desordenados:

import timeit, random, sys
sys.setrecursionlimit(10000)     # en_orden recursivo sobre árbol degenerado lo necesita

ids = list(range(2000))
desordenados = ids[:]
random.shuffle(desordenados)

def construir(claves):
    a = ArbolBusqueda()
    for c in claves:
        a.insertar(c, None)
    return a

print(timeit.timeit(lambda: construir(ids), number=5))          # ~4 s   (¡O(n²) total!)
print(timeit.timeit(lambda: construir(desordenados), number=5)) # ~0.03 s (O(n log n))

(Los tiempos exactos dependen de tu máquina; la proporción — dos órdenes de magnitud — no.) Con claves aleatorias, el ABB queda razonablemente equilibrado en promedio y las 2 000 inserciones cuestan O(n log n) en total; con claves ordenadas, la inserción i-ésima recorre i nodos y el total es O(n²). Y la ironía es cruel: el caso de uso más habitual (ids autoincrementales) es exactamente el peor caso del ABB. Un índice que se degrada justo con los datos que más va a recibir no es un índice serio. La solución — un árbol que se reequilibra solo en cada inserción — es la próxima lección.

dict vs ABB: cada uno a lo suyo

Con los dos índices construidos, la comparación honesta (asumiendo ABB equilibrado; n elementos, k resultados):

Operación dict / TablaHash ABB
Buscar clave exacta O(1) O(log n)
Insertar / borrar O(1) O(log n)
Recorrer en orden O(n log n) (hay que ordenar) O(n) (inorden)
Mínimo / máximo O(n) O(log n)
Rango [a, b] O(n) (recorrer todo y filtrar) O(altura + k)
Requisito sobre claves hashables comparables entre sí

La lectura correcta no es "cuál gana" sino "para qué pregunta": clave exacta → hash; orden, extremos y rangos → árbol. Los sistemas reales usan ambos a la vez — TaskFlow también: la TablaHash de 05-02 para obtener(id) en O(1), y este ABB para listados y rangos. Es la misma decisión que toma una base de datos al elegir entre un índice hash y un índice de árbol (lo veremos de cerca en 06-06).

Errores Comunes y Consejos

  • Validar la propiedad ABB comparando solo con el padre. Un nodo debe respetar a todos sus ancestros, no solo al inmediato. El validador correcto propaga cotas (mínimo, máximo) al descender — es el ejercicio estrella de 06-08.
  • Borrar el caso de dos hijos "a lo bruto". Sustituir por un hijo cualquiera rompe la propiedad. El sustituto tiene que ser el sucesor (mínimo del subárbol derecho) o el predecesor (máximo del izquierdo) — solo ellos encajan entre ambos subárboles.
  • Olvidar reasignar al llamar a _borrar. El patrón nodo.izquierdo = self._borrar(nodo.izquierdo, clave) funciona porque cada llamada devuelve la nueva raíz del subárbol. Llamar sin asignar deja el árbol intacto y el bug es silencioso.
  • Claves no comparables entre sí. Mezclar int y str como claves explota (TypeError al comparar). Y con claves compuestas, cuida el orden de la tupla: (prioridad, id) ordena por prioridad primero; (id, prioridad) es otro índice distinto.
  • Asumir que "en promedio se equilibra". Cierto con claves aleatorias, falso con claves ordenadas o casi ordenadas — que es lo que producen los sistemas reales (ids, timestamps). No confíes en la suerte: 06-05 existe por esto.

Ejercicios

Ejercicio 1: contiene y el sucesor de una clave

Añade a ArbolBusqueda (a) contiene(clave) que devuelva True/False, y (b) sucesor(clave) que devuelva la menor clave del árbol estrictamente mayor que la dada (exista o no la dada en el árbol), o None. Con el índice de la lección (tras borrar el 10): sucesor(8) → 12, sucesor(9) → 12, sucesor(20) → None.

Ejercicio 2: las tareas pendientes del rango

Usando por_prioridad y rango, escribe urgentes_pendientes(arbol, prio_max) que devuelva los títulos de las tareas con prioridad entre 1 y prio_max cuyo estado sea "pendiente", ordenados por (prioridad, id). El filtro de estado se aplica sobre el resultado del rango (el árbol indexa por prioridad, no por estado — un índice por consulta).

Ejercicio 3: ¿cuánto mide mi árbol?

Escribe altura_abb(arbol) (reutiliza la altura de 06-02 sobre arbol.raiz) y compárala en dos índices de 1 023 claves: uno construido con claves ordenadas range(1023) y otro con las mismas barajadas. ¿Qué altura mínima era posible? Relaciona los tres números.

Soluciones

Solución 1

    def contiene(self, clave):
        # No basta "buscar(clave) is not None": un valor podría SER None.
        nodo = self.raiz
        while nodo is not None:
            if clave == nodo.clave:
                return True
            nodo = nodo.izquierdo if clave < nodo.clave else nodo.derecho
        return False

    def sucesor(self, clave):
        candidato = None
        nodo = self.raiz
        while nodo is not None:
            if nodo.clave > clave:
                candidato = nodo.clave      # sirve, pero quizá haya uno menor...
                nodo = nodo.izquierdo       # ...busquémoslo a la izquierda
            else:
                nodo = nodo.derecho         # demasiado pequeño: a la derecha
        return candidato

print(indice.sucesor(9))    # 12
print(indice.sucesor(20))   # None

Comentario: sucesor es el patrón "mejor candidato hasta ahora": cada nodo mayor que la clave se apunta como candidato y se intenta mejorar bajando a la izquierda; los nodos menores o iguales se descartan bajando a la derecha. Un solo descenso, O(altura), y sin necesitar que la clave exista. La pega sutil de contiene está en el comentario: en el índice guardamos alguna tarea como None en la demo, y buscar no distingue "no está" de "está y vale None" — el mismo matiz que resolvía in frente a get en el dict.

Solución 2

def urgentes_pendientes(arbol, prio_max):
    resultado = []
    for (prio, id_t), tarea in arbol.rango((1, 0), (prio_max, float("inf"))):
        if tarea["estado"] == "pendiente":
            resultado.append(tarea["titulo"])
    return resultado

print(urgentes_pendientes(por_prioridad, 2))
# ['Arreglar CSS', 'Desplegar API', 'Optimizar consultas']
# (las de prioridad 1 estaban "en curso" y "bloqueada": filtradas)

Comentario: el árbol hace el trabajo grueso (acotar y ordenar, O(altura + k)) y el filtro fino va después en Python, O(k). Es la arquitectura de cualquier consulta real: el índice reduce el universo, el resto se filtra. Indexar por todas las combinaciones posibles no compensa; se indexa la dimensión más selectiva.

Solución 3

import random

def altura_nodo(nodo):
    if nodo is None:
        return -1
    return 1 + max(altura_nodo(nodo.izquierdo), altura_nodo(nodo.derecho))

def altura_abb(arbol):
    return altura_nodo(arbol.raiz)

claves = list(range(1023))
ordenado = construir(claves)
barajadas = claves[:]
random.shuffle(barajadas)
aleatorio = construir(barajadas)

print(altura_abb(ordenado))    # 1022  (degenerado: una clave por nivel)
print(altura_abb(aleatorio))   # ~20-24 (varía con la baraja)

Comentario: la altura mínima posible con 1 023 = 2¹⁰ − 1 nodos es 9 (el árbol perfecto de 10 niveles, tabla de 06-02). El aleatorio queda en ~20: no es perfecto, pero sigue siendo O(log n) — la teoría dice que el ABB aleatorio promedia ≈ 1,39·log₂ n... ¡pero ninguna garantía cubre el caso ordenado, que da 1022! Tres números, tres mundos: el ideal (9), el probable (≈20) y el catastrófico (1022). La próxima lección garantiza quedarse a un paso del ideal, llegue lo que llegue.

Conclusión

El ABB ha saldado las cuentas pendientes: con una sola regla — menores a la izquierda, mayores a la derecha — TaskFlow tiene un índice que busca en O(altura), lista en orden con el inorden (el misterio de 06-03, resuelto), encuentra mínimo y sucesor de un vistazo y responde rangos con poda, incluida la consulta "prioridad entre 1 y 3" que humilló al hash, vía la clave compuesta (prioridad, id). También sabes borrar sin romper nada (hoja, un hijo, y el caso del sucesor) y conoces la letra pequeña del contrato: todo es O(altura), y la altura depende del orden de llegada. Con ids autoincrementales — el pan de cada día — el ABB degenera en lista y sus O(log n) se evaporan, como acabas de medir. La próxima lección arregla esto de raíz: el árbol AVL detecta el desequilibrio en cada inserción con un número por nodo y lo corrige con rotaciones locales, garantizando O(log n) pase lo que pase. El índice de TaskFlow está a una lección de volverse indestructible.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados