Á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. */
