Árbol AVL

Los árboles AVL 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. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, 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.

Definición de la altura de un árbol
Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H(T), es:

* 0 si el árbol T contiene solo la raíz.
* 1 + max(H(Ti),H(Td)) si contiene más nodos.

Definición de árbol AVL
Arboles balanceados o equilibrados: · Un árbol binario de búsqueda es k-equilibrado si cada nodo lo es. · Un nodo es k-equilibrado si las alturas de sus subárboles izquierdo y derecho difieren en no más de k. Arboles AVL (Adel’son, Vel’skii, Landis) · Un árbol binario de búsqueda 1-equilibrado se llama árbol AVL. Cabe destacar que un árbol AVL no es un Tipo de dato abstracto (TDA) sino una estructura de datos.

Arbol Binario No Equilibrado



Arbol Binario Equilibrado - AVL




Factor de equilibrio


Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el 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á equilibrado y su subárbol derecho es un nivel más alto.
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.

Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.