Arboles Binarios de Búsqueda Balanceada (AVL).

Los ABB solo mantienen eficiencia en el proceso de busqueda si estan balanceados, pero cunado tienen una tendencia degenerada la eficiencia en el proceso de busqueda baja. El algoritmo AVL propone chequear en cada operacion de insercion o eliminacion el balance del arbol y reestructurarlo en caso de que este se pierda.

Figura numero 27

    Factor de Equilibrio (FE)
    Altura sub arbiol izquierdo (hsi)
    Altura sub arbol derecho (hsd)

   FE=hsi-hsd

Figura numero 28

Un arbol binario esta balanceado (AVL) para todos los nodos, si (FE>-2 y FE<2)  sino arbol no balanceado.

Después de analizar pude concluir que un árbol es perfectamente balanceado cuando es completo, también que el factor de equilibrio (FE) de una hoja es igual a cero. 

Operación

Insertar: inicialmente se aplica la misma regla ABB pero adicional mente se calcula el FE en los nodos de la rama de la inserción, comenzando por el nodo insertado, si camino a la raíz un nodo a parte de la hoja tiene FE igual a cero o se llega a la raíz y ningún FE esta fuera de rango de balance, se para el proceso porque todo esta bien; si no cuando el FE esta fuera de balance, se reestructura el árbol en un proceso llamado rotación que compromete tres nodos principalmente y puede ser de varios casos.

• Caso 1: Rotacion(II)= izquierda izquierda, insertar: C,B,A 

• Caso 2: Rotacion (DD)= derecha derecha, insertar: A,B,C

  

  
  

• Caso 3: Rotacion (ID)= Izquierda derecha, insertar: C,A,B

• Caso 4: Rotaciozquierda, insertar: A,C,B

  

  
  

  Eliminar: se aplica inicialmente la misma regla ABB, pero adicional mente se calcula el FE en la rama de la eliminación, si se detecta desbalance, se reestructura el árbol dependiendo del caso de rotación. Ejemplo: eliminar 53,33,12,7, en el siguiente árbol.

Solución:

Como el que se quiere eliminar es el 53 se suprime y luego se calcula el factor de equilibrio en la rama donde se elimino.

ay que reestructurar, escogiendo los tres nodos donde esta el problema. 

Reestructurando queda de la siguiente manera:

Eliminando el 33 resulta de la siguiente manera:

Eliminando el 12 resulta de la siguiente manera:

Eliminando el 7 resulta de la siguiente manera:

Resulta necesario reestructurar el subarbol derecho. 

El árbol resulta de la siguiente manera:

Apreciaciones importante y reflexión:

En figura numero 27 observamos gráficamente la reestructuracion de un árbol para que pueda quedar balanceado.

Puedo llegar a la conclusión que para que un árbol este balanceado debe existir una diferencia de un 1 nivel  entre el subarbol izquierdo  y el derecho. 

Se puede observar en la figura numero 28 un árbol en el cual se le calcula el factor de equilibrio a cada nodo, y la altura del subarbol izquierdo y derecho.