pascal arb

Á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. Acopy 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 yLandis).
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 deelementos.
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 sepasará 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 lascosas 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 formade 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...