6 ejemplos de Arboles AVL

Los arboles AVL son árboles binario con una propiedad adicional: se balancean automáticamente teniendo en cuenta el factor de balance (FB) y el valor de cada nodo que insertamos o eliminamos. En el  enlace Estructura de Datos: Arboles puedes conocer mas sobre la  terminología que usamos en este artículo.

El factor de balance (FB) de un nodo es la diferencia de alturas entre la rama izquierda menos la derecha, para que el árbol esté balanceado este valor solo pueden ser -1, 0 ó 1.

FB= altura(arbol.izq)-altura(arbol.der)

Para lograr el balance adecuado, debemos ubicar al nodo hijo en la posición correcta antes de hacer cualquier rotación. 

Cuando la rotación se hace con nodos externos hablamos de rotación sencilla, mientras que si se trata de nodos internos o que requieran un cambio de dirección del nodo, se refiere a una rotación doble.

Ejemplos de Auto-balanceo

1.  En este ejemplo iniciamos con un árbol balanceado, pero en el paso 2 vamos a insertar el nodo 16 en el nodo hoja número 17, esta inserción des-balancea el árbol especialmente al nodo 13, por lo tanto con este nodo es que haremos una  rotación  doble izquierda-derecha.

 

2. Ahora queremos insertar 2 en el nodo hoja 3,  esto des-balancea el árbol en el nodo interno 4, por lo tanto hacemos una rotación sencilla a la derecha y  finalmente logramos balancear el árbol 

 

3.Insertamos 3 en el nodo hoja 2, el nodo de des-balance es 4, así que hacemos una rotación doble derecha-izquierda

4. Insertamos 7 en el nodo hoja 8, el nodo de des-balance es 6, así que hacemos una rotación doble derecha (7-8)-izquierda.

5. Insertamos 9 en el nodo hoja 8, el des.balance se genera en el nodo interno 5, desplazamos el nodo 7 hacia arriba, esta es una rotación simple a la izquierda (solo interactuan los nodos 4, 5 y 7 en la rotación) , el nodo hoja 6 ahora depende de 5.

6. Este era el punto del examen :) así que tiene truco,  Esta es una rotación doble izquierda-derecha usando  los nodos 6 en la raiz, 9 y 7. 

Si tienes información adicional sobre este tema, tus comentarios, dudas  o enlaces de referencia serán bienvenidos, .

Estructura de Datos: Arboles

Un árbol es una estructura de datos no lineal y jerárquicamente organizada, cuyos elementos son nodos conectados por bordes que no forman ciclos. Todo árbol tiene un nodo raíz de donde descienden mas nodos, existe solo un camino para acceder a cada nodo desde la raíz.

Algunos ejemplos de arboles son: la tabla de contenido de un libro o el sistema de archivos de cualquier sistema operativo ya sea Unix, DOS o Windows.

 

Datos importantes y terminología

• Un árbol con n nodos tiene n-1 bordes o conectores
• La raíz es un nodo sin padres o ancestros
• las hojas son los nodos mas externos sin hijos o descendientes
• hermanos son nodos con el mismo padre

Longitud de un camino: el el número de bordes que se pueden seguir desde un nodo hasta alcanzar otro nodo

Profundidad: Número de bordes desde la raíz a el nodo, la profundidad del nodo raíz siempre es 0

Altura: Longitud del camino mas largo desde la raíz al a la hoja mas profunda que se pueda alcanzar.

Tamaño del nodo: Es la suma de todos los nodos descendientes mas uno, que equivale al nodo que estamos midiendo, el tamaño de la raíz determina el tamaño del árbol.

Estructuras para implementar árboles

Con una lista enlazada

Con una matriz si sabemos el número máximo de hijos que poseen los nodos

Siguiente:Formas de recorrer un árbol

Si tienes información adicional sobre este tema, tus comentarios o enlaces de referencia serán bienvenidos.