Un BST simple puede degenerar en una lista enlazada (operaciones O(n)) si las claves llegan en orden ordenado. BST auto-equilibrados — como AVL y árboles rojo-negro — rotan automáticamente nodos después de inserciones/eliminaciones para mantener la altura ~log n, garantizando operaciones O(log n).
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Árbol AVL | Árbol rojo-negro | |
|---|---|---|
| Rigurosidad del equilibrio | estricta (equilibrada por altura) | más flexible |
| Búsquedas | más rápida (más corta) | un poco más lenta |
| Inserción/eliminación | más rotaciones | menos rotaciones |
| Mejor para | cargas de trabajo de lectura intensiva | cargas de trabajo de escritura intensiva |
| Operación | Tiempo |
|---|---|
| búsqueda | O(log n) |
| inserción | O(log n) |
| eliminación | O(log n) |
Ambos mantienen el equilibrio mediante rotaciones — reestructuraciones locales O(1) que preservan el ordenamiento del BST y reducen la altura.
Los árboles equilibrados respaldan mapas y conjuntos ordenados en bibliotecas estándar (p. ej., Java TreeMap, C++ std::map utilizan árboles rojo-negro), proporcionando iteración ordenada más operaciones logarítmicas garantizadas.
Son la respuesta cuando necesitas el ordenamiento de un BST y una garantía de rendimiento sólida contra entrada adversarial.