Lecciones · #10 de 11

Árboles Balanceados

Las rotaciones mantienen la altura ≈ log n, sin importar el orden de inserción

AVL tree · self-balancing rotations

size0

avl height0

naïve bst h.0

init

value

Pruébalo: Presiona insertar 1..15 para forzar una secuencia degenerada. La altura del ABB ingenuo salta a 15; la altura del AVL se mantiene en 4 — porque cada desbalance dispara una rotación, destellada en el lienzo.

Por qué importa

Los ABB normales pueden degradarse a O(n). Los árboles balanceados garantizan O(log n) reequilibrándose automáticamente tras inserciones y eliminaciones. Los árboles AVL y rojo-negro son los caballos de batalla detrás de la mayoría de las bibliotecas estándar de los lenguajes.

La idea

¿Recuerdas cómo un ABB puede convertirse en una lista enlazada si insertas datos ordenados? Los árboles balanceados evitan esto reestructurándose tras las operaciones.

Árboles AVL: Después de cada inserción/eliminación, comprueba si los subárboles de algún nodo difieren en altura por más de 1. Si es así, rota para corregirlo.

Las rotaciones son el movimiento mágico:

Rotación derecha: Cuando el subárbol izquierdo es demasiado alto
Rotación izquierda: Cuando el subárbol derecho es demasiado alto
Rotaciones dobles: Para los casos en zigzag

El resultado: la altura es siempre O(log n), así que todas las operaciones se mantienen garantizadas en O(log n).

Árboles rojo-negro usan un truco distinto: colorean los nodos de rojo o negro con reglas que limitan cuánto puede desequilibrarse el árbol. Menos estrictamente balanceados que los AVL, pero con menos rotaciones en promedio.

Puntos clave

Garantizan operaciones O(log n) sin importar el orden de inserción
Las rotaciones son operaciones O(1) que preservan la propiedad del ABB
AVL: balance más estricto (diferencia de altura ≤ 1)
Rojo-negro: balance más laxo, menos rotaciones

Invariantes

Estos árboles heredan el invariante del ABB y añaden una regla de balance encima. La regla de balance es lo que garantiza la altura O(log n).

Invariante AVL: Para cada nodo, |height(left) − height(right)| ≤ 1. Se impone estrictamente después de cada inserción y eliminación mediante rotaciones.; Consecuencia: altura h < 1.44 · log₂(n + 2) — dentro del 44% del mínimo teórico.
Invariantes rojo-negro — los cuatro deben cumplirse: 1. Cada nodo está coloreado de rojo o de negro.; 2. La raíz es negra. (A veces se enuncia: las hojas — los centinelas NULL — también son negras.); 3. Un nodo rojo solo tiene hijos negros. (No hay dos rojos seguidos a lo largo de ningún camino raíz-a-hoja.); 4. Todo camino de la raíz a un NULL pasa por el mismo número de nodos negros. Esta es la altura negra; es el invariante estructural que acota la altura del árbol.; Consecuencia: altura h ≤ 2 · log₂(n + 1). Más laxo que AVL pero más fácil de mantener.

Profundizando

AVL vs rojo-negro — cuál elegir

| Propiedad | AVL | Rojo-negro | |---|---|---| | Altura en el peor caso | ≤ 1.44 log₂ n | ≤ 2 log₂ n | | Rotaciones por inserción | hasta 2 | hasta 2 | | Rotaciones por eliminación | hasta O(log n) | hasta 3 | | Velocidad de búsqueda | ligeramente más rápida (más balanceado) | ligeramente más lenta | | Velocidad de inserción/eliminación | más lenta | más rápida | | Memoria por nodo | 1–2 bits (factor de balance) | 1 bit (color) | | Uso típico | bases de datos, con muchas lecturas | stdlib del lenguaje std::map, TreeMap, rbtree.h del kernel de Linux |

Regla práctica: si lees mucho más de lo que escribes, AVL. Si tu carga de trabajo es mixta o con muchas escrituras, rojo-negro. El std::map de C++, el TreeMap de Java y el planificador de procesos del kernel de Linux usan todos rojo-negro por esta razón.

Árboles B — la generalización a la página de disco

Un árbol B generaliza el ABB en una dirección: cada nodo contiene muchas claves (digamos de 100 a 1000), no solo una. Un nodo tiene k + 1 hijos si tiene k claves, y los rangos de clave de los hijos se intercalan con las claves del padre (a la izquierda de clave₀ → hijo₀, entre clave₀ y clave₁ → hijo₁, …).

¿Por qué tantas claves por nodo? Las búsquedas en disco. En un disco giratorio, leer 1 byte y leer 16 KB toma esencialmente el mismo tiempo — el costo es el movimiento del cabezal, no los bytes transferidos. Los motores de bases de datos llenan cada nodo del árbol B para que ocupe exactamente una página de disco (típicamente 4 KB o 16 KB). Una lectura de disco trae ~256–1024 claves de golpe, así que navegar una base de datos de miles de millones de filas toma solo 3–4 lecturas de página. La misma lógica aplica a los SSD (donde el costo de búsqueda lo domina la E/S alineada a páginas) y a los inodos del sistema de archivos.

Todo índice de base de datos relacional, todo sistema de archivos moderno (ext4, NTFS, APFS, XFS) y la mayoría de los almacenes clave-valor (RocksDB, LevelDB) usan árboles B o su primo cercano, el árbol B+ (donde los nodos hoja forman una lista enlazada para escaneos de rango rápidos). Los árboles B son la razón por la que SELECT * WHERE id BETWEEN 1000 AND 2000 toma menos de un milisegundo en una tabla de mil millones de filas.

Números de costo del mundo real

Para un árbol balanceado de n = 1,000,000 claves:

Búsqueda: ~20 comparaciones (log₂ 1M ≈ 20)
Memoria: ~24 MB (suponiendo 24 B por nodo — 3 punteros + clave de 4 bytes)

Compáralo con un arreglo ordenado por clave:

Búsqueda: ~20 comparaciones (búsqueda binaria, el mismo log₂ n)
Memoria: ~4 MB (solo las claves, sin punteros)
Inserción: O(n) — desplazamiento del arreglo

Así que si tu conjunto de datos es de solo lectura y cabe en memoria, un arreglo ordenado le gana a un árbol balanceado tanto en velocidad (localidad de caché) como en memoria. Los árboles balanceados pagan su sobrecarga para mantener inserciones en O(log n).

Detalles matemáticos

Factor de balance AVL: BF(n) = height(n.left) - height(n.right); Must be in 1
Complejidad temporal (garantizada): Search: O(log n); Insert: O(log n); Delete: O(log n)
Cotas de altura: AVL: h < 1.44 log_2(n+2); Red-Black: h leq 2 log_2(n+1)

Implementación

Concepto de rotación

// Rotación derecha cuando el subárbol izquierdo es demasiado alto
//       y                x
//      / \              / \
//     x   C   --->     A   y
//    / \                  / \
//   A   B                B   C

fn rotate_right(y: Node) -> Node {
    let x = y.left.take();
    y.left = x.right;
    x.right = Some(y);
    x
}

Cuándo usarlos

Necesitas rendimiento O(log n) garantizado
Los datos llegan en orden ordenado/casi ordenado
Implementar mapas, conjuntos, colas de prioridad
Índices de bases de datos

Práctica

La verificación que acompaña a toda implementación de árbol auto-balanceado:

¿Está balanceado en altura un árbol binario? — fácil · la pasada postorden O(n) con salida temprana basada en centinela; lo que afirmas después de cada rotación AVL / rojo-negro

→ Explora todos los problemas de práctica

⚖️ Árboles Balanceados