Recorrido narrado

AVL y rojinegro

Dos familias de árboles balanceados, con la misma idea: un invariante de balance más rotaciones.

• AVL: las alturas de los dos subárboles de cada nodo difieren como mucho en 1. Muy equilibrado: búsquedas un poco más rápidas.
• Rojinegro: cada nodo es rojo o negro; ningún rojo tiene un hijo rojo, y todos los caminos de un nodo a sus hojas tienen los mismos negros. Menos estricto: el camino más largo es como mucho el doble del más corto. Insertar y borrar rotan menos.

En los dos, la altura es O(log n) en el peor caso, sin importar el orden de las claves. Buscar, insertar y borrar cuestan O(log n) en el peor caso.

Implementar un rojinegro completo es largo y delicado. Lo importante para elegir es la garantía: balanceado = O(log n) peor caso; BST sin balance = O(h), con h hasta n.

Su fila en la tabla de costos

Los árboles balanceados (AVL, rojinegro), en las columnas de conjunto y diccionario de la ruta. La condición es el balance: el peor caso ya no depende del orden de las claves.

Representación	buscar(k)	insertar(k)	borrar(k)	mínimo	sucesor(k)	rango(a, b) con r resultados
árbol balanceado (AVL, rojinegro)	O(log n) en el peor caso	O(log n) en el peor caso	O(log n) en el peor caso	O(log n)	O(log n)	O(log n + r)