Arbol AVL

Es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó. [(AVL) Adelson-Velskii y Landis]

Características:

• Están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa
• La complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n)
• La inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Factor de equilibrio:

El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo; Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

Si el factor de equilibrio de un nodo es: 0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. 1 -> el nodo está desequilibrado y su subárbol derecho es un nivel más alto. -1 -> el nodo está desequilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.

.