Arboles AVL

ARBOLES AVL

Un árbol AVL que sus siglas vienen de (Adelson-Velskii y Landis), es un árbol binario que cumple con la igualdad entre niveles. Estos deben ser nivelados con el siguiente procedimiento.

A continuación vamos a presentar varios ejemplos de como deben ser nivelados estos arboles.

¿Como podemos saber cuando un árbol es AVL? lo podemos saber cuando la sumatoria de todos los nodos tiene que dar como resultado máximo 1, ¿Como realizamos la sumatoria de los nodos? cuando existe un nodo por la parte derecha es +1 cuando existe un nodo en la parte izquierda es -1, por ejemplo la raíz que es el nodo A en la derecha tiene 3 nodos que son B, D y F, y en la izquierda tiene 1 nodo que es el nodo C, la operación queda de la siguiente forma:

3 - 1 = 2 por lo tanto al pasar de 1 no es un árbol AVL

Entonces a estas operaciones se les llama Factor de balance y cada nodo tiene su factor de balance.

A= 2 (3-1=2)
B= 1 (2-1=1)
C= 0 (0-0=0)
D= 1 (1-0=1)
E= 0 (0-0=0)
F= 0 (0-0=0)


Ahora teniendo los factores de niveles podemos observar que debemos marcar el que tiene primero el numero mayor y el que le sigue, en este caso marcamos con la letra p a el nodo A y con q a el nodo B, ahora vamos a realizar una rotación a la derecha, antes de eso vamos realizar el recorrido en In-Orden: F, D, B, E, A, C.


Aquí podemos observar el árbol con la rotación a la derecha donde el nodo A toma el lugar del nodo E y este pasa hacer un hijo del nodo A, para verificar si el árbol es AVL hallamos los respectivos factores de balance.


Video Complementario

Ejercicios

Dada la secuencia de claves enteras:100,29,71,82,48,39,101,22,46, 17,3,20,25,10.Representar gráficamente el árbol AVL correspondiente.


Elimine claves consecutivamente hasta encontrar un desequilibrio y dibuje la estructura del árbol tras efectuarse la oportuna restauración