Arboles 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 copyof 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. Lapropiedad 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, ycomo 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 elprocedimiento 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 seriede 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 elcorrer 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 laimplementació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 enel 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...