Arboles AVL

Consideraciones sobre la altura de los nodos

Como vimos en la definición del tipo abstracto para nodos de árboles AVL, se necesitará tener acceso a la altura cada nodo del árbol en tiempo constante. Dado que una función para hallar la altura de un nodo dado en un árbol tendrá un tiempo de ejecución de O(log(n)) peor caso, no nos queda otra alternativa que almacenar una variable altura en cada nodo e irla actualizando en las inserciones y eliminaciones que se efectúen sobre el árbol.

Como el lector ya debería saber, una función para calcular la altura de un nodo puede escribirse recursivamente como:

int altura(AVLTree *t)

{

if(es_vacio(t))

return -1;

else

return max(altura(izquierdo(t)), altura(derecho(t)));

}

Queremos que la altura de un árbol que consta de sólo un nodo sea 0. Entonces debemos definir la altura de un árbol vacío como -1.

Sin embargo, no podemos darnos el lujo de tener una función cuyo tiempo de ejecución siempre es O(n) ya que, como dijimos, necesitamos la altura de un nodo en tiempo constante. Para ello, redefiniremos la función de la siguiente manera, aprovechando el campo altura que ahora tiene cada nodo del árbol.

int altura (AVLTree * t)

{

if(es_vacio(t))

return -1;

else

return t->altura;

}

Important: Debemos tener mucho cuidado en actualizar el campo altura de cada nodo siempre que modifiquemos de alguna manera el árbol AVL.

Así, es importante tener una función que nos permita actualizar la altura de un nodo cualquiera del árbol y cuyo tiempo de ejecución sea O(1) en el peor de los casos. A continuación se lista una tal función:

void

actualizar_altura (AVLTree * t)

{

if(!es_vacio(t))

t->altura = max (altura ((t)->izq), altura ((t)->der)) + 1;

}

Rotaciones simples

Veremos a continuación una operación sencilla sobre un árbol binario de búsqueda que conserva el órden en sus nodos y que nos ayudará a restaurar la propiedad de equilibrio de un árbol AVL al efectuar operaciones sobre el mismo que puedan perturbarla.

Figure 3. Árbol antes de la rotación simple

Miremos por un momento el árbol de Figure 3. Dado que este es un árbol de búsqueda se debe cumplir x < y y además todos los nodos del subárbol A deben ser menores que x y y; todos los nodos del subárbol B deben ser mayores que x pero menores que y; y todos los nodos del subárbol C deben ser mayores que y y por lo tanto que x.

En Figure 4 se ha modificado sencillamante el árbol. Como puede verificarse fácilmente por las desigualdades descriptas en el párrafo anterior, el nuevo árbol sigue manteniendo el órden entre sus nodos, es decir, sigue siendo un árbol binario de búsqueda. A esta transformación se le denomina rotación simple (o sencilla).

Figure 4. Árbol luego de la rotación simple

Veamos un ejemplo concreto. Deseamos insertar el número 3 en el árbol de enteros de Figure 5. La inserción se muestra punteada en Figure 6. Sin embargo, como puede verse, la inserción a provocado la pérdida de la propiedad de equilibrio del árbol ya que dicha propiedad no se cumple en el nodo marcado con rojo. ¿Qué hacemos para recomponer dicha pripiedad? Simplemente realizamos una rotación simple. En este caso se dice que la rotación es izquierda ya que la "pérdida de equilibrio se produce hacia la izquierda. En Figure 7 puede verse el árbol luego de la rotación: la propiedad de equilibrio ha sido reestablecida. Como mostramos atrás, la rotación conserva el orden entre los nodos, por lo que podemos afirmar que este último árbol si es AVL.

Figure 5. Árbol AVL

Figure 6. Árbol luego de la inserción: pérdida de la propiedad de equilibrio marcada

...