arboles

En un árbol de búsqueda binaria es posible que con la

cantidad de inserciones y extracciones que se realizan sin
un orden predecible el árbol resultante tenga un número
mayor de nodos en larama izquierda que en la rama
derecha o a la inversa, teniendo como consecuencia
tiempos de búsqueda muy altos.

Un árbol AVL es un árbol binario de búsqueda que cumple con
la condición de que ladiferencia entre las alturas de los
subárboles izquierdo y derecho de cada uno de sus nodos

difieren a lo mucho en 1. El método que logra lo anterior, fue
descrito en 1962 por dos matemáticosrusos G. M. Adelson-Vel Skii y
E. M. Landis; en su honor los árboles de búsqueda resultantes se

denominan Arboles AVL.

Se tiene el siguiente árbol :

El factor de balance para cada nodo es :
A= 2 -3 = -1
B=1-0=1
C=2-1=1
D=0-0=0
E=1 -0=1
F=0 -0=0
G=0 -0=0
Si el factor de balance de todos y cada uno de los nodos que pertenecen al árbol
esta el rango de -1. . 1, se puede decir que esun árbol AVL o balanceado.

class nodoAVL
{

int dato;
int fb; //factor de balance del nodo
nodoAVL izq, der;

}

Se definirá como el ajuste de varios apuntadores con el objeto deconvertir un árbol no AVL aun árbol AVL.
El árbol que se muestra pierde sus propiedades de AVL dado que
tiene una altura mayor por su izquierda

Por lo que es necesario aplicarle una rotación. Unarotación exige el
ajuste de varios apuntadores con el propósito de :

El árbol siga siendo AVL.
 Que el recorrido en inorden sea el mismo antes de la
rotación y después de ella.

Se aplica unasimple rotación a la derecha cuando el nodo
raíz cuenta con una altura no permita por su izquierda.
q=p(izq);
p(izq)=q(der)
q(der)=p;
p=q;

Se aplica una simple rotación a la izquierda cuando elnodo
raíz cuenta con una altura no permita por su derecha.
q=p(der);
p(der)=q(izq)
q(izq)=p;
p=q;

Anteriormente pudimos restaurar la propiedad de
equilibrio cuando se presentaban...