Árboles AVL

Un árbol binario de búsqueda que se rebalancea solo. La altura se queda en O(log n) — para cualquier entrada.

Factor de balance + rotación

• Cada nodo: factor de balance = altura(izq) − altura(der), siempre en {−1,0,+1}
• La inserción lo rompe → se repara con una rotación O(1)
• Rotación: se mueven 3 apuntadores, el orden del BST se conserva
• Cuatro casos: dos rotaciones simples, dos dobles (zig-zag)

Mira cómo la entrada ordenada se mantiene balanceada

Inserta 1..7 ordenado — el caso que mató al BST simple. El AVL rota → altura 3, no 7.

El balance garantiza O(log n)

Con 100000 inserciones ordenadas: altura 17 del AVL contra 100000 del BST simple. 104× más rápido en n=8000.

AVL contra red-black

• AVL: balance más apretado → más bajo, búsquedas más rápidas, más rotaciones
• Red-black: más laxo → menos rotaciones, mejor para actualizaciones
• Los dos O(log n); gastan distinto el presupuesto de balanceo

Para llevar

Una reparación pequeña en O(1), aplicada de forma consistente, convierte un peor caso catastrófico en una garantía a prueba de balas. Sigue: árboles red-black.