ARBOLES AVL

Es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho.

FACTOR DE EQUILIBRIO

Se denomina factor de equilibrio o factor de balanceo , el cual no sirve para poder evidenciar si el arbol se encuentra balanceado o no.

Este arbol no es AVL , porque no esta balaceado.

Factor de balance

10=-2

12=-1

15= 0

EL Factor de balance nuevo es: 10=0 ;12=0 ; 15= 0

ROTACION A LA IZQUIERDA

Se realiza una rotacion a la izquierda cuando el arbol queda desbalanceado por la derecha y es el ajuste de dos apuntadores , despues de una altura no permitida.

DOBLE ROTACION A LA IZQUIERDA

Se hace una doble rotacion a la izquiera si se cumple:

1. El nodo indicado por p tiene un factor de balance menor que 1.

2.El nodo indicado por q tiene un factor de balance igual a 1

3.Hay que hacer una simple rotacion a la derecha desde q y una simple rotacion a la izquierda desde p

ROTACION A LA DERECHA

1. El nodo indicado por p tiene factor de balance > 1

2.El nodo indicado por q tiene factor de balance = 1

DOBLE ROTACION A LA DERECHA

1. El nodo indicado por p tiene factor de balance > 1

2. El nodo indicado por q tiene factor de balance = -1

1.Simple rotacion a la izquierda ---> q

2.Simple rotacion a la derecha ---> p

OPERACIONES

1.INSERCION

En la inserción debe mantenerse la condición de equilibrio, la altura del subárbol izquierdo y la del subárbol derecho difieran en una unidad o sean iguales. En caso de que se genere un desequilibrio hay que reequilibrar la estructura para que siga siendo un árbol AVL.

2.ELIMINACION

En la eliminacion podemos inferir que el proceso es idéntico al de la inserción, la única diferencia es que en la inserción tras realizar una rotación el árbol ya queda equilibrado, mientras que en el borrado puede ser necesario realizar mas de una rotación, para que vuelva a quedar equilibrado .

Video Tutorial