ARBOLES AVL

  Un árbol AVL es un árbol binario de búsqueda (ABB) que tiene como característica que siempre esta balanceado; que se le añade una condición de equilibrio. esta condición es que para todo nodo ,la altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1.

CARACTERISTICAS

La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1. 

Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles. 

Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su subárbol izquierdo es más alto y 0 si las alturas son las mismas. 

La inserción y eliminación en AVLS es la misma que en los ABBS. 

EQUILIBRIO

Equilibrio (n) = altura-der (n) – altura-izq (n) describe relatividad entre subárbol der y subárbol izq. 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                  es necesario reequilibrar.

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.

     Se encuentra rotación simple cuando se cambia de nodos de izquierda a derecha o derecha a izquierda

Se realiza rotacion doble cuando hay las dos formas de rotacion simultanias