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

Árboles Binarios

Siguiente ►
►

En la lección anterior construimos árboles genéricos donde cada nodo puede tener cualquier número de hijos: perfectos para jerarquías libres como la de TaskFlow, pero sin propiedades matemáticas fuertes que explotar. Esta lección restringe el árbol a como máximo dos hijos por nodo, con posiciones distinguidas (izquierdo y derecho), y esa restricción tan simple abre la puerta a casi todo lo que queda de módulo: sobre los árboles binarios se construyen los árboles de búsqueda (06-04), los AVL (06-05) y los montículos (06-07). Aquí aprenderás la clase NodoBinario, los tipos de árbol binario (lleno, completo, perfecto, degenerado), las cuentas que relacionan nodos y altura — la clave de por qué "O(log n)" aparecerá tantas veces — y una representación sorprendente: un árbol completo guardado en un array plano.

Contenido

  1. Definición: dos hijos, con nombre y apellido
  2. La clase NodoBinario
  3. Tipos de árboles binarios: lleno, completo, perfecto y degenerado
  4. Las cuentas del árbol binario: nodos, niveles y altura
  5. Representación en array de un árbol completo
  6. TaskFlow: un árbol binario de decisión para clasificar tareas

Definición: dos hijos, con nombre y apellido

Un árbol binario es un árbol en el que cada nodo tiene como máximo dos hijos, y — detalle crucial — cada hijo ocupa una posición con nombre propio: hijo izquierdo o hijo derecho. No es lo mismo un nodo con un solo hijo izquierdo que con un solo hijo derecho: son árboles binarios distintos.

graph TD
    subgraph "Árbol A"
        A1((5)) --> B1((3))
        A1 -.x.-> C1(( ))
    end
    subgraph "Árbol B (distinto de A)"
        A2((5)) -.x.-> B2(( ))
        A2 --> C2((3))
    end

En el árbol genérico, hijos = [x] era simplemente "un hijo". Aquí la posición importa, y ese matiz será oro puro en 06-04: "izquierda = menores, derecha = mayores" solo tiene sentido si izquierda y derecha existen como conceptos separados.

La clase NodoBinario

En lugar de una lista de hijos, dos referencias con nombre — el mismo salto que dimos del Nodo al NodoDoble en el módulo 2, pero con otro significado: allí anterior/siguiente encadenaban en línea; aquí izquierdo/derecho ramifican.

class NodoBinario:
    """Un nodo de árbol binario: valor y dos hijos con posición."""

    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None    # subárbol izquierdo (None = no hay)
        self.derecho = None      # subárbol derecho  (None = no hay)

Y ya está: no necesita más métodos, porque los hijos se asignan directamente. Construyamos a mano el primer árbol:

graph TD
    R((10)) --> I((6))
    R --> D((15))
    I --> II((3))
    I --> ID((8))
    D --> DI((12))
raiz = NodoBinario(10)
raiz.izquierdo = NodoBinario(6)
raiz.derecho = NodoBinario(15)
raiz.izquierdo.izquierdo = NodoBinario(3)
raiz.izquierdo.derecho = NodoBinario(8)
raiz.derecho.izquierdo = NodoBinario(12)

La definición recursiva de la lección anterior se afina: un árbol binario es vacío (None), o un nodo con un árbol binario izquierdo y un árbol binario derecho. De ahí que las funciones sobre árboles binarios tengan casi siempre esta silueta:

def contar(nodo):
    if nodo is None:                                   # árbol vacío
        return 0
    return 1 + contar(nodo.izquierdo) + contar(nodo.derecho)

def altura(nodo):
    """Altura del subárbol. Convención: árbol vacío = -1, hoja = 0."""
    if nodo is None:
        return -1
    return 1 + max(altura(nodo.izquierdo), altura(nodo.derecho))

print(contar(raiz))   # 6
print(altura(raiz))   # 2

Detalle de altura: devolver -1 para el árbol vacío hace que la cuenta cuadre sola — una hoja tiene dos hijos None de altura -1, así que su altura es 1 + max(-1, -1) = 0, como debe ser. Y max porque la altura la marca el camino más largo hacia una hoja.

Tipos de árboles binarios: lleno, completo, perfecto y degenerado

No todos los árboles binarios con los mismos nodos tienen la misma forma, y la forma determina el rendimiento. Los cuatro nombres que hay que conocer:

Tipo Definición Idea visual
Lleno (full) Cada nodo tiene 0 o 2 hijos (nunca exactamente 1) Sin "brazos a medias"
Completo (complete) Todos los niveles llenos salvo quizá el último, que se rellena de izquierda a derecha sin huecos Se llena como un teatro por filas
Perfecto Todos los niveles completamente llenos (todas las hojas a la misma profundidad) El triángulo ideal
Degenerado Cada nodo tiene un solo hijo: el árbol es una cadena Una lista enlazada disfrazada 
graph TD
    subgraph "Lleno"
        L1((A)) --> L2((B))
        L1 --> L3((C))
        L2 --> L4((D))
        L2 --> L5((E))
    end
    subgraph "Completo"
        C1((A)) --> C2((B))
        C1 --> C3((C))
        C2 --> C4((D))
        C2 --> C5((E))
        C3 --> C6((F))
    end
graph TD
    subgraph "Perfecto"
        P1((A)) --> P2((B))
        P1 --> P3((C))
        P2 --> P4((D))
        P2 --> P5((E))
        P3 --> P6((F))
        P3 --> P7((G))
    end
    subgraph "Degenerado"
        D1((A)) --> D2((B))
        D2 --> D3((C))
        D3 --> D4((D))
    end

Observaciones que conviene interiorizar:

  • Todo árbol perfecto es completo y lleno; las categorías se solapan.
  • El completo — llenar por niveles y de izquierda a derecha, sin huecos — parece una definición caprichosa, pero es exactamente la forma que permite la representación en array de la sección 5, y por eso es la forma de los montículos de 06-07.
  • El degenerado es la pesadilla: estructuralmente es una lista enlazada del módulo 2, con coste O(n) para llegar al final. En 06-04 veremos lo fácil que es crear uno sin querer, y 06-05 existe para impedirlo.

Las cuentas del árbol binario: nodos, niveles y altura

Tres hechos numéricos, todos derivados de "cada nodo tiene como máximo 2 hijos":

  • Nivel k tiene como máximo 2^k nodos: 1 en el nivel 0 (la raíz), 2 en el 1, 4 en el 2, 8 en el 3... Cada nivel puede duplicar al anterior. (¿Te suena? En el módulo 4, el ejercicio binarios_hasta(n) generaba "1, 10, 11, 100..." con una cola: estabas recorriendo por niveles un árbol binario perfecto sin saberlo. En 06-03 cerraremos ese círculo.)
  • Un árbol de altura h tiene como máximo 2^(h+1) − 1 nodos: la suma 1 + 2 + 4 + ... + 2^h. Un árbol perfecto de altura 10 alberga 2 047 nodos; de altura 20, más de dos millones.
  • Al revés — y esta es la cuenta importante — un árbol con n nodos tiene altura mínima ⌊log₂ n⌋: para guardar n nodos necesitas al menos log₂(n) niveles, porque menos niveles no dan capacidad suficiente. Y altura máxima n − 1 (el degenerado).
n nodos Altura mínima (equilibrado) Altura máxima (degenerado)
7 2 6
1 000 9 999
1 000 000 19 999 999

Esta tabla es el mapa del resto del módulo. Casi todas las operaciones que veremos (buscar en 06-04, insertar/extraer en 06-07) cuestan O(altura): caminan de la raíz hacia abajo, un nodo por nivel. Si el árbol está equilibrado, altura ≈ log₂ n y la operación es logarítmica — 20 pasos para un millón de elementos, la misma magia que la búsqueda binaria del módulo 1. Si está degenerado, altura ≈ n y volvemos al O(n) de la lista enlazada. Toda la batalla de 06-04 y 06-05 es mantener la altura logarítmica.

Representación en array de un árbol completo

Sorpresa: un árbol binario completo no necesita nodos ni referencias — cabe en una lista de Python. Se numeran los nodos por niveles, de izquierda a derecha, empezando en 0, y ese número es su índice en el array:

graph TD
    A["10 (i=0)"] --> B["6 (i=1)"]
    A --> C["15 (i=2)"]
    B --> D["3 (i=3)"]
    B --> E["8 (i=4)"]
    C --> F["12 (i=5)"]
arbol = [10, 6, 15, 3, 8, 12]

La aritmética que sustituye a las referencias — apréndetela, porque es el corazón del montículo de 06-07:

Desde el nodo en el índice i Fórmula
Hijo izquierdo 2*i + 1
Hijo derecho 2*i + 2
Padre (i - 1) // 2 
def hijo_izquierdo(arbol, i):
    j = 2 * i + 1
    return arbol[j] if j < len(arbol) else None

def hijo_derecho(arbol, i):
    j = 2 * i + 2
    return arbol[j] if j < len(arbol) else None

def padre(arbol, i):
    return arbol[(i - 1) // 2] if i > 0 else None

print(hijo_izquierdo(arbol, 0))  # 6   (hijos de 10: índices 1 y 2)
print(hijo_derecho(arbol, 1))    # 8   (hijos de 6: índices 3 y 4)
print(padre(arbol, 5))           # 15  ((5-1)//2 = 2)

Comprueba las fórmulas con el diagrama: los hijos del índice 1 son 3 y 4; los del 2 son 5 y 6. Ventajas de esta representación: cero memoria en referencias (compara con los dos punteros por nodo de NodoBinario), datos contiguos en memoria (la localidad de caché de 01-05), y navegación padre↔hijo con una división. La letra pequeña: solo funciona sin huecos, es decir, con árboles completos. Si el árbol tuviera un hueco intermedio habría que rellenar con None y desperdiciar posiciones — en un degenerado de 20 nodos, más de un millón de huecos. Por eso el montículo de 06-07 se mantiene siempre completo: para vivir en un array.

TaskFlow: un árbol binario de decisión para clasificar tareas

¿Dónde encaja un árbol binario en TaskFlow, más allá de preparar 06-04? En un árbol de decisión: cada nodo interno es una pregunta de sí/no, izquierda = no, derecha = sí, y las hojas son veredictos. Clasifiquemos tareas entrantes:

graph TD
    A{"¿prioridad == 1?"} -->|no| B{"¿estado == bloqueada?"}
    A -->|sí| C{"¿estado == bloqueada?"}
    B -->|no| D["Bandeja normal"]
    B -->|sí| E["Revisar dependencias"]
    C -->|no| F["¡Atender YA!"]
    C -->|sí| G["Escalar al responsable"]
def hacer_pregunta(texto_pregunta, condicion):
    """Nodo interno: guarda la pregunta y la función que la evalúa."""
    nodo = NodoBinario(texto_pregunta)
    nodo.condicion = condicion       # función tarea -> bool
    return nodo

# Hojas: el veredicto es el valor
bandeja  = NodoBinario("Bandeja normal")
revisar  = NodoBinario("Revisar dependencias")
atender  = NodoBinario("¡Atender YA!")
escalar  = NodoBinario("Escalar al responsable")

# Nodos internos (convención: izquierdo = no, derecho = sí)
urgente = hacer_pregunta("¿prioridad == 1?", lambda t: t["prioridad"] == 1)
bloq_no_urg = hacer_pregunta("¿bloqueada?", lambda t: t["estado"] == "bloqueada")
bloq_urg    = hacer_pregunta("¿bloqueada?", lambda t: t["estado"] == "bloqueada")

urgente.izquierdo, urgente.derecho = bloq_no_urg, bloq_urg
bloq_no_urg.izquierdo, bloq_no_urg.derecho = bandeja, revisar
bloq_urg.izquierdo, bloq_urg.derecho = atender, escalar

def clasificar(nodo, tarea):
    """Baja por el árbol respondiendo preguntas hasta llegar a una hoja."""
    while nodo.izquierdo is not None:          # las hojas no tienen hijos
        if nodo.condicion(tarea):
            nodo = nodo.derecho                # sí -> derecha
        else:
            nodo = nodo.izquierdo              # no -> izquierda
    return nodo.valor

t1 = {"id": "T-07", "titulo": "Caída del servidor", "prioridad": 1, "estado": "pendiente"}
t2 = {"id": "T-08", "titulo": "Actualizar logo", "prioridad": 3, "estado": "bloqueada"}
print(clasificar(urgente, t1))   # ¡Atender YA!
print(clasificar(urgente, t2))   # Revisar dependencias

Fíjate en dos cosas. Primera: clasificar es iterativa y O(altura) — responde una pregunta por nivel y desciende; con el árbol equilibrado, clasificar entre 2^h veredictos cuesta solo h preguntas. Segunda: el patrón "comparar en el nodo y elegir izquierda o derecha" que acabas de escribir es, gesto a gesto, el mismo con el que buscaremos en el ABB de 06-04 — solo cambiará la pregunta (¿mi clave es menor que la tuya?).

Errores Comunes y Consejos

  • Tratar izquierdo y derecho como intercambiables. Un nodo con solo hijo izquierdo y otro con solo hijo derecho son árboles distintos. A partir de 06-04, confundirlos rompe directamente la corrección.
  • Confundir "lleno" y "completo". Son traducciones traicioneras de full y complete, y ni siquiera la literatura en inglés es siempre consistente. Quédate con las definiciones de la tabla; en este curso "completo" siempre significa "sin huecos, rellenado por niveles de izquierda a derecha" — la forma del heap.
  • Usar la representación en array con árboles no completos. Las fórmulas 2i+1/2i+2 presuponen que no hay huecos. Con un árbol arbitrario tendrías que insertar None de relleno, y en el peor caso (degenerado) el array crece exponencialmente respecto a los nodos reales.
  • Descuidar la convención de altura del árbol vacío. Hay textos donde la hoja tiene altura 1 y el vacío 0 (cuentan nodos en vez de aristas). Cualquiera de las dos funciona si eres consistente; en este curso: vacío = −1, hoja = 0.
  • Consejo: cuando dudes de una fórmula de índices, dibuja un árbol de 6-7 nodos, numéralo por niveles y compruébala a mano en 30 segundos. Es infinitamente mejor que memorizar.

Ejercicios

Ejercicio 1: ¿es un árbol lleno?

Escribe es_lleno(nodo) que devuelva True si cada nodo del árbol tiene 0 o 2 hijos. Pruébala con el árbol de la sección 2 (que no es lleno: el 15 tiene un solo hijo) y con el árbol de decisión de TaskFlow (que sí lo es).

Ejercicio 2: del array al recuento de hojas, sin construir nodos

Dado un árbol completo en representación de array, escribe hojas_array(arbol) que devuelva la lista de valores de sus hojas usando solo las fórmulas de índices (un nodo es hoja si su hijo izquierdo caería fuera del array). Para [10, 6, 15, 3, 8, 12] debe devolver [3, 8, 12].

Ejercicio 3: mínimos niveles para las tareas de TaskFlow

Sin ejecutar código: TaskFlow gestiona 5 000 tareas y quieres guardarlas en un árbol binario. (a) ¿Cuál es la altura mínima posible del árbol? (b) ¿Y la máxima? (c) Si una operación cuesta O(altura), ¿cuántos pasos son en cada caso? Después comprueba (a) con una línea de Python.

Soluciones

Solución 1

def es_lleno(nodo):
    if nodo is None:
        return True                                   # el vacío cumple trivialmente
    if (nodo.izquierdo is None) != (nodo.derecho is None):
        return False                                  # exactamente un hijo: no es lleno
    return es_lleno(nodo.izquierdo) and es_lleno(nodo.derecho)

print(es_lleno(raiz))      # False (el 15 solo tiene hijo izquierdo)
print(es_lleno(urgente))   # True  (el árbol de decisión)

Comentario: la línea clave usa != entre dos booleanos como "o exclusivo": es False cuando ambos hijos existen o ambos faltan, y True (→ no lleno) cuando hay exactamente uno. Y el and final corta en cuanto un subárbol falla. Nota de diseño: en un árbol de decisión ser lleno no es casualidad — una pregunta con una sola respuesta posible no sería una pregunta.

Solución 2

def hojas_array(arbol):
    resultado = []
    for i in range(len(arbol)):
        if 2 * i + 1 >= len(arbol):      # sin hijo izquierdo => sin hijos => hoja
            resultado.append(arbol[i])
    return resultado

print(hojas_array([10, 6, 15, 3, 8, 12]))   # [3, 8, 12]

Comentario: en un árbol completo no puede existir hijo derecho sin izquierdo (el último nivel se rellena de izquierda a derecha), así que basta comprobar 2i+1. Bonus que puedes verificar: la primera hoja está siempre en el índice len(arbol) // 2 — en un array de 6 elementos, los índices 0, 1 y 2 son internos y 3, 4 y 5 son hojas. El heapify de 06-07 explotará exactamente este hecho.

Solución 3

(a) La altura mínima es ⌊log₂ 5000⌋ = 12 (2¹³ − 1 = 8 191 ≥ 5 000 nodos caben en 13 niveles, y 2¹² − 1 = 4 095 < 5 000 demuestran que 12 niveles no bastan). (b) La máxima es 4 999: el árbol degenerado, una tarea colgando de otra. (c) O(altura) significa unos 12 pasos en el árbol equilibrado frente a hasta 4 999 en el degenerado — más de 400 veces peor con los mismos datos.

import math
print(math.floor(math.log2(5000)))   # 12

Comentario: esta diferencia no es teórica: en 06-04 la provocaremos con código real (insertando ids ya ordenados) y en 06-05 la mediremos. Guarda estos números en la cabeza.

Conclusión

El árbol binario añade a la jerarquía de 06-01 una disciplina: dos hijos como máximo, cada uno con posición propia. De esa disciplina has sacado la clase NodoBinario, la taxonomía de formas (lleno, completo, perfecto, degenerado), las cuentas que atan nodos y altura — con la conclusión central del módulo: operación O(altura) + árbol equilibrado = O(log n); árbol degenerado = O(n) — y la representación en array con índices 2i+1/2i+2 que reaparecerá en el montículo de 06-07. También has escrito tu primer descenso comparando en cada nodo, con el árbol de decisión de TaskFlow. Pero hasta ahora hemos visitado los nodos un poco "a demanda", sin método. La siguiente lección pone orden: los cuatro recorridos sistemáticos de un árbol — preorden, inorden, postorden y por niveles — que son a los árboles lo que el bucle for es a las listas, y donde por fin la cola del módulo 4 y aquel ejercicio binarios_hasta mostrarán su verdadera cara.

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