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.