ES 
EnglishDefault
Українська
Polski🌳 Arbol AVL — Rotaciones Autobalanceadas
Inserta y elimina claves en un arbol AVL y observa como se actualizan los factores de balance tras cada cambio. Cuando un subarbol se inclina mas alla de ±1, rotaciones simples y dobles restauran automaticamente el balance de altura.
Sobre el Arbol AVL — Rotaciones Autobalanceadas
Un arbol AVL, llamado asi por sus inventores Georgy Adelson-Velsky y Evgenii Landis, quienes lo publicaron en 1962, es el primer arbol binario de busqueda autobalanceado. Cada nodo almacena un factor de balance igual a la altura de su subarbol izquierdo menos la altura de su subarbol derecho, y el arbol mantiene el invariante de que este valor permanece dentro de {−1, 0, 1} en todo momento. Tras una insercion o eliminacion, las alturas se recalculan a lo largo del camino de vuelta a la raiz, y el primer ancestro que se encuentra desequilibrado se corrige con una rotacion simple (desequilibrio izquierda-izquierda o derecha-derecha) o una rotacion doble (desequilibrio izquierda-derecha o derecha-izquierda) — cada una una reescritura de puntero O(1). Esta disciplina estricta mantiene la altura del arbol en O(log n) en el peor caso, a diferencia de un BST ingenuo que puede degradarse a una lista enlazada con entrada ordenada. Comparado con los arboles rojo-negro, los arboles AVL estan mas rigidamente balanceados, dando busquedas mas rapidas a costa de rotaciones mas frecuentes al insertar y eliminar, lo que hace que los arboles AVL sean atractivos cuando las lecturas superan ampliamente a las escrituras.
Preguntas Frecuentes
Por que el factor de balance debe mantenerse dentro de {-1, 0, 1}?
Este rango es el umbral preciso que mantiene la altura del arbol demostrablemente en O(log n). Adelson-Velsky y Landis demostraron que un arbol que obedece este invariante tiene una altura de como maximo aproximadamente 1.44*log2(n+2), asi que permitir factores de balance de +/-1 da suficiente flexibilidad para una insercion eficiente mientras sigue garantizando una altura logaritmica.
Cual es la diferencia entre una rotacion simple y una doble?
Una rotacion simple (caso LL o RR) corrige un desequilibrio causado por un subarbol que pesa mas en el mismo lado que su propio hijo pesado — basta con reescribir un puntero. Una rotacion doble (caso LR o RL) maneja un desequilibrio en zigzag donde el hijo pesado se inclina hacia el lado opuesto, y requiere dos rotaciones: primero en el hijo para convertirlo en un caso de rotacion simple, y luego en el propio nodo.
Como se compara un arbol AVL con un arbol rojo-negro?
Ambos garantizan una altura O(log n), pero los arboles AVL imponen un invariante de balance mas estricto, dando arboles mas bajos y busquedas mas rapidas. Los arboles rojo-negro relajan la restriccion de balance (permitiendo que el camino mas largo de raiz a hoja sea hasta el doble del mas corto), lo que significa menos rotaciones al insertar y eliminar. Esto hace que los arboles AVL sean preferibles para cargas de trabajo con muchas lecturas y los arboles rojo-negro preferibles para cargas de trabajo con muchas escrituras.
Por que la eliminacion puede requerir rotaciones en cada nivel hasta la raiz, a diferencia de la insercion?
Una insercion solo anade altura a un subarbol, por lo que como maximo se necesita una rotacion (simple o doble) para restaurar el balance, tras lo cual la altura general del subarbol se restaura a su valor previo a la insercion. Una eliminacion puede reducir la altura de un subarbol, y esa reduccion puede propagarse hacia arriba, potencialmente disparando una rotacion de rebalanceo en cada ancestro del camino hacia la raiz — hasta O(log n) rotaciones en el peor caso.
Inserta y elimina claves en un arbol AVL y observa como se actualizan los factores de balance tras cada cambio. Cuando un subarbol se inclina mas alla de ±1, rotaciones simples y dobles restauran automaticamente el balance de altura.
2D · HTML5 Canvas 2D · objetivo 60 FPS · funciona totalmente en el cliente, sin instalacion