Los árboles AVL y Red-Black mantienen altura O(log n), pero lo logran con filosofías distintas: AVL prioriza el balance estricto, mientras que Red-Black acepta desbalance moderado a cambio de menos rotaciones promedio.
11.1 Balanceo estricto vs moderado
- AVL: diferencia de alturas entre subárboles máximo de 1 en cada nodo; altura más baja y búsquedas algo más predecibles.
- Red-Black: solo garantiza black-height uniforme; la altura puede ser hasta el doble de log2(n+1) pero sigue siendo
O(log n).
Si el foco es minimizar la altura a toda costa (por ejemplo, rutas de memoria largas que afectan la caché), AVL es preferible. Cuando se prioriza simplicidad en rebalanceo y pocas actualizaciones, Red-Black ofrece buenas garantías con menos disciplina de altura.
11.2 Rotaciones
- AVL: rotaciones frecuentes en inserciones y eliminaciones; hasta dos rotaciones por operación (casos dobles).
- Red-Black: inserción suele requerir 0 o 1 rotación; eliminación puede requerir más, pero a menudo solo recoloreo.
En cargas de escritura intensa, la menor cantidad de rotaciones de Red-Black reduce bloqueos y contención. En AVL, las rotaciones adicionales se compensan con nodos más cortos y caminos de lectura más uniformes.
11.3 Rendimiento en búsqueda
- AVL: ventaja ligera por altura más baja; recomendable para cargas dominadas por lecturas.
- Red-Black: altura mayor pero todavía logarítmica; impacto práctico pequeño salvo en lecturas ultra sensibles.
En la práctica, la diferencia puede ser marginal si el conjunto cabe en caché. En datos grandes, la altura extra de Red-Black puede traducirse en 1 o 2 accesos de memoria adicionales por búsqueda.
11.4 Rendimiento en inserción/eliminación
- AVL: más rotaciones en promedio; escritura ligeramente más costosa pero con buen acceso posterior.
- Red-Black: menos rotaciones promedio en inserción; eliminación puede ser más compleja pero con recoloreos frecuentes.
En sistemas con alta concurrencia o con operaciones de lotes, Red-Black tiende a ofrecer menor costo amortizado de actualización. AVL se luce cuando las actualizaciones son menos frecuentes que las lecturas.
11.5 Tabla comparativa
BalanceEstricto (|FB| ≤ 1)Moderado (black-height)
Altura máxima~1.44 log2(n+2)≤ 2 log2(n+1)
Rotaciones en inserciónHasta 20-1 en la mayoría
Rotaciones en eliminaciónHasta 20-3 según casos
Mejor usoLecturas intensivasMixtas lectura/escritura
Memoria extraFactor de balance/altura por nodoColor por nodo
Implementaciones comunesÁrboles en motores geoespaciales o diccionarios en memoriastd::map / std::set, muchos índices de bases de datos
En resumen: usa AVL cuando tu prioridad sea la profundidad mínima y las consultas dominen; elige Red-Black cuando necesites escrituras más baratas y un balanceo suficiente sin apretar tanto la altura.