Cómo se balancean AVL y árboles rojo-negro

Insertar claves ordenadas puede convertir un árbol de búsqueda en una lista. Para impedirlo, los árboles balanceados detectan ramas demasiado desparejas y reorganizan enlaces sin romper el orden de las claves.

Qué significa balancear, exactamente

Balancear no significa que todos los niveles estén completos. Significa imponer reglas que mantengan la altura en $O(\log n)$. Entonces buscar, insertar y borrar conservan su garantía logarítmica incluso para secuencias de entrada adversas.

La reorganización debe preservar la invariante del ABB. No se cambian claves arbitrariamente: se cambia qué nodo ocupa la raíz local y cómo se conectan sus subárboles.

La rotación, el único movimiento que hay

Una rotación derecha eleva al hijo izquierdo y baja la raíz hacia la derecha. Una rotación izquierda hace el movimiento simétrico. Ambas mantienen el recorrido inorden, por lo que conservan el conjunto de claves ordenado.

Cuando el desequilibrio forma un zigzag hacen falta dos rotaciones: primero se endereza el hijo y después se rota la raíz. Cada rotación toca una cantidad constante de enlaces y cuesta $O(1)$.

AVL: el factor de balance

Un AVL guarda o calcula el factor de balance de cada nodo:

Exige que ese factor sea $-1$, $0$ o $1$. Después de insertar o borrar, recorre el camino hacia la raíz, actualiza alturas y rota donde la regla se rompe. Su balance estricto produce búsquedas muy predecibles, a cambio de más ajustes durante modificaciones.

Rojo-negro: un bit de color

Un árbol rojo-negro agrega un bit conceptual de color. Entre otras reglas, la raíz es negra, un nodo rojo no tiene hijo rojo y todos los caminos desde un nodo hasta hojas vacías contienen la misma cantidad de nodos negros.

Estas propiedades permiten caminos de longitudes distintas, pero garantizan que el más largo no supere el doble del más corto. La altura sigue siendo $O(\log n)$. Inserciones y borrados reparan colores y, cuando hace falta, aplican rotaciones.

Cuál de los dos, y por qué carga

AVL mantiene una forma más rígida y suele favorecer cargas con muchas búsquedas. Rojo-negro acepta algo más de desnivel y suele requerir menos rotaciones en cargas con muchas escrituras.

No es una ley universal de rendimiento: caché, implementación y patrón de claves también importan. Las bibliotecas suelen elegir rojo-negro para mapas y conjuntos ordenados porque ofrece buenas garantías con actualizaciones moderadas.

Cuál de todos, en la práctica

Cierre

Las rotaciones reparan la forma sin alterar el orden. AVL controla diferencias de altura; rojo-negro controla colores y cantidad de nodos negros. Las reglas son distintas, pero el objetivo es el mismo: impedir que la altura crezca linealmente.