Árboles AVL

Adelson-Velskii and Landis’ Tree
Los Árboles AVL son árboles binario de búsqueda auto-balanceados-
En un árbol balanceado la altura de dos subárboles hermanos en cualquier
nodo del árbol son iguales o difieren por no más de un nivel de altura.
Si en algún momento la diferencia de alturas entre subárboles hermanos
difieren por más de uno, se realiza un rebalanceo para mantener el esto
balanceado del árbol.
La diferencia de alturas entre subárboles hermanos dan pie al término factor
de equilibrio
El rebalanceo se realiza por medio de la Rotación de la cual existen
• Rotación Simple a la Izquierda (RSI) – RII: Rotación Izquierda Izquierda
• Rotación Simple a la Derecha (RSD) – RDD: Rotación Derecha Derecha
• Rotación Doble a la Izquierda (RDI) – RDI: Rotación Derecha Izquierda
• Rotación Doble a la Derecha (RDD) – RID: Rotación Izquierda Derecha

​

¿Qué rotación aplicar?
Si un árbol está desbalanceado hacia la
izquierda (-2), aplicar rotación hacia derecha
Si un árbol está desbalanceado hacia la
derecha (2), aplicar rotación hacia izquierda

En un árbol que está desbalanceado hacia
la izquierda revisar el factor de equilibrio
del subárbol izquierdo
En un árbol que está desbalanceado hacia
la derecha revisar el factor de equilibrio
del subárbol derecho