Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

Una clase C++ completa para conocer y usar árboles

Resumen   

Discutimos cómo es el funcionamiento y la implementación de la clase C++ Tree, que puede ser usada por alumnos para programar algoritmos recursivos que trabajan en jerarquías. Esta clase es bastante general y subsume la mayoría de las abstracciones descritas en los libros de texto.

We discuss how the workings and implementation of the Tree which can be used by students to program recursive algorithms that work in hierarchies. This abstraction is quite general and subsumes most tree abstractions described in text books.

T | [a] <---- p / | \ / / \ \ / / \ \ [b] [c] [d] [e] /|\ /|\ / | \ / | \ / | \ / | \ [f] [g] [h] [i] [j] [k] / \ [l] [m] / \ [n] [o]

Figura 1

Introducción   

      Es usual confundir el significado de los conceptos de "Estructura de datos", "Clase C++", "Abstracción" y "Modelo de la clase". Una Clase C++ es un módulo de programación que tiene una funcionalidad específica definida por su implementación. La Abstracción es necesaria para que quienes usen la clase C++ lo hagan de forma adecuada pues una de las razones más importantes para usar abstracción es documentar módulos para poder reutilizarlos. El Modelo de la clase es un diagrama, en el que se muestra la relación entre los campos que incluye la clase; la Figura 1 es un modelo del árbol. El concepto de Estructura de datos se ha usado en los libros de texto en los que se explican algoritmos eficientes para mostrar tanto el modelo de la clase, como su eficiente implementación algorítmica; por eso, a veces se confunde la estructura de datos con su modelo, pero en realidad el modelo sólo es una parte de la estructura de datos.

      En el dibujo de la izquierda de la Figura 1 se muestra la estructura jerárquica del árbol. En el dibujo de la derecha muestra con detalle cómo está construido un árbol, pues en ese diagrama se detalla la relación entre los campos de los nodos que forman el árbol. La figura de la izquierda es más abstracta, mientras que la de la derecha corresponde a una implementación concreta, pues es el modelo usado para una de las implementaciones C++ aquí descritas.

      La construcción de programas por partes, usando módulos, se facilita mucho cuando se usan clases. Muchas clases existen porque corresponden a objetos concretos, como ocurre con las clases "Persona" o "Número Complejo"; a éstos módulos básicos podemos llamarles Clases elementales. Hay otras clases, las que llamamos clases Contenedoras, que sirven para almacenar a otros objetos. Los contenedores más importantes son tres:

1. El Vector o Arreglo
2. La Lista
3. El Arbol

      Existen otros contenedores, como "Heap.pas", "Poly.pas", "Matriz.c++", etc, pero la mayoría de las estructuras de datos importantes se obtienen al combinar vectores, listas y árboles.

      Indiscutiblemente, el más importante de todos los contenedores es el vector, que es una construcción sintáctica básica de la mayoría de los lenguajes de programación. La Lista le sigue en orden de importancia, pues generalmente está implementada como una estructura dinámica que le evita al programador definir de antemano la capacidad máxima que necesitará, lo que facilita la escritura de programas. Es tan importante la lista que hay lenguajes especializados en su uso, como por ejemplo Lisp o Scheme.

      En comparación a los otros contenedores, los árboles se usan relativamente poco, pues la mayor parte de los programas no necesitan manejar estructuras jerárquicas recursivas. De hecho, la biblioteca STL de C++ está compuesta de contenedores "lineales", pues todos son secuencias que tienen algunas cualidades adicionales [Brey-2000]; lo mismo ocurre con la biblioteca de componentes que construyó Microsoft para su plataforma .NET. Además, con las listas es posible implementar árboles, por lo que en aquellas ocasiones en que una jerárquicas recursiva es la solución, muchos programadores escogerán escribir su programa de árboles directamente, o utilizan árboles binarios, cuyos algoritmos se pueden encontrar en la mayoría de libros de texto sobre estructuras de datos [AHU-84].

      Aunque el árbol no es tan importante como la lista, es didácticamente conveniente estudiarlo por lo menos por las siguientes razones:

1. La especificación del árbol parece simple a primera vista, pero en la práctica es bastante complicada, por lo que cuando el estudiante logra entenderla entonces aprende con profundidad cómo debe diseñar e implementar programas usando abstracción como mecanismo de construcción y documentación de módulos.
2. En esta especificación del árbol basta usar el concepto de "Árbol", plasmado en las clases C++ "Tree", que permite usar las clases sin necesidad de conocer la estructura interna del árbol, ni la de sus nodos, que es lo que ocurre con otras implementaciones [BD-96]. Por eso, en las especificaciones de las operaciones nunca es necesario mencionar el concepto de "Nodo", que está presente en casi todos los árboles descritos en los libros de texto; el uso de estas clases permite la separación de funciones que es requisito necesario para aplicar con éxito la abstracción al construir programas.
3. Como en las especificaciones de las operaciones del árbol no se habla de "nodos" tampoco es necesario hablar de " Punteros". Más aún, para usar la clase "Tree" no hace falta manejar punteros, lo que resulta en una clase muy simple, que consiste únicamente del tipo "Tree" junto con sus operaciones.
4. Esta implementación es una buena herramienta para que el estudiante asimile las cualidades y defectos que tiene C++ como lenguaje de programación para la construcción de programas sofisticados o de alta complejidad.
5. Dada la complejidad de esta implementación, el estudiante tiene la oportunidad de comprender cuáles son las limitaciones que tiene el uso abstracción para la construcción de programas sofisticados.

El árbol de nodos   

      Antes de implementar la clase "Tree" es necesario definir qué es un árbol. Los árboles son grafos, pues están compuestos de nodos y aristas que los unen. Para definir matemáticamente un árbol es necesario definir primero el concepto de Camino, que es una secuencia de aristas que conectan nodos, en que la arista siguiente en el camino comienza en el nodo en que termina la arista anterior. Un Circuito es un camino en el que el primer y último nodo son el mismo, y un Circuito simple es un circuito en que cada nodo aparece sólo una vez. Se dice que el grafo es Conectado si siempre existe un camino entre cualesquiera 2 nodos del grafo. Con base a estos conceptos son equivalente las siguientes definiciones matemáticas del árbol "T" [Even-79]:

1. "T" es un grafo conectado que no tiene circuitos simples.
2. "T" no tiene circuitos simples, pero si a "T" se le agrega cualquier arista se forman un circuito.
3. "T" es un grafo cuyos nodos no están conectados consigo mismos en el que siempre existe un único camino entre cualesquiera 2 nodos.
4. "T" es un grafo conectado, pero si una arista de "T" es removida el resultado es que "T" queda desconectado.
5. "T" tiene "n" nodos y no tiene circuitos, y también tiene exactamente "n-1" aristas.
6. "T" es un grafo conectado de "n" nodos que tiene exactamente "n-1" aristas.

      Todas estas definiciones son escuetas, correctas y completas pero, paradójicamente, no hablan de las propiedadas principales de los árboles, por lo menos desde el punto de vista del programador, pues no mencionan que un árbol en una jerarquía encabezada por su raíz. De hecho, en estos árboles matemáticos cualquier nodo podría fungir como nodo raíz. Estos hechos son muestra de que el concepto de árbol no es fácil de definir, pues tiene muchos posibles significados (¿qué es un árbol binario?).

      Una forma de definir qué es un árbol es mostrar cómo está hecho. En los libros de texto lo usual es definir un árbol como un conjunto finito de elementos o nodos organizados de acuerdo a las siguientes propiedades:

1. T es un conjunto finito, o vacío, de elementos almacenados en "nodos" [T.Empty()].
2. Los nodos del árbol están conectados unos a otros por medio de aristas o enlaces.
3. Un árbol no vacío siempre tiene un único nodo llamado la "raíz" del árbol [T.Root()] del que todos los demás nodos son descendientes [T.Child(i)].
4. Cada nodo en el árbol, excepto el nodo raíz, tiene un único nodo del que desciende directamente. Ese nodo es el nodo padre [T.Father()].
5. Dos nodos que tienen el mismo padre se llaman hermanos [T.Sibling(i)].
6. Los nodos que no tienen descendientes se llaman nodos hoja [Is_Leaf(T)].
7. La longitud del camino que separa a un nodo de la raíz se conoce como su "profundidad" [Depth(T)].
8. La longitud del camino más largo desde un nodo a alguno de sus descendiente es la altura del nodo [Height(T)].
9. La altura del árbol es la altura de su raíz.
10. Entre cualesquiera dos nodos del árbol siempre existe un único camino que los une.
11. Los descendientes de un nodo siempre están ordenados de izquierda a derecha [T.Child(i)].
12. Cada nodo puede tener un hijo número "n" aunque no tenga hijos anteriores o posteriores.

[r] / \ [0] [1] [r] / \ [1] [0]

[r] / [h] [r] \ [h]

typedef .... value_type; // a lo STL class Tree_Node { value_type _data; Tree_Node * _left; Tree_Node * _right; // ... };

Figura 2

      Las últimas 2 condiciones son necesarias para que la definición de lo que es un árbol sea completa, pues al eliminarlas ocurre que los dos árboles binarios de la Figura 2 son iguales. Estos árboles binarios se diferencian por el orden de sus hijos, o porque en que uno tiene su hijo "[h]" a la izquierda, y el otro lo tiene a la derecha y es precisamente la última condición la que sirve para determinar si éstos 2 árboles son iguales o diferentes. En el caso de árboles binarios, lo usual es implementarlos usando 2 punteros "_left" y "_right" que indican adónde está almacenado el nodo izquierdo y derecho, por lo que al poner el puntero nulo [(Tree_Node*)0] en alguno de estos campos es posible determinar si un nodo es el hijo derecho o izquierdo de su nodo padre.

      Si cada nodo puede tener un hijo número "n" aunque no tenga hijos anteriores o posteriores, se puede concluir que "si el árbol está construido de nodos, y cada nodo puede tener hasta "N" hijos, lo natural es poner en el nodo un vector de "N" punteros a los hijos" [AHU-84]:

class Tree_Node { // ... etc. private: value_type _data; Tree_Node * _Lchild[N]; // ... };

bool Is_Leaf(Tree_Node * p) { if (p == 0) return false; for (unsigned i=0; i<N; ++i) { if (p->_Lchild[i] != 0) return false; } return true; }

Figura 3

      La discusión puede seguir de la siguiente manera: "Un nodo hoja es fácil de detectar, pues todos los punteros a sus hijos son punteros nulos", como se hace en el algoritmo "Is_Leaf()" de la Figura 3.

class Tree_Node { private: value_type _data; list <Tree_Node*> _Lchild; // ... };

class Tree_Node_N { struct Node_Index { Tree_Node * _child; unsigned _n_child; // ... }; private: value_type _data; list <Node_Index> _Lchild; // ... };

Figura 4

      Sin embargo, esta implementación de vectores es ineficiente, pues en cada hoja hay que almacenar un vector completo lleno de valores nulos. Por eso, es natural tratar de usar una representación más eficiente, como lo es una lista de punteros a los nodos. Desafortunadamente, la ventaja de usar una lista también incide en la estructura interna del árbol, pues si en la lista de hijos "_Lchild<>" se mantienen únicamente los punteros no nulos, al almacenar un árbol binario como el de la Figura 2 no se podría distinguir entre un hijo izquierdo del derecho, pues en la lista estaría sólo el puntero al hijo. Para remediar este problema se puede seguir alguno de estos caminos:

1. Almacenar siempre los punteros a los hijos, aunque sean punteros nulos. En este caso es mejor usar el vector de punteros que una lista, pues generalmente un vector de "N" punteros ocupa menos espacio que la lista de "N" punteros.
2. Almacenar los punteros nulos a los hijos sólo para nodos internos, de manera que la lista de "_Lchild<>" para nodos hoja sería siempre una lista vacía.
3. Agregarle a cada puntero no nulo una indicación de cuál es el número de hijo que representa, como se muestra en la parte derecha de la Figura 4.

class Tree_Node_N { struct Node_Index { Tree_Node * _child; unsigned _n_child; // ... }; private: value_type _data; list <Node_Index> _Lchild; // ... };

class Tree_Node_N { struct Node_Index { Tree_Node * _child; // ... }; private: value_type _data; unsigned _n_child; list <Node_Index> _Lchild; // ... };

Figura 5

      Usar el campo "_n_child" parece ineficiente o contraproducente, pues hace que los nodos sean más "pesados" porque incluyen más datos que se usan para mantener la estructura jerárquica del árbol. De hecho, muchos programadores se salen de su camino para implementar "listas unidireccionales" [DiM-2000a], con el fin de ahorrarse un puntero (¡hasta ahorrarse un "bit" merece un buen esfuerzo! [DiM-2000b]). Aunque le es natural a todo programador tratar de ahorrar todo el espacio posible, en la práctica no es eso siempre lo mejor, como se ha hecho en la biblioteca STL, en que se usan listas doblemente enlazadas, pese a que para ellos cada nodo de la lista incluye 2 punteros en lugar de uno en una lista simple. Por eso no debe preocupar mucho el agregar el campo "_n_child" al nodo, aunque es mejor ponerlo dentro del nodo hijo, y no en el vector de punteros del padre, como se muestra en la parte derecha de la Figura 5.

      Si se recorre la lista de hijos de un nodo y ya se llegó al hijo número "_n_child", para el programador es posible recuperar este valor tanto si está almacenado junto al puntero hijo en la lista "_Lchild" como si lo toma de uno de los campos almacenados en el nodo hijo. Almacenar "_n_child" en el nodo (hijo) tiene una ventaja adicional, pues permite saber qué posición ocupa el nodo en la lista de hijos del padre aún cuando no se haya localizado al nodo recorriendo los hijos del padre, lo que puede ocurrir en los recorridos que van de las hojas hacia la raíz.

class Tree_Node_N { struct Node_Index { Tree_Node * _child; // ... }; private: value_type _data; unsigned _n_child; list <Node_Index> _Lchild; // ... };

class Tree_Node { private: unsigned _n_child; value_type _data; Tree_Node * _father; list <Tree_Node *> _Lchild; // ... };

Figura 6

      Desde la óptica de la implementación, para determinar si un hijo es derecho o izquierdo en el árbol binario, o su posición en un árbol "n"-ario, es necesario que cada nodo tenga los campos que aparecen a la derecha en la Figura 6. Si se hace el análisis desde la óptica de la abstracción, es necesario definir qué significa la operación "T.Child(i)" cuando no existe un hijo número "i". La respuesta puede ser muy sencilla si se define que existe el hijo "T.Child(i+1)" sólo existe cuando ya existe todos los hijos anteriores, desde "[0→i]". En este caso, los 2 árboles en el medio de la Figura 2 son iguales (y no son árboles binarios). Si se elimina esta condición se torna posible representar árboles binarios; por eso es necesario que un árbol tenga un "i"-ésimo hijo nulo, o sea, que no exista "T.Child(i)".

class Tree_Node { private: value_type _data; // ****** ****** unsigned _n_child; Tree_Node * _father; list <Tree_Node *> _Lchild; // ... };

class Tree_Node { private: value_type _data; unsigned _refCount; unsigned _n_child; Tree_Node * _father; Tree_Node * _Lchild[N]; // ... };

Figura 7

      Como se muestra en la derecha de la Figura 7, en el nodo se incluye un vector completo de "N" punteros y un puntero de vuelta al padre, que es nulo en el caso de la raíz del árbol. Debido a que la clase "Tree_Node" fue hecha para mostrar las separación clara entre especificación e implementación, no se ha tratado de minimizar la cantidad de espacio usado. Además, se ha agrado el campo "_refCount" que sirve para mantener un contador de referencias, lo que, como se verá luego facilita mucho el trabajo con árboles y sus sub-árboles.

El árbol hecho con base en la lista   

      La programación es el arte de acomodar trucos para obtener algoritmos efectivos. Por eso, al analizar el árbol que usa nodos con un vector de punteros, salta inmediatamente a la vista una de sus principales limitaciones: ningún nodo puede tener más de Tree_Node::N hijos, que es la dimensión máxima del vector de punteros del nodo. Además, la cantidad de punteros nulos almacenados en nodos del árbol es muy grande, pues todos los nodos hoja, que casi siempre son los más en el árbol, tienen que tener su vector de punteros completamente lleno de punteros nulos. Aún para árboles binarios eso es desperdicio.

class Tree_Node { // Máximo "N" hijos por "Tree_Node" static const unsigned N = 15; private: value_type _data; unsigned _refCount; unsigned _n_child; Tree_Node * _father; Tree_Node * _Lchild[N]; // ... \=/ };

#include <map> // ... no hay máximo "N" ... class Tree_Node { private: value_type _data; unsigned _refCount; unsigned _n_child; Tree_Node * _father; map<unsigned, Tree_Node *> _Lchild; // \===/ };

Figura 8

      Una manera de corregir estas limitaciones es usar un vector inteligente para los hijos, como lo sería un diccionario en indexado por "_n_child", de manera que "_Lchild[_n_child]" exista únicamente para aquellos valores de "_n_child" que contienen un puntero a otro nodo. Un candidato adecuado para implementar este vector es la clase "map<>" de la biblioteca STL, como se muestra en la derecha de la Figura 8.

T = A A /|\ / B C D B / \ \ L M C / \ L D \ M

Figura 9

      Un truco bien conocido es el de usar un árbol binario para representar los valores de un árbol "n"-ario, como se muestra en la Figura 9. La forma de hacerlo es bastante simple, pues ambos árboles tienen la misma raíz. En el árbol binario, el hijo izquierdo siempre es el primer hijo del árbol "n"-ario, mientras que los hijos derechos del árbol binario son los hermanos del hijo izquierdo. Como sobra un puntero a la derecha en el nodo del último hijo (en los nodos "D" y "M"), queda muy conveniente poner ahí un puntero al padre, lo que se ha enfatizado en la figura al usar doble línea. Todos los punteros en el árbol se usan, y únicamente el nodo raíz tiene su puntero derecho nulo, pues en un árbol sólo la raíz no tiene nodo padre. Esta estructura de datos es muy compacta y eficiente [HS-92].

      El inconveniente de estos árboles llamados "Hijo-izquierdo Hermano Derecho" es que para llegar al hijo número "n" hay que visitar antes a todos los hijos anteriores, mientras que en el árbol implementado con un vector de punteros a los hijos esta operación es inmediata, pues en un vector la cantidad de tiempo para llegar a cualquiera de sus elementos siempre es la misma. La ventaja de los árboles hijo+hermano es que no desperdician espacio en punteros nulos, y además sirven para representar de manera natural cualquier árbol "n"-ario, pues no tienen la limitación de un máximo de hijos por nodo (siempre y cuando haya memoria dinámica suficiente). Por eso, en muchas ocasiones es preferible usar árboles hijo+hermano, pues no requieren del programador cliente grandes cuidados para evitar sobrepasar el límite de número de hijos.

class Tree_Node { private: value_type _data; unsigned _refCount; bool _points_to_father; Tree_Node * _left_child; Tree_Node * _right_brother; }; // Tree_Node

#include "pointer.h" class Tree_Node { private: value_type _data; unsigned _refCount; Tree_Node * _left_child; pointer<Tree_Node> _right_brother; }; // Tree_Node

Figura 10

      Al implementar los árboles hijo+hermano surgen algunas dificultades que hay que mencionar. Lo primero es que se hace necesario incluir en el nodo algún marcador que permita diferenciar si un puntero derecho apunta a otro hermano, o si más bien ahí está el puntero al nodo padre que tiene el último hermano. Existen varios trucos de programación para lograr esta diferenciación entre los que se pueden destacar 2. El primero, y talvez el menos complicado, es esconder en el puntero final un "bit" que indique si ese puntero es o no un puntero al padre, usando un truco de programación similar al expuesto en [DiM-2000b]. Como se muestra en la Figura 10, este truco evita incluir en el nodo un campo adicional, de tipo booleano, que indique si el puntero apunta al padre o al hermano. La razón por la que aquí no se usa el truco del "bit escondido" es que es difícil de explicar a estudiantes novatos, y además se puede lograr el mismo efecto con la otra alternativa descrita más adelante.

class Tree_Node { private: value_type _data; unsigned _refCount; bool _points_to_father; Tree_Node * _left_child; Tree_Node * _right_brother; }; // Tree_Node

// (_n_child < 0) ==> ( _points_to_father == true) class Tree_Node { private: value_type _data; unsigned _refCount; int _n_child; // incrementado en int(1) Tree_Node * _left_child; Tree_Node * _right_brother; }; // Tree_Node

Figura 11

      Como en muchas ocasiones es importante saber cuál es el número de hijo entre todos los hijos de un mismo padre, que se obtiene con el método "Child_Number()" del árbol, es necesario incluir en el nodo el campo "_n_child"; ahí se puede también indicar si un nodo es el último en la lista de hijos de su padre, almacenando un valor negativo en el campo "_n_child". Como en C++ todos los índices comienzan en cero "0" (no como en Pascal o Fortran, en donde comienzan en uno "1") en muchos casos existirá el hijo número cero (de hecho, el hijo izquierdo en un árbol binario es precisamente "Child(0)"). Sin embargo, el cero tiene la particularidad de que es el único número que es igual a su negativo, pues siempre es cierto que "0 == -0", por lo que el campo "_n_child" no podría contener un número negativo para el único hijo número cero. Por eso, en la implementación se almacena el valor "-n-1" o el valor "+n+1" en el campo "_n_child" dependiendo de si el nodo es o no el último en la lista de hijos del nodo padre. Esta particularidad también es la razón por la que el campo "_n_child" es un entero positivo "unsigned" para el árbol que usa un vector de punteros en sus nodos, como en la Figura 7, mientas que es un entero con signo "int" para los nodos hijo+hermano. El árbol con punteros descrito en este documento usa nodos definidos como se muestra en la parte derecha de la Figura 11, que es la declaración que corresponde al modelo de la Figura 9.

Funcionalidad del árbol   

      En las secciones anteriores la mayor parte de la discusión se hizo desde la óptica de la implementación, por lo que fue necesario usar la palabra "Nodo" muchas veces. Como ocurre con las listas de Lisp, es posible especificar el árbol sin usar el concepto de "Nodo", usando más bien sub-árboles, así como la listas Lisp están definidas en término de sus sub-listas. Por analogía con Lisp, un sub-árbol es una parte de un árbol.

      Lo más simple muchas veces es suficiente; afortunadamente, basta definir un sub-árbol como un objeto que contiene una referencia hacia el valor almacenado en la jerarquía que representa la raíz del sub-árbol. La diferencia principal entre árboles y sub-árboles es que los primeros nunca tendrán en su raíz una indicación de quien es su padre, pues por definición la raíz un árbol no tiene padre alguno, mientras que sí puede ocurrir que un sub-árbol descienda de algún nodo por lo que en ese caso su raíz tendría un padre no vacío.

      Una vez que se usa el concepto de "sub-árbol" en lugar del de "nodo" se puede prescindir completamente de los nodos, porque en lugar de manipular los nodos se puede manipular sub-árboles cuya raíz es el "nodo" (que ya no hace falta mencionar). Por eso, la especificación de la operación "Child(n)" dice que retorna el "n"-ésimo sub-árbol hijo, no que retorna un nodo. Desafortunadamente, al definir los árboles como referencias surge un problema adicional, pues hay que mantener un control de cuántas referencias existen para cada nodo del árbol. Habrá más de una referencia al mismo sub-árbol si, por ejemplo, para el mismo árbol se invoca más de una vez la operación "Child(n)".

      Los árboles son útiles porque, además de almacenar valores, lo hacen imponiendo una estructura que permite luego lograr eficiencia en muchos algoritmos. Por eso, es importante definir cuáles mecanismos existen para pasar de un valor almacenado en el árbol a otro, y cómo se usan esos mecanismos. Los iteradores lineales de la biblioteca STL estándar de C++ son bien conocidos [Mall-97], pero a fin de cuentas no reflejan la estructura no lineal de los árboles. Por eso, el mecanismo principal para recorrer un árboles es visitar al padre y a sus hijos mediante la invocación de los métodos "Father()" y "Child(n)".

      Los árboles son contenedores, por lo que deben incluir operaciones que permitan almacenar valores en el árbol. Para ésto hay que contar por lo menos con 2 mecanismos: uno para cambiar un valor individual y el otro para injertar sub-árboles completos. Para agregar o cambiar un valor en la raíz se usa "Change_Root(d)", y para hacer lo mismo en el "n"-ésimo hijo se usa "Change_Child(n,d)". El método "Graft(n,Ti)" sirve para agregar el sub-árbol "Ti" completo, como "n"-ésimo hijo de "T". Los métodos "Erase()" junto con "Erase_Son(n)" tiene el efecto inverso, pues eliminan el sub-árbol completo.

      Como ocurre con cualquier objeto, también para los árboles tiene sentido definir sus operaciones elementales de copia, impresión, etc. Al copiar un árbol, que es una referencia, lo que se copia es una referencia, y el resultado es una copia superficial de valores. Por eso la operación "Copy()" es una copia superficial, y si se necesita una copia profunda del árbol, hay que usar "Copy_Deep()". Como se usa semántica de referencia para implementar árboles, las operaciones para recorrer los valores almacenados en el árbol retornan un nuevo objeto sub-árbol cuando , como lo hace por ejemplo "Child(n)". Esas referencias no son los valores almacenados del árbol y en consecuencia al intercambiarlas, mediante el método "Swap()" o al copiarlas, mediante el método "Copy()", no se modifica los valores almacenados en el árbol. Para modificar los valores almacenados es necesario usar los métodos que realizan esa función, como lo son "Change_Root(d)", "Change_Child(n,d)" o "Graft(n,Ti)". Por eso, si se usa "Swap()" para intercambiar 2 árboles obtenidos mediante invocaciones a "Child(n)" no se logrará cambiar los valores de los árboles originales.

/** Convierte a "T" en su sub-árbol espejo, en el que recursivamente los hijos quedan en orden inverso del orden en el que aparecían originalmente en "T" a a /|\ /|\ / / \ \ / / \ \ b c d e e d c b /|\ /|\ /|\ /|\ f g h i j k k j i h g f / \ / \ l m m l / \ / \ n o o n */ void Mirror( Tree& T ) { if ( T.Empty() ) { return; // se sale si el árbol está vacío } Tree Child = T.Leftmost(); while ( ! Child.Empty() ) { // recursión para cambiar a todos los hijos Mirror( Child ); Child = Child.Right_Sibling(); } unsigned N = T.Rightmost_N(); Tree Ti, Tn_i; // [0] [1] [2] [3] [4] N == 4 unsigned i, Mid = (N+1) / 2; // i i < 2 == Mid ==> 2 == 4/2 == 5/2 for (i=0; i<Mid; ++i) { // Intercambia los hijos i <==> N - i Ti = T.Child( i ); Tn_i = T.Child( N - i ); T.Graft( i, Tn_i ); assert(( Ti.Empty() ? true : Ti.Father().Empty() )); T.Graft( N - i, Ti ); } }

// [0] [1] [2] [3] [4] N == 4 unsigned i, Mid = (N+1) / 2; // i i < 2 == Mid ==> 2 == 4/2 == 5/2 for (i=0; i<Mid; ++i) { // Intercambia los hijos i <==> N - i T.Child(i) . Swap ( T.Child( N - i ); } // \====/

Figura 12

      En la parte de arriba de la Figura 12 está la implementación de la función "Mirror(T)" que funciona porque recursivamente vuelve al revés a "T" y a todos sus sub-árboles.

      La Figura 12 es muestra de que es posible implementar algoritmos recursivos de manera natural cuando se usa el concepto de "Sub-Árbol" en lugar del de "Nodo". En ésto también ayudan las cualidades sintácticas del lenguaje C++, cuyos mecanismos de herencia y sobrecarga de nombres permiten escribir con naturalidad los algoritmos, sin sacrificar el ocultamiento de datos.

      El algoritmo "Mirror(T)" implementado en la Figura 12 también sirve para ver que es muy cómodo usar sub-árboles pues, para simplificar la implementación, dentro del ciclo "for" se usan los 2 sub-árboles temporales "Ti" y "Tn_i". Al principio del ciclo "for" el resultado de la asignación "Ti = T.Child(i)" es hacer que el valor de "Ti" sea un sub-árbol cuyos valores están almacenados como sub-árbol de "T", con lo que efectivamente "T" y "Ti" comparten sus valores almacenados (esto quiere decir que si se ejecutara la operación "Ti.Change_Root(d)" cambiaría tanto el valor de "Ti" como el de "T"). Después de la ejecución de la operación "T.Graft(i,Tn_i)" ya no hay valores comunes entre "T" y "Ti", pero sí ocurre que "Ti" mantiene los valores que fueron parte de "T". Por eso, pese a que la operación "T.Graft(i,Tn_i)" elimina "Ti" como sub-árbol de "T", en "Ti" quedan los valores que luego son intalados como el hijo número "N-i" gracias la la última operación del ciclo, operación "T.Graft(N-i,Ti)"

      Para intercambiar los sub-árboles de la posición "i" a "N-i" en "Mirror(T)" es necesario usar "Graft(n,Ti)" pues si se usara un simple "Swap()", como está en la parte de abajo de la Figura 12, el resultado sería intercambiar las nuevas referencias a los hijos de "T" que "Child(n)" retorna, pero eso no cambia los valores almacenados en "T". En otras palabras, el efecto de esa invocación a "Swap()" sería dejar el árbol "T" con su valor original, e intercambiar las referencias que contienen los sub-árboles temporales que las 2 invocaciones a "Child()" producirían, lo que no tiene efecto en el valor de "T".

      Después de que un estudiante logra comprender por qué es necesario usar "Graft(n,Ti)" en lugar del simple "Swap()", ya no tendrá dificultad en saber cómo funcionan los lenguajes que usan la semántica de referencia como mecanismo fundamental para manipulación de datos, como ocurre en los lenguajes Java y C#.

Especificación del árbol   

      Después de analizar la implementación del algoritmo "Mirror(T)" en la Figura 12 es natural deducir la especificación de cada una de las operaciones de la clase "Tree". La especificación completa de la clase fue obtenida usando el sistema de documentación Doxygen [VANH-2004]. La especificación para la clase "TL::Tree" que corresponde a la implementación "Tree_V.h" del nodo con un vector de punteros es un poco más restringida que la especificación para la clase "TL::Tree" en donde se usa una lista de hijos en, cuya implementación está en "Tree_L.h". Ambos documentos han sido generados con Doxygen.

      Casi todas las especificaciones para las operaciones del árbol son exactamente iguales, independientemente de la implementación. Sin embargo, sí hay una diferencia entre ellas, pues en la implementación que usa el vector de punteros, que se encuentra en el espacios de nombres (namespace) "TV", existe una cota superior para la cantidad de hijos para un nodo, que es el valor de "TV::Tree::N". Por ejemplo, en la especificación de "TV::Tree::Graft(n,o)" es necesario que "(n < Tree::N)", mientras que en el método homónimo "TL::Tree::Graft(n,o)" esta restricción es innecesaria. En la práctica ocurre que las cualidades de una implementación son el factor decisivo para usar una clase.

      Desde el punto de vista de la flexibilidad de uso, es más cómodo usar el árbol del espacio de nombres "TL" que el de vectores, para evitar la preocupación de controlar que siempre se cumplan las restricciones impuestas en cada una de las especificaciones de los métodos de la clase. A menos que sea de primordial importancia mantener un tiempo de acceso constante hacia los hijos, pues la complejidad de la operación "TL::Tree::Child()" es O(Father().Child_Count()) mientras que la de "TV::Tree::Child()" es O(1), es mejor usar la implementación "TL::Tree" que la otra, porque es menos restrictiva. Si además se sabe que cada árbol tendrá relativamente pocos sub-árboles, en general será mejor idea usar aquella implementación que le brinde mayor flexibilidad de uso al programador cliente. La referencia completa para las clases "TV::Tree" y "TL::Tree" está disponible aquí: está disponible aquí:

TV::Tree → Tree_V.h:

http://www.di-mare.com/adolfo/p/TreeTdef/classTV_1_1Tree.html

TL::Tree → Tree_L.h:

http://www.di-mare.com/adolfo/p/TreeTdef/classTL_1_1Tree.html

      Esta abstracción se ha escogido porque permite definir sobre ella la mayor parte de las operaciones importantes asociadas con árboles. En este sentido, esta abstracción es muy "general", lo que tiene gran utilidad didáctica. También sirve para representar un árbol binario, que es muy utilizado en artículos y libros de texto. A un estudiante le sirve para comprender el concepto de árbol, para que luego pueda estudiar las estructuras de datos que apoyan a los algoritmos que usan árboles para lograr gran eficiencia.

class Bin_Tree { Node * _root; public: struct Node { Node *_left, *_right; value_type _data; }; friend void Print0( Node * ); void Print() { Print0(_root); } };

// Print0() trabaja con nodos // - No trabaja con el árbol void Print0( Bin_Tree::Node *p) { if (p != 0) { Print0( p->_left ); cout << p->_data << ' '; Print0( p->_right ); } }

Figura 13

      Como se muestra en la implementación de la función "Mirror()" en la Figura 12, las clases "TV::Tree" y "TL::Tree" facilitan la escritura de algoritmos recursivos que manipulan la estructura del árbol, sin importar cuál es su contenido, porque el acoplamiento entre los valores almacenados y el contenedor es muy bajo. Tradicionalmente, los algoritmos recursivos que trabajan con árboles tienen que ser implementados en 2 partes, en donde hay un procedimiento externo que recibe parámetros de tipo "árbol" y luego invoca un procedimiento recursivo que realmente realiza el trabajo, y como argumento se le envía un puntero al nodo raíz del árbol, como se muestra en Figura 13 con la función "Print0()" y el método "Bin_Tree::Print()". Esta forma de proceder no es conveniente porque induce al programador cliente a usar los campos privados del objeto, y así violentar el ocultamiento de datos que es el mecanismo que se usa para evitarle al programador cliente conocer cómo está implementado un módulo de programación. La abstracción definida aquí permite implementar la función "Print()" en término de sub-árboles, y sin usar una rutina intermedia como "Bin_Tree::Print()" cuyo único trabajo es invocar al procedimiento recursivo que realiza el trabajo.

      Una gran ventaja de esta especificación es que permite usar la funcionalidad característica de un árbol, pues permite manipular información organizada jerárquicamente, pero evita el uso de punteros, que tanta dificultad representan para la mayor parte de los programadores.

class Bin_Tree : public Tree { private: Tree Child( unsigned n ) { } // bloquea acceso al n-ésimo hijo Tree Graft( unsigned n, Tree & o ) { } // ídem public: Bin_Tree Graft_Left( Tree & o ) { return Tree::Graft(0, o); } // "0" es el izquierdo Bin_Tree Graft_Right( Tree & o ) { return Tree::Graft(1, o); } // "1" es el derecho // ... };

Figura 14

      Es relativamente sencillos obtener una clase de árboles binarios, si se deriva directamente de cualquiera de las clases "TV::Tree" o "TL::Tree" la nueva clase "Bin_Tree", para la que basta ocultar algunas de las operaciones para árboles más generales, como por ejemplo "Tree::Child()", como se muestra en la Figura 14. De esta manera la mayor parte de los métodos están definidos para "Tree" por lo que están disponibles por herencia para la clase "Bin_Tree", salvo unos pocos que requieren de una implementación diferente.

      Lograr que la implementación esté separada de la especificación es un objetivo primordial cuando se construyen programas usando abstracción [Gur-95]. La mejor muestra de que ese objetivo se ha logrado para las 2 implementaciones del árbol que se presentan aquí es la biblioteca de rutinas "Tree_Ex.h" que funciona correctamente con ambas implementaciones.

El concepto de árbol   

      La cantidad de operaciones que tiene la clase "Tree", es muy grande, pues incluye todas las operaciones que deben ser incluidas. Sin embargo, en la mente de las personas no son todas las operaciones las que identifican a la una clase.

\ |___ | | ^ ^

Figura 15

      La Figura 15 es una silla. No es una silla bonita, pero ti tiene su sentadera, sus paticas y el respaldar. Este dibujo es una abstracción del concepto silla, pues "abstraer" significa "Separar las cualidades de un objeto para considerarlas aisladamente o para considerar el mismo objeto en su pura esencia o noción". Cuando se habla de una pila en programación, el programador usuario entiende que se habla de un contenedor que tiene 2 operaciones principalísimas: "Push()" y "Pop()". En la biblioteca STL las pilas son parte de todos los contenedores, porque casi todos tienen las operaciones "push_front()" y "pop_front()". De hecho, la plantilla "stack<>" funciona porque estas operaciones están bien definidas para los otros contenedores. Lo mismo ocurre con las colas y sus operaciones "Enqueue()" y "Dequeue()". Por eso es importante definir cuáles son las operaciones "principalísimas" para la clase "Tree".

Child(n)	Acceso al "n"-ésimo hijo	TL	TV
operator * ()	Acceso al valor almacenado en la raíz	TL	TV
Change_Root(d)	Sustituye por "d" el valor almacenado en la raíz	TL	TV
Erase()	Elimina el árbol y sus descendientes	TL	TV
Father()	Acceso al padre	TL	TV
Graft(n,Ti)	Injerta "Ti" como "n"-ésimo hijo	TL	TV

Figura 16

      En la Figura 16 están las operaciones principales de un árbol. En muchas ocasiones se usa un concepto de árbol que no incluye las operaciones "Graft(n,Ti)" y "Father()" porque muchas veces las implementaciones sólo tiene un puntero a los hijos, como ocurre con los árboles binarios de la Figura 2. Puede ocurrir también que se hable de "Erase_Son(n)" en lugar de "Erase()" para es frecuente no incluir el puntero al padre que hay que usar al implementar "Erase()". Aunque la operación más compleja es "Graft(n,Ti)", la más importante es "Child(n)", que es la que permite llegar a los hijos desde el padre, pues casi siempre se usa un árbol porque se necesita este tipo de acceso. Desde el punto de vista más general, con los árboles ocurre algo similar a lo que ocurre en las listas, en las que la operación principal es avanzar hacia el siguiente nodo invocando "List::Next()".

      ¿Tiene sentido usar árboles que no tengan alguna de las operaciones de la Figura 16? Esta es una pregunta teórica, pues en la práctica los árboles son "nodos" que almacenan un valor y que están "conectados" a sus hijos derecho e izquierdo, pues casi siempre lo que se usa es un árbol binario como el de la Figura 2. Siendo así las cosas, y debido a que no es usual incluir un puntero al padre, que es lo que permite implementar con relativa eficiencia la operación "Graft()", se puede decir que la abstracción aquí descrita no concuerda con lo que se usa en muchos libros de texto. Pero si es válido alzar la conjetura de que, junto con el desarrollo de la tecnología y el conocimiento, poco a poco esta abstracción del árbol será más utilizada.

El elemento contenido en el árbol   

      Debido a que la clase árbol es una clase contenedora, tiene mucho sentido implementarla usando plantillas. Debido a que las 2 implementaciones que se muestran aquí tienen fines didácticos más que industriales, en esta implementación se ha usado el truco del "Tdef.h" para la enseñanza de plantillas C++ descrito en [DiM-2004].

      Para lograr obtener un árbol que contiene números enteros, hay que editar el archivo "Tdef.h" para definir ahí el tipo "Elem_Type" como un número entero, pues "Elem_Type" es el elemento contenido en el árbol (este tipo se usa para definir "Tree::value_type" en ambas implementaciones). La forma más simple de definir "Elem_Type" es incluir esta línea de código en "Tdef.h":
      "typedef int Elem_Tree;" // Definición en "Tdef.h"

#include <complex> // números complejos STL using namespace std; class rotation : public complex<double> { // ... }; #define Tdef_h_incluido // Evita que se use el archivo Tdef.h al compilar Tree typedef rotation Elem_Tree; // Tipo usado como elemento contenido al simular plantillas #include "Tree_Ex.h"

Figura 17

      Figura 17 se muestra otra forma de definir el tipo "Elem_Tree" que se necesita para que compilar el árbol, en cualquiera de sus 2 implementaciones. Al definir la variable del preprocesador "Tdef_h_incluido" se evita incluir el archivo "Tdef.h". pues al principio del archivo "Tree_L.h y de "Tree_V.h se encuentran las siguientes directivas para el procesador:
    #ifndef Tdef_h_incluido
        #include "Tdef.h"
    #endif
que evitan incluir el archivo "Tdef.h" cuando ya está definida la variable "Tdef_h_incluido". El código de la Figura 17 deja definido el tipo "Elem_Tree" como la clase "rotation", y además se evita que al compilar el árbol el tipo "Elem_Tree" sea redefinido. También es necesario cambiar el siguiente renglón en "Tree_Ex.h":
      #include "Tree_L.h" // o "Tree_V.h"
pues es el archivo "Tree_Ex.h" el que incluye a "Tree_L.h" o a "Tree_V.h".

Detalles de implementación   

      Talvez la exposición en este artículo debiera haber comenzado por lo más abstracto, para llegar al final a lo más concreto. Sin embargo, los programadores aprendemos como los niños: de lo concreto a lo abstracto. Por eso, con frecuencia partimos de una implementación para luego obtener la abstracción que le corresponde. El último paso es definir el trabajo realizado, escribiendo la documentación de la especificación (en lo que afortunadamente ayuda mucho contar con herramientas como Doxygen que extraen las especificaciones del código fuente). Después de todo, la razón para usar abstracción es construir programas, lo justifica el enfoque aquí usado.

      En general la parte más compleja en la implementación es la manipulación de punteros, pues un pequeño descuido puede resultar en un puntero roto, que en general tiene efectos impredecibles en el programa. Precisamente por lo difícil que es manipular punteros se justifica usar clases y módulos, que permiten encapsular el uso de punteros en una sección aparte de la implementación, para facilitar la depuración independientemente del resto del programa.

      Mantener las cuentas de referencia en el campo "_refCount" es una tarea difícil, pues es muy fácil perder la cuenta cuando se construyen y destruyen objetos. La ventaja de usar cuentas de referencia es que facilita mucho la copia de objetos, pues el método "Copy()" sólo tiene que copiar un puntero y aumentar un contador. Debido a la complejidad de estas 2 implementaciones, definitivamente para un estudiantes es provecho conocer cómo se manipulan por doquier las cuentas de referencia "_refCount", cuyo uso contribuye a posponer la destrucción de objetos hasta que todavía están en uso.

      Respecto del uso de cuentas de referencia cabe hacer una digresión importante. Los programadores C++ con frecuencia alimentan el mito de que C++ es un lenguaje más "rápido" o "eficiente" que otros lenguajes más modernos, como lo son Java o C#. Sin embargo, si los árboles acá descritos hubieran sido implementados en alguno de esos 2 lenguajes, seguramente tendrían un mejor desempeño que la versión C++, pues Java y C# usan un recolector de basura que funciona cuando se requiere, o sea, que se activa cuando se agota la memoria dinámica. Debido a que los computadores ahora tienen cantidades enormes de memoria, ese evento es relativamente raro, por lo que la versión C++ requeriría más tiempo de ejecución porque cada ves que se hace una copia en C++ es necesario también incrementar o decrementar los contadores de referencia "_refCount", lo que no ocurre en las implementaciones Java o C#. En otras palabras, la estrategia C++ para recuperar memoria dinámica es muy avara (greedy), y esa política no siempre da buenos resultados: C++ cuenta los centavos mientras que los otros sólo se ocupan de los millones.

      La especificación de "Copy()" y de las otras operaciones de copiado retorna una referencia "Tree&" en lugar de un nuevo objeto de tipo "Tree" por razones puramente de eficiencia, pues en el contexto en que esas operaciones se pueden usar no existe el problema de que el uso de la referencia cause un efecto colateral indeseado. Si en la implementación no fuera necesario usar el contador de referencias "_refCount", estos métodos retornarían un nuevo objeto "Tree" por eso es más sencillo. Este es un ejemplo en donde la búsqueda de la eficiencia en la implementación tiene un impacto en la especificación.

      Definitivamente, en ambas implementaciones la operación más compleja es "Graft()", pues la manipulación de punteros que requiere es muy intrincada. Esta operación es el centro de la implementación. Como generalmente es más fácil manejar vectores que punteros, es natural que la implementación de "TV::Graft()" sea mucha más sencilla que la de "TL::Graft()", pues es la versión de listas es necesario usar el método privado intermedio "Erase_Son_Prev()" que tiene una estructura de funcionamiento muy compleja.

      Es curioso, pero la función "Mirror()" de la Figura 12 no es idempotente, pues al aplicarla 2 veces consecutivas no siempre se obtiene el mismo árbol original, pues la rotación de los hijos se hace intercambiando el hijo "int(0)" con el número "Rightmost_N()", por lo que si hay 2 hijos, "[1+9]" por ejemplo, al sacar el espejo la primera vez quedarán numerados "[0+8]", y luego quedarán numerados "[0+8]" de nuevo, y se perderá la numeración original "[1+9]".

      El programa "TTree.cpp" puede ser muy útil para determinar cuál es el funcionamiento de cada operación, pues en muchos casos se usar la macro "assert()" para verificar el resultado correcto de la ejecución de cada operación.

Conclusión   

      Hasta hace pocos años en los cursos intermedios de programación se usaban las listas para mostrar los conceptos de abstracción y especificación para los construcción de programas por módulos. Debido a que ahora ya existen muchas bibliotecas completas de contenedores lineales [Mall-97] , conviene usar el objeto contenedor árbol como instrumento didáctico para enseñar técnicas avanzadas de programación. La implementación que aquí se presenta es un paso en esa dirección.

      La preferencia hacia C++ como lenguaje en el segundo curso de programación se justifica por sus cualidades para abstracción y especificación [BLW-2001]. La aparente eficiencia de C++ no lo es tal en situaciones prácticas, en las que lenguajes más simples como C# o Java pueden ser una mejor alternativa; de hecho, mantener las cuentas "_refCount" correctas aumentan la dificultad de estas 2 implementaciones en C++. Se justifica continuar usando C++ sólo en cursos en donde la eficiencia es un objetivo central, como en Análisis de Algoritmos o Sistemas Operativos.

Agradecimientos   

      La profesora Gabriela Marín contribuyó con facilidades bibliográficas. El estudiante Alejandro Di Mare hizo varias observaciones y sugerencias importantes para mejorar este trabajo.

Bibliografía   

Código fuente   

Archivo	Descripción	Texto	Doxygen
Tdef.h	Archivo para simular plantillas http://www.di-mare.com/adolfo/p/TreeTdef/Tdef.h	.txt	.html
Tree_Ex.h	Algunas funciones de ejemplos de uso de la clase Arbol http://www.di-mare.com/adolfo/p/TreeTdef/Tree_Ex.h	.txt	.html
Tree_L.h	Declaraciones y definiciones para la clase Arbol [Lista] http://www.di-mare.com/adolfo/p/TreeTdef/Tree_L.h	.txt	.html
Tree_V.h	Declaraciones y definiciones para la clase Arbol [Vector] http://www.di-mare.com/adolfo/p/TreeTdef/Tree_V.h	.txt	.html
TTree.cpp	[T]est[Tree].cpp ==> Ejemplos de uso de la clase Arbol http://www.di-mare.com/adolfo/p/TreeTdef/TTree.cpp	.txt	.html
Tree.vcproj	Compilación VC++ v7 http://www.di-mare.com/adolfo/p/TreeTdef/Tree.vcproj	.txt	.vcproj
TreeTdef.dxg	Configuración Doxygen [v 1.3.9.1] http://www.di-mare.com/adolfo/p/TreeTdef/Tree.dxg	.txt	.dxg

Documentación Doxygen → http://www.di-mare.com/adolfo/p/TreeTdef/index.html
ftp://ftp.stack.nl/pub/users/dimitri/doxygen-1.3.9.1-setup.exe
Fuentes completos → http://www.di-mare.com/adolfo/p/TreeTdef/TreeTdef.zip

Indice   

[-]	Resumen
[1]	Introducción
[2]	El árbol de nodos
[3]	El árbol hecho con base en la lista
[4]	Funcionalidad del árbol
[5]	Especificación del árbol
[6]	El concepto de árbol
[7]	El elemento contenido en el árbol
[8]	Detalles de implementación
[9]	Referencia de la Clase TL::Tree
[10]	Referencia de la Clase TV::Tree
[-]	Conclusión
[-]	Agradecimientos
[-]	Código fuente
	Bibliografía
	Indice
	Acerca del autor
	Acerca de este documento
	Principio Indice Final

Acerca del autor   

Adolfo Di Mare <adolfo@di-mare.com>

Acerca de este documento   

Referencia:	Di Mare, Adolfo: Una clase C++ completa para conocer y usar árboles , Reporte Técnico ECCI-2004-03, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, http:// www.di-mare.com /adolfo/p/ TreeTdef.htm, Diciembre 1997.
Internet:	http://www.di-mare.com/adolfo/p/TreeTdef.htm
Autor:	Adolfo Di Mare <adolfo@di-mare.com>
Contacto:	Apdo 4249-1000, San José Costa Rica Tel: (506) 207-4020       Fax: (506) 438-0139
Revisión:	ECCI-UCR, Febrero 2006
Visitantes: