Arbol AVL

Árboles AVL (Adelson-Velskii y Landis)

Árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.con el objetivo de maximizar el tiempo de acceso en búsqueda.
Basándose en el siguiente algoritmo:

Rotación derecha
1.- Se busca nodo padre de raíz (padre) (FIG. 1.0)
2.-Nodo a toma la referencia de nodo izquierdo de raíz (FIG. 1.0)
3.-Hijos derechos de nodo a pasan a ser de nodo izquierdo de raíz (FIG. 1.1)
4.-Nodo a apunta en su brazo derecho a raíz (FIG. 1.1)
5.-Padre de nodo raíz apunta a nodo a (FIG. 1.2)

FIG. 1.0 FIG 1.1

FIG 1.2

Rotación Izquierda
1.- Se busaca nodo padre de raíz (padre) (FIG. 1.0)
2.-Nodo a toma la referencia de nodo derecho de raíz (FIG. 1.0)
3.-Hijos Izquierdos de nodo a pasan a ser de nodo derecho de raíz (FIG. 1.1)
4.-Nodo a apunta en su brazo izquierdo a raíz (FIG. 1.1)
5.-Padre de nodo raíz apunta a nodo a (FIG. 1.2)

Fig. 1.0 Fig. 1.1

Fig. 1.2

Composición de Nodo en árbol AVL

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.
Explicación de 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;
Donde la diferencia obtenida por definición de este árbol debe ser -1, 0, 1

Composición grafica del nodo:

Arellano Bello Gilberto Jesus

Lic.informatica,Tecnologico de Zacatepec