PDF de programación - Árboles AVL

Árboles AVL

Sebastián Gurin (Cancerbero)

Copyright © 2004 by Sebastián Gurin

Copyright (c) 2004 Sebastián Gurin. Permission is granted to copy,
distribute and/or modify this document under the terms of the GNU Free
Documentation License, Version 1.2 or any later version published by the
Free Software Foundation; with no Invariant Sections, no Front-Cover Texts,
and no Back-Cover Texts. A copy of the license is included in the section
entitled "GNU Free Documentation License".

1. 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 árbol binario 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 árbol para 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 operaciónes 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 de equilibrio de los
árboles AVL implica una dificultad a la hora de insertar o eliminar elementos: estas
operaciones pueden no conservar dicha propiedad.

1

Árboles AVL

Figure 1. Árbol AVL de enteros

A modo de ejemplificar esta dificultad, supongamos que al árbol AVL de enteros de
Figure 1 le queremos agregar el entero 3. Si lo hacemos con el procedimiento normal
de inserción de árbols binarios de búsqueda el resultado sería el árbol de Figure 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.

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

2

Árboles AVL

En Section 5 se pasará a explicar una serie de operaciones sobre los nodos de un árbol
AVL con las cuales poder restaurar la propiedad de equilibrio de un árbol AVL luego
de agregar o eliminar elementos.

2. Menor cantidad posible de nodos para una
altura dada

pag 115.

3. Declaración del tipo de dato

Iremos ya declarando el tipo de dato que representará un árbol AVL. Esto nos ayudará
a formalizar las cosas y nos permitirá en el correr de este documento ir definiendo las
operaciones sobre el tipo de dato abstracto.

El lenguaje a utilizar será C. Fue elegido tan sólo por gustos personales del autor de
este documento. Sin embargo se tratará de usar sólo aquellas características de C que
puedan ser fácilmente implementadas en la mayoría de los lenguajes estructurados
como Pascal, Modula-2, etc.

Algunas consideraciones sobre la implementación del tipo de dato
abstracto

• Las declaraciones que se listarán a continuación no tienen porqué tomarse al pie de

la letra. Cada programador tendrá su estilo y su forma de resolver sus problemas.

• Las declaraciones que se listarán a continuación no tienen porqué tomarse al pie de

la letra. Cada programador tendrá su estilo y su forma de resolver sus problemas.

• Como se podrá ver en el siguiente listado, la única diferencia de los nodos de un

árbol AVL con los de un árbol binario común es la variable altura en la estructura
nodo.

• Los nodos de un árbol pueden almacenar cualquier tipo de dato, arbitrariamente
complejo. En este documento, por razones de simplicidad se usará el tipo de dato
más simple que soporte comparaciones, o sea los enteros (tipo int de Ansi C). En el
caso de que los datos almacenados en cada nodo sean más complicados (por ejemplo
estructuras) o sean dinámicamente almacenados en memoria, algunas funciones

3

Árboles AVL

deberán adaptarse para manejarlos. Por ejemplo, se deberá pasar como parámetros
funciones de comparación, equivalencia, y de liberación de memoria.

A continuación se lista la declaración del tipo abstracto de dato Árbol AVL:

typedef struct AVLNode AVLTree;

struct AVLNode
{

int dato;
AVLTree izq;
AVLTree der;
int altura;

};

¸

Como ya dijimos, por cuestiones de simplicidad, la información almacenada en
cada nodo del árbol será un entero.

¸ Cada nodo tendrá almacenada su propia altura con respecto a la raíz absoluta del

árbol con el que estamos trabajando. Esta característica se verá en Section 4.

A continuación declaramos las operaciónes básicas sobre árboles binarios y con las
cuales trabajaremos para acceder al tipo abstracto de dato Árbol AVL de aquí en más.

Note: Si se usa algún lenguaje orientado a objetos como C++ o java y ya se
tienen clases como árboles binarios o árboles binarios de búsqueda, conviene
declarar los árboles AVL como una subclase de alguna de estas. Luego, las
operaciones declaradas a continuación se heredarán de estos tipos.

/* Constructores */

AVLTree *vacio (void);
/* devuelve un árbol AVL vacío */

AVLTree *hacer (int x, AVLTree * izq, AVLTree * der);
/* devuelve un nuevo árbol formado por una raíz con valor x,

subárbol izquierdo el árbol izq y subárbol derecho el árbol
der. */

4

˚
˚
Árboles AVL

/* Predicados

*/

bool es_vacio (AVLTree * t);
/* devuelve true sii. t es un árbol vacío. */

/* Selectores

*/

AVLTree *izquierdo (AVLTree * t);
/* devuelve el subárbol izquierdo de t. */

AVLTree *derecho (AVLTree * t);
/* devuelve el subárbol derecho de t. */

int raiz (AVLTree * t);
/* devuelve el valor de la raíz del árbol t. Precondición:

!es_vacio(t) */

int altura (AVLTree * t);
/* devuelve la altura del nodo t en el árbol */

/* Destructures */

void destruir (AVLTree * t, void (*free_dato) (int));
/* libera la memoria ocupada por los nodos del árbol. Si los

datos almacenados en cada nodo están almacenados dinámicamente
y se los quiere liberar también, debe pasarse como segundo
parámetro una función de tipo void func(int t) que libere
la memoria de objetos int. Si los datos no están
almacenados dinámicamente o simplemente no se los quiere
destruir (liberar de memoria), pásese como segundo parámetro
NULL. Nota: Función Recursiva! */

Note: Como se ha podido apreciar en el segmento de código anterior, se ha
tratado de usar, en lo posible, el lenguaje español tanto para los comentarios

5

Árboles AVL

como para los identificadores de variables y funciones. Sin embargo, esto se
hace sólo con motivo de ser coherentes con el documento y el autor recomienda
a los lectores programadores que en sus programas utilicen el lenguaje inglés
para nombrar los identificadores.

4. 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

6

return t->altura;

}

Árboles AVL

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;

}

5. 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

7

Árboles AVL

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 r