Arboles

INVESTIGACIÓN DE ÁRBOLES AVL

INTRODUCCIÓN

Definición. Un árbol 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 1.
La denominación de árbol AVL viene dada por los creadores de tal estructura
(Adelson-Velskii y Landis).

Recordamos que un árbol binario de búsqueda es un árbolbinario en el cual cada nodo cumple con que todos los nodos de su subárbol izquierdo son menores que la raíz y todos los nodos del subárbol derecho son mayores que la raíz.
Recordamos también que el tiempo de las operaciones sobre un árbol binario de búsqueda son O(log n) promedio, pero el peor caso es O(n), donde n es el número de elementos.
La propiedad de equilibrio que debe cumplir un árbolpara ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. Como se verá, el tiempo de ejecución de las operaciones sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.
Sin embargo, y como era de esperarse, esta misma propiedad deequilibrio de los árboles AVL implica una dificultad a la hora de insertar o eliminar elementos: estas operaciones pueden no conservar dicha propiedad.

Figura 1. Árbol AVL de enteros

A modo de ejemplificar esta dificultad, supongamos que al árbol AVL de enteros de Figura 1 le queremos agregar el entero 3. Si lo hacemos con el procedimiento normal de inserción de árboles binarios de búsquedael resultado sería el árbol de Figura 2 el cual ya no cumple con la condición de equilibrio de los árboles AVL dado que la altura del subárbol izquierdo es 3 y la del subárbol derecho es 1.

Figura 2. Árbol que no cumple con la condición de equilibrio de los árboles AVL.

FACTOR DE EQUILIBRIO

Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a losárboles derecho e izquierdo, igual que los ABB, y además un miembro nuevo: el factor de equilibrio.

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.

ROTACIONES SIMPLES DE NODOS 
Los reequilibrados se realizan medianterotaciones, en el siguiente punto veremos cada caso, ahora vamos a ver las cuatro posibles rotaciones que podemos aplicar.
Rotación simple a la derecha (SD):
Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de -1, es decir, que esté cargado a la izquierda.[pic]
Procederemos del siguiente modo:
Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de -2. Y llamaremos Q al nodo raíz del subárbol izquierdo de P. Además, llamaremos A al subárbol izquierdo de Q, B al subárbol derecho de Q y C al subárbol derecho de P.
En el gráfico que puede observar que tanto B como C tienen la misma altura (n), y A es una unidad mayor (n+1). Estohace que el FE de Q sea -1, la altura del subárbol que tiene Q como raíz es (n+2) y por lo tanto el FE de P es -2.
1. Pasamos el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P.
2. El árbol P pasa a ser el subárbol derecho del nodo Q.
3. Ahora, el nodo Q pasa a tomarla posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque sus dos subárboles tienen la misma altura (n), en el caso de Q, porque su subárbol...