🌳 Árboles Binarios

init

Pruébalo: Inserta algunos valores. Luego prueba cada recorrido — preorden, inorden, postorden, por niveles — y observa cómo se ilumina el orden de visita debajo del árbol.

Por qué importa

Los árboles son la estructura natural para datos jerárquicos: sistemas de archivos, documentos HTML, organigramas, árboles de decisión. Los árboles binarios son la base de los ABB (árboles binarios de búsqueda), los montículos y el análisis de expresiones.

La idea

Imagina un árbol genealógico, pero donde cada persona tiene como máximo dos hijos (izquierdo y derecho). Comienza desde un único ancestro raíz.

Eso es un árbol binario. Cada nodo tiene como máximo dos hijos.

Los árboles abren nuevas formas de organizar datos:

• Jerarquía: Natural para relaciones padre-hijo
• Recursión: Todo subárbol es en sí mismo un árbol — los problemas se descomponen de manera hermosa
• Múltiples caminos: A diferencia de las estructuras lineales, los árboles se ramifican

Los recorridos visitan los nodos en distintos órdenes:

• Preorden: Procesar el nodo, luego los hijos (serialización)
• Inorden: Hijo izquierdo, nodo, hijo derecho (orden ordenado en un ABB)
• Postorden: Primero los hijos, luego el nodo (eliminación)
• Por niveles: Capa por capa usando una cola (BFS)

Puntos clave

• Cada nodo tiene como máximo 2 hijos (izquierdo y derecho)
• La altura determina la eficiencia — balanceado es O(log n), desbalanceado puede ser O(n)
• Cuatro órdenes de recorrido: preorden, inorden, postorden, por niveles
• Base de los ABB, montículos y árboles de expresiones

Profundizando

Un árbol binario completo llena cada nivel antes de comenzar el siguiente (excepto, posiblemente, el último nivel). Un árbol binario lleno tiene cada nodo con 0 o 2 hijos. Un árbol binario perfecto es a la vez completo y lleno. Estas distinciones importan para las implementaciones de montículos (que requieren ser completos) y para el balanceo de árboles.

La fórmula "máximo de nodos en el nivel k = 2ᵏ" surge por inducción: el nivel 0 tiene un nodo (la raíz); cada nivel tiene a lo sumo el doble del anterior. Sumar la serie geométrica desde el nivel 0 hasta la altura h da un máximo de 2^(h+1) − 1 nodos. Invirtiendo: un árbol balanceado de n nodos tiene altura ⌊log₂ n⌋.

En la práctica

• Sistemas de archivos. Los directorios forman un árbol (con algunos enlaces simbólicos que lo convierten en un DAG). find / no es más que un recorrido de árbol.
• Árboles DOM. Todo documento HTML es un árbol; los selectores CSS y las consultas al DOM son patrones de recorrido. getElementById es una tabla hash montada encima para hacer la búsqueda O(1).
• Grafos de escena en gráficos + robótica. El URDF (Unified Robot Description Format) de un robot es un árbol de eslabones conectados por articulaciones; calcular la pose de una mano en el marco del mundo es una cadena de multiplicaciones de matrices recorriendo desde la hoja hasta la raíz.
• Octrees y árboles KD. Los árboles de subdivisión espacial impulsan la detección de colisiones, la búsqueda del vecino más cercano en nubes de puntos (usada por todo sistema de SLAM) y el trazado de rayos.
• Árboles de expresiones. Todo compilador convierte el código fuente en un AST — un árbol donde los operadores son nodos interiores y los operandos son hojas. El orden de recorrido elige tu estrategia de evaluación.

Detalles matemáticos

Propiedades del árbol

máx. de nodos en el nivel k 2ᵏ

máx. de nodos en el árbol, altura h 2ʰ⁺¹ − 1

altura mínima, n nodos ⌊log₂ n⌋

altura máxima (degenerado) n − 1

Tiempo de recorrido

O(n) — cada nodo se visita exactamente una vez

Espacio

recorrido recursivo O(h) en la pila de llamadas

iterativo (BFS) O(w) donde w es el nivel más ancho

Implementación

Nodo de árbol binario

struct TreeNode<T> {
    data: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

// Recorrido inorden (recursivo)
fn inorder(node: Option<&Box<TreeNode<T>>>) {
    if let Some(n) = node {
        inorder(n.left.as_ref());
        process(n.data);
        inorder(n.right.as_ref());
    }
}

Órdenes de recorrido

• Preorden: Nodo -> Izquierdo -> Derecho
• Inorden: Izquierdo -> Nodo -> Derecho
• Postorden: Izquierdo -> Derecho -> Nodo
• Por niveles: BFS con cola

Práctica

Tres problemas, cada uno enseñando una forma distinta de recursión:

• Profundidad máxima — fácil · recursión simple de dos líneas (1 + max(izquierdo, derecho)); el calentamiento con el que abre toda entrevista sobre árboles
• Recorrido por niveles — medio · el árbol se encuentra con la cola; BFS con el truco de "capturar el tamaño" para recuperar los niveles
• Diámetro de un árbol binario — medio · el patrón de "dos valores por recursión" — retornar la altura, actualizar el mejor como efecto secundario

→ Explora todos los problemas de práctica