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 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; |
- 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 the Section called Consideraciones sobre la altura de los nodos.
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. */ /* 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 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.