                  La Implementacin de Tree.pas

                               por

                          Adolfo Di Mare

                    Reporte Tcnico ECCI-94-07
                       Proyecto 326-93-256
                           Revisin 1.0


Resumen:
=======

Se  discute cmo est construida  la implementacin del ADT TTree, 
que  corresponde  a una  abstraccin del  Tipo Abstracto  de Datos 
(ADT)  TTree  muy  general,  que  subsume  a  la  mayora  de  las 
abstracciones definidas en los libros de texto.  La implementacin 
se ha realizado  para el ambiente  Turbo Pascal v5.0,  aunque para 
trabajar con ella es  ms  cmodo  usar  la  versin  v6.0  o  una 
posterior.

Tree.pas  es   una  implementacin   muy  completa   pues  incluye 
comportamientos  que  le permite  insertar en  el contendor  tanto 
elementos como punteros a elementos.  Por eso es que el manejo  de 
memoria  dinmica que se necesita  en esta implementacin tiene un 
gran valor didctico.


Abstract:
========

We discuss  how the  implementation for  TTree Abstract  Data Type 
(ADT)  is constructed.   This implementation correspond  to a very 
general  TTree  abastraction  which  subsumes  most   abstractions 
defined in text books.  This implementation has been made for  the 
Turbo  Pascal v5.0 environment, even  though it is less cumbersome 
to use version v6.0 or later to work with it.

Tree.pas, is a very  complete implementation, because it  included 
the capability to  insert in the  container ADT both  elements and 
pointer to elements.   This is why  the dynamic memory  management 
needed in this implementations has a great didactic value.


Esta investigacin se realiz dentro del proyecto de investigacin 
326-93-256 "DBgen: Generacin de Sistemas  a partir de su Base  de 
Datos" inscrito ante  la  Vicerrectora  de  Investigacin  de  la 
Universidad  de  Costa  Rica.   La  Escuela  de  Ciencias   de  la 
Computacin e Informtica tambin ha aportado fondos para realizar 
este trabajo.


                  La Implementacin de Tree.pas
                  =============================


     Una clasificacin  simple de  los Tipos  Abstractos de  Datos 
(ADTs) los divide en dos tipos bsicos: los simples o elementales, 
y  los contenedores. Un  ADT es un contenedor  si contiene a otros 
ADTs. Los contenedores ms importantes son tres:

     1.- El ADT Arreglo [ARRAY]
     2.- El ADT Lista   [List.pas]
     3.- El ADT Arbol   [Tree.pas]

Existen   otros   ADTs  importantes,   como  Heap.pas,   Poly.pas, 
Matriz.pas,  etc,  pero  la  mayora de  las estructuras  de datos 
importantes se obtienen al combinar inteligentemente a estos  tres 
ADTs.   De todos estos, el ms  importante es, sin duda alguna, el 
Arreglo, hasta el punto de que todos los lenguajes de  computacin 
modernos lo incluyen como una construccin sintctica bsica.

     Aunque  el ADT  Arbol no es  tan importante com  la Lista, es 
didcticamente  conveniente  estudiarlo  por  lo  menos  por   las 
siguientes tres razones:

1) La especificacin del ADT TTree parece simple a primera  vista, 
   pero en la prctica es  bastante complicada, por lo que  cuando 
   el estudiante logra entenderla entonces aprende en detalle cmo 
   debe disear e implementar sus Tipos Abstractos de Datos.

2)_Esta   implementacin   usa   al   contenedor   TList   en   su 
   implementacin,  lo  que le  muestra al  estudiante como  crear 
   nuevas estructuras de datos con base en las existentes.

3) Dada la complejidad de esta implementacin, el estudiante tiene 
   la  oportunidad de  comprender cules son  las limitaciones que 
   tiene el uso de Tipos Abstractos de Datos para la  construccin 
   de programas sofisticados.

     El  ADT  rbl es  el contenedor  que sirve  para representar 
jerarquas  en  el computador.   Un rbol  T contiene  un conjunto 
finito de  elementos  organizados  de  acuerdo  a  las  siguientes 
propiedades:

a) T es un conjunto finito, o vaco,  de elementos  almacenados en 
   "nodos" [Empty(T)].

b) Los nodos del rbol estn conectados unos a otros por medio  de 
   aristas o enlaces.

c) Un rbol no vaco siempre tiene un nico nodo llamado la "raz" 
   del  rbol,  del que  todos los  dems nodos  son descendientes 
   [Root(T)].

d) Cada nodo en el rbol,  excepto el  nodo raz,  tiene un  nico 
   nodo del que desciende directamente. Ese nodo es el nodo  padre 
   [Father(T,n)].


e) Dos  nodos  que  tienen  el  mismo  padre  se  llaman  hermanos 
   [Sibling(T,n,i)].

f) Los  descendientes  de  un  nodo  siempre  estn  ordenados  de 
   izquierda a derecha [Child(T,n,i)].

g) Los  nodos que  no tienen  descendientes se  llaman nodos  hoja 
   [Leaf(T,n)].

h) La  longitud del  camino que  separa a  un nodo  de la  raz se 
   conoce como su "profundidad" [Depth(T,n)].

i) La longitud del camino ms largo desde un nodo a alguno  de sus 
   descendiente es la altura del nodo [Height(T,n)]. La altura del 
   rbol es la altura de su raz.

j) Entre cualesquiera dos nodos del rbol siempre existe  un nico 
   camino que los une.

     En el siguiente diagrama se muestra un rbol:


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

     Para definir  el rbol  como un  Tipo Abstracto  de Datos  es 
necesario distinguir  entre un  nodo del  rbol, el  contenido del 
nodo y su posicin  en el rbol.  En  este diagrama los nodos  son 
las cajitas ([a]...[m]) que estn ligadas en orden jerrquico,  el 
contenido  de cada  nodo es lo  que aparece dentro  de cada cajita 
("a".."m"),  y la  posicin de cada  nodo es un  apuntador al nodo 
(@[a]=p).  Por  ejemplo,  la  posicin  del  nodo  raz  es  @[a]; 
p=@[a]=Root(T).

     Para  no cargar  mucho la notacin,  en este documento  no se 
hace distincin entre un nodo del rbol y su contenido, por lo que 
en lugar de hablar  de "la  posicin del  nodo raz  del rbol  T" 
simplemente se dice que  p=@a=Root(T), o sea que  la raz de T  se 
denota con @a: la notacin "@" sirve para distinguir al valor  del 
nodo de su posicin en el rbol.  Esta notacin es ambigua pues no 
permite representar un rbol en que dos o ms de sus nodos  tienen 
el mismo valor, aunque es ms  cmoda de usar.  De acuerdo a  esta 
convencin, el diagrama del rbol T es el siguiente:

                                T
                                
                                a
                               /|\
                             / / \ \
                            b  c d  e
                           /|\     /|\
                          f g h   i j k
                                   / \
                                   l m

     Como  se muestra en  el diagrama de T,  este rbol cumple con 
las siguientes propiedades del ADT TTree:

- T no est vaco: Empty(T) = FALSE.

- La raz de T es el nodo que contiene "a": @a=Root(T).

- El nodo que contiene a "b" tiene tres descendientes: (f, g,  h). 
  @b = Father(T,@f) = Father(T,@g) = Father(T,@h).

- (f,  g,  h)  son  nodos hermanos,  pues todos  son descendientes 
  directos de "b":
    @f = Sibling(T,@g,-1) = Sibling(T,@h,-2) = Sibling(T,@f, 0)
    @g = Sibling(T,@f, 1) = Sibling(T,@h,-1) = Sibling(T,@g, 0)

- Los descendientes del nodo que contiene "b" son (f, g, h):

    @f = Child(T,@b,1)  @g = Child(T,@b,2)  @h = Child(T,@b,3)

- Los nodos hoja de T son (f, g, h, c, d, i, l, m, k):

    Leaf(T,@f) = f-...-k = Leaf(T,@k) = TRUE
    Leaf(T,@a) = a-b-e-j = Leaf(T,@j) = FALSE

- La  profundidad  del  nodo  raz siempre  es cero.  Siempre debe 
  existir un nodo hoja cuya profundidad sea la altura del rbol:

    0 = Depth(T,@a) =  Depth(T,Root(T))
    1 = Height(T,@b) = 1 + Height(T, Child(T,@b,1))
    3 = Height(T,Root(T)) = Height(T, @a) = Depth(T, @m)


Abstraccin de TTree
====================

     Para  almacenar un rbol en  el computador es necesario crear 
una  abstraccin  del  concepto  "rbol", la  que luego  puede ser 
cristalizada en  la implementacin  del ADT  rbol.  Para  definir 
esta abstraccin es necesario definir los elementos que forman  un 
rbol:

     1) Nodos
     2) Valor almacenado en cada nodo    [Unidad Elem.pas]
     3) Posicin en el rbol
     4) Aristas de enlace entre nodos.

     En  la  implementacin, a  cada uno  de estos  conceptos debe 
corresponder un tipo de datos o un campo en una instancia. En esta 
implementacin, la correspondencia es la siguiente:

     1) Nodo       Tipo    TNode_RepTree  Tree.pas
     2) Valor      Tipo    TElem          Elem.pas
     3) Posicin   Tipo    PTpos          Tree.pas
     4) Arista     Campo   punteros       Tree.pas

     Es  importante   destacar  que   existen  muchas   formas  de 
implementar  el ADT  rbol, cada una  de las que  tiene diferentes 
ventajas  que en general comportan  una mejora de rendimiento para 
realizar una o varias de las operaciones.  Por ejemplo, en algunas 
implementaciones no  es  necesario  representar  directamente  las 
aristas,  pues con base  en la posicin relativa  de los nodos del 
rbol se puede deducir cuales  son los enlaces entre nodos.   Este 
hecho  se  usa  en  la implementacin  del ADT  THeap, que  es una 
elegante estructura de datos para representar rboles.

     Para incrementar la modularidad del ADT, la implementacin de 
TTree consta  de  dos  unidades  Pascal.   La  primera,  Tree.pas, 
contiene todo el cdigo que implementa al ADT Arbol. La segunda es 
la unidad llamada  Elem.pas, que tiene  todas las operaciones  del 
ADT elemental contenido en el rbol. Este ADT elemental puede ser, 
a su vez, otro contenedor. El ADT rbol puede contener a cualquier 
otro  ADT para el que  estn definidas las operaciones elementales 
que usa Tree.pas para manipular a Elem.pas.

     Para adaptar  el rbol  a diferentes  ADTs elementales  basta 
cambiar el nombre del ADT elemental  usado en el rbol, lo que  se 
puede hacer con relativa facilidad usando un editor de texto  para 
modificar el programa  fuente  Tree.pas.   Para  facilitarle  este 
trabajo al programador usuario de TTree, en el mdulo Tree.pas hay 
un recuadro llamado  PARAMETERS  que  tiene  los  nombres  de  los 
identificadores que es necesario cambiar si el elemento  contenido 
en el rbol no se llama "Elem".

     El concepto de rbol en Computacin es muy amplio, por lo que 
a veces no queda bien definido.  Por ejemplo, en un rbol  binario 
siempre  es posible  que un nodo  tenga un hijo  derecho aunque no 
tenga en el  hijo  izquierdo;  la  abstraccin  de  rbol  que  se 
presenta aqu no podra distinguir en un rbol si el nico hijo de 
un nodo es un nodo derecho o izquierdo.

     Esta abstraccin se ha escogido porque permite definir  sobre 
ella  la mayor parte de  las operaciones importantes asociadas con 
rboles.   En este sentido, esta  abstraccin es muy "general", lo 
que  tiene  gran  utilidad  didctica.   Pero  como  se   mencion 
anteriormente,  tiene  tambin sus  restricciones: no  es sencillo 
representar  un rbol binario usando  TTree.  Lo importante es que 
le sirve al estudiante para comprender el concepto de Arbol,  para 
que luego pueda estudiar las estructuras de datos que apoyan a los 
algoritmos que usan rboles para lograr gran eficiencia.


Operaciones
===========

     Como  ocurre cuando  el programador usa  a la mayora  de los 
ADTs contenedores, las operaciones sobre el rbol deben permitirle 
definir sobre cul de todos los nodos del rbol desea actuar. Para 
definir una posicin en el rbol se usa el tipo de datos PTpos.

     Una variable de tipo PTpos es  un puntero a uno de los  nodos 
del rbol.   Como  este  tipo  est  definido  como  parte  de  la 
abstraccin del ADT rbol, entonces un PTpos es puntero Pascal que 
no puede ser  derreferenciado.   Esto  quiere  decir  que  si  una 
variable  "p" es  de tipo PTpos,  entonces nunca puede  ser vlido 
manipular aquello a lo que apunta:

     VAR
       p : PTpos;
     ...
     p^ := ....;   {  ERROR !!! }
     FunProc(p):   { OK }

     El ADT rbol tiene todas las operaciones de un ADT elemental. 
Estas operaciones son las siguientes:

     Init(T):     Constructor; inicializa el rbol.
     Clear(T):    Limpia al rbol.
     Done(T):     Destructor; destruye al rbol.

     Copy(x,y):   Copia el valor del rbol "y" en "x".
     Move(x,y):   Le traslada a "x" el valor del rbol "y".

     Equal(x,y):  Compara el valor de "x" con el de "y".
     Less(x,y):   Compara el valor de "x" con el de "y".

     Load(T,F):   Carga el valor de "T" desde el archivo "F".
     Store(T,F):  Almacena el valor de "T" en el archivo "F".

     OK(T):       Verifica la invariante del ADT.
     Fix(T):      Repara rboles.

     Adems estn implementadas todas las operaciones con las  que 
siempre cuenta un ADT contenedor:

     Empty(T):        Verifica si el rbol est vaco.
     Count(T):        Cantidad de elementos del rbol.

     Behave(T,b,sw):  Cambia el comportamiento del rbol.
     Behaviour(T,b):  Verifica si "T" tiene el comportamiento "b".

     Retrieve(T,p):   Transforma una posicin en puntero al valor.
     Locate(T,x):     Busca un valor en el rbol.
     Valid(L,p):      TRUE si "p" es una posicin de T.

     La operacin  Retrieve(T,p)   retorna  un  puntero  al  valor 
almancenado en uno de los nodos del rbol "T".  Esta operacin  es 
muy importante porque es la que separa al contenedor, que en  este 
caso es el  ADT  TTree,  de  su  elemento  contenido,  TElem.   La 
existencia  de esta operacin se  justifica porque muchas veces el 
programador  necesita   escribir  algoritmos   que  manipulan   la 
estructura del rbol, sin importar cul es su contenido.  Como  en 
esta  abstraccin  se separa  la estructura  del rbol  de lo  que 
contiene, entonces los algoritmos que slo manipulan la estructura 
del rbol no necesitan ser reprogramados cuando se cambia el  tipo 
de valor almacenado  en el rbol:  la operacin Retrieve(T,p)  los 
independiza de ese valor.

     Si, por el contrario,  el programador necesita manipular  los 
valores  de los elementos almacenados  en el rbol, entonces puede 
accesarlos en dos pasos: primero debe obtener la posicin "p"  del 
nodo  del rbol,  y luego puede  obtener el valor  del nodo usando 
Retrieve(T,p).

     Las  operaciones  arriba descritas  son comunes  a todos  los 
contenedores. Lo que realmente define  al ADT rbol son las  dems 
operaciones,  las que  pueden ser ejecutadas  eficientemente en la 
estructura de datos del rbol.  La operacin para agregar nodos al 
rbol, al insertarle valores, es Insert().

     Insert(T,p,i,e)  inserta al elemento "e"  de forma que sea el 
i-simo hijo del nodo cuya posicin  en el rbol "T" es "p".   Por 
ejemplo,  para agregarle el nodo "x"  como segundo hijo de la raz 
de "T" se debe invocar a Insert() de la siguiente forma:

                   T                              T
                      Insert(T, Root(T), 2, x)   
                   a                              a
                  /|\                            /|\\
                / / \ \                        / /| \\
               b  c d  e                      b x c d e
              /|\     /|\                    /|\     /|\
             f g h   i j k                  f g h   i j k
                      / \                            / \
                      l m                            l m

     Con  la operacin  Insert()  es posible  insertarle una nueva 
raz  al rbol;  para esto hay  que especificar la  posicin nula, 
Tree.Null, como segundo argumento de Insert():
- Insert(T, Tree.Null, x, 0): inserta "x" como nueva raz de "T".

     Todos  los elementos que se le  agregan a un rbol siempre se 
agregan en nodos  hoja.  No es  posible insertar a  un nodo en  un 
lugar que no sea la  hoja. La operacin Graft() permite  trasladar 
rboles completos.

     Graft(T1,p,i, T2) es una operacin que complementa a Insert() 
pues  toma el rbol T2 y lo  inserta como el i-simo hijo del nodo 
"p" de T1.


                                   Graft(T1, @e, 2, T2)
           T1         T2                    T1            T2
                                                     <vaco>
           a          j                     a
          /|\        / \                   /|\
        / / \ \      l m                 / / \ \
       b  c d  e                        b  c d  e
      /|\     / \                      /|\     /|\
     f g h   i   k                    f g h   i j k
                                               / \
                                               l m

     Para manipular al rbol el programador necesita poder obtener 
la posicin de los nodos del rbol.  Las operaciones que  retornan 
posiciones en el rbol son:

     Root(T):        Retorna la posicin de la raz del rbol.
     Father(T,p):    Padre del nodo cuya posicin es "p".
     Child(T,p,i):   i-simo hijo de "p" en "T" (i>0).
     Sibling(T,p,i): i-simo heramano de "p".

     Estas  operaciones  le permiten  al progamador  moverse a  lo 
largo  y ancho del rbol.   Generalmente el recorrido comienza por 
la raz, aunque  tambin puede usarse  Locate() para encontrar  un 
nodo especfico en el rbol.

                                T
                                
                                a
                               /|\
                             / / \ \
                            b  c d  e
                           /|\     /|\
                          f g h   i j k
                                   / \
                                   l m

     @a = Root(T)

     @b = Father(T,@f) = Father(T,@g) = Father(T,@h)

     @f = Sibling(T,@g,-1) = Sibling(T,@h,-2) = Sibling(T,@f, 0)
     @g = Sibling(T,@f, 1) = Sibling(T,@h,-1) = Sibling(T,@g, 0)
     @h = Sibling(T,@f, 2) = Sibling(T,@g, 1) = Sibling(T,@h, 0)

     @f = Child(T,@b,1)
                        @g = Child(T,@b,2)
                                           @h = Child(T,@b,3)
     @a = Locate(T,"a")
                        @g = Locate(T,"g")
                                           @h = Locate(T,"h")

     Child() y Sibling() sirven para moverse en la lista de  hijos 
de un  nodo.  La  operacin First_Child()   es una  abreviacin de 
Child(T,p,1); Next_Sibling() es una abreviacin de Sibling(T,p,1).

     Las otras operaciones que complementan a Insert() son las que 
permiten eliminarle nodos al rbol. Las operaciones Prune(T,p)   y 
Prune_Child(T,p,i) sirven para  eliminar subrboles completos;  la 
diferencia entre las  dos es que  Prune() elimina al  subrbol que 
tiene por raz al nodo "p", mientras que Prune_Child() elimina  al 
i-simo subrbol del nodo "p":

                                                   
          T                                 T
                  Prune_Child(T, @a, 4)    
          a                                 a
         /|\       Prune(T, @e)            /|
       / / \ \                           / / \
      b  c d  e                         b  c d
     /|\     /|\                       /|\
    f g h   i j k                     f g h
             / \
             l m

     Las  operaciones Extirpate(T,p)  y Extirpate_Child(T,p,i) son 
similares a Prune() y Prune_Child(), pero en lugar de eliminar  un 
subrbol completo, slo eliminan un nodo.  En caso de que el  nodo 
tenga descendencia, entonces los hijos del nodo eliminado pasan  a 
ser hermanos de los nodos hermanos del nodo eliminado:

                                                   
          T                                T
              Extirpate_Child(T, @e, 2)   
          a                                a
         /|\        Extirpate(T, @j)      /|\
       / / \ \                          / / \ \
      b  c d  e                        b  c d  e
     /|\     /|\                      /|\    // \\
    f g h   i j k                    f g h  i l m k
             / \
             l m

     Count_Children(T,p) retorna el nmero de hijos de un nodo  en 
el rbol y Count(T) retorna el nmero total de nodos del rbol.

     Height(T,p) retorna la altura del nodo de posicin "p" en  T, 
y  Depth(T,p)   retorna su  profundidad.  Leaf(T,p)   retorna TRUE 
cuando "p" es  un  nodo  hoja  de  T.   Length(T,n,m)  retorna  la 
longitud del nico camino que une al nodo "n" con el nodo "m", que 
puede ser 0 cuando "n" es "m".

     13 = Count(T)
      4 = Count_Children(T, Root(T))

      3 = Heigth(Root(T)) = Length(T, @a, @m) = Depth(T, @m)

      0 = Length(T, @c, @c)
      1 = Length(T, @l, Father(@l))
      2 = Length(T, @f, Sibling(T,@f,2))
      5 = Length(T, @f, @m)


Modelo
======

     El  modelo del ADT  es un diagrama de  la estructura de datos 
usado para implementarlo. TTree tiene el siguientes modelo:

                            Ŀ
                             _bhvr 
                            Ĵ
                             _excp 
                            Ĵ
                             _root 
                            
                                
                               \/
                                v
                         Ŀ
                         Ŀ    > Tree.Null
                         TElemĿ
         > ٳfather <Ŀ
                        Ĵ               
                           children                  
                                               
                                       
                                                 
             Ŀ              Ŀ    
             Ŀ              Ŀ    
       ĴTElem              TElemĿ
       fatherٳ              ٳfather
       Ĵ< v v  v v >Ĵ
          children                          children   
                                           
                           
         v v v  v v v                        v v v  v v v

     El Rep del ADT TTree contiene tres campos.  "_bhvr" tiene  el 
conjunto de  comportamientos del  rbol, "_excp"  es para  uso del 
manejador de excepciones y "_root" apunta a la raz del rbol.

     Para  aumentar  la utilidad  de este  ADT, la  implementacin 
puede manejar cuatro tipos de  nodos, aunque en cada momento  dado 
no puede ocurrir que el mismos rbol tenga dos o ms tipos de nodo 
distintos.  El  programador usuario  del TTree  escoge el  tipo de 
nodo a usar mediante las operaciones Behave() y Behaviour().

     Lo comn a todos los tipos  de nodo para TTree es que  tienen 
una  lista de hijos.  En  lo que difieren es en  si tienen o no un 
puntero al padre, que est en el campo "father", o si en lugar  de 
tener una copia del elemento del nodo lo que tienen es un  puntero 
al elemento.  Los nodos que  contienen un puntero al padre  ocupan 
ms memoria que los que no  la contienen, aunque a cambio de  este 
costo  de  almacenamiento   aceleran  visiblemente  la   operacin 
Father(T,p),  que  es  una  operacin  muy  importante  es  muchas 
aplicaciones  [del  mismo orden  de importancia  que List.Prev()].  
Los  nodos que  tienen punteros a  elementos son tiles  cuando es 
necesario que el  mismo  objeto  est  simultneamente  en  varios 
contenedores.

     Los  tipos de  nodo que puede  utilizat el ADT  TTree son los 
siguientes:

          TNode_EF                       TNode_PF

         Ŀ
         Ŀ    ^                       ^      ^
         TElemĿ               Ŀ
         ٳfather                PElem father
         Ĵ               Ĵ
            children                     children   
                                        
                        
           v v v  v v v                   v v v  v v v

         Ŀ
         Ŀ                            ^
         TElem                      Ŀ
         ٳ                       PElem 
         Ŀ               Ŀ
            children                     children   
                                        
                        
           v v v  v v v                   v v v  v v v

           TNode_EnF                      TNode_PnF

     La  siguiente  convencin se  usa en  la implementacin  para 
nombrar a los tipos de nodo:

     EF  = nodo con puntero al padre (contiene elemento).
     EnF = nodo sin puntero al padre (contiene elemento).
     PF  = nodo con puntero al padre (contiene puntero).
     PnF = nodo sin puntero al padre (contiene puntero).

     E:  Indica que el nodo contiene al elemento.
     P:  Indica que el nodo NO contiene al elemento, sino
         que tiene un puntero al elemento.
     F:  Indica que el nodo tiene un puntero al padre.
     nF: Indica que el nodo NO tiene un puntero al padre.


Comportamientos
===============

     Para aumentarle  la  utilidad  de  su  ADT  el  implementador 
siempre trata de  trata de lograr  que su ADT  sea lo ms  general 
posible.   Para  esto define  varios comportamientos,  los que  le 
permiten  al programador usuario ajustar  el ADT a sus necesidades 
personales. Para agregarle un comportameinto al ADT el programador 
usuario inovoca a la funcin Behave(T,b,TRUE), la que le agrega  a 
"T" el comportamiento "b", pero  slo si es vlido hacerlo.   Para 
quitarle el comportamiento se usa Behave(T,b,FALSE).

     Los comportamientos implementados para  el ADT TTree son  los 
siguientes:

     Insert_using_Move
     Use_Father_Pointer
     Use_Instance_Pointers
     Destroy_Pointed_Instances.

     Cada vez que se inserta un valor en el rbol por medio de  la 
operacin Insert(T,p,i,x), es  necesario  copiar  o  trasladar  el 
valor de "x" al nuevo nodo del rbol.  Cuando el rbol "T" incluye 
el  comportamiento Insert_using_Move  entonces Insert(T,p,i,x) usa 
Elem.Move() para trasladar el  valor de "x" al  nodo, y si no  usa 
Elem.Copy() para copiar el valor "x" al nodo.

     Si el rbol "T" incluye al comportamiento  Use_Father_Pointer 
entonces cada nodo del rbol tiene un puntero al padre, o sea, que 
se usa nodos del tipo TNode_EF o TNode_PF.

     El comportamiento  Use_Instance_Pointers sirve  para que  los 
nodos del rbol contengan punteros a los elementos almacenados  en 
el  rbol, en lugar de contener  copias de cada elemento.  Por eso 
este  comportamiento no es  compatible con Insert_using_Move, pues 
si se usan punteros a instancias no hace falta copiar o  trasladar 
valores a los nodos del rbol. Por eso la expresin:
     Behaviour(T, Insert_using_Move)
       AND
     Behaviour(T, Use_Instance_Pointers)
siempre es  FALSE.  El  comportamiento Use_Instance_Pointers  hace 
que el rbol use nodos de tipo TNode_PF o TNode_PnF.

     Si el rbol  incluye al comportamiento  Use_Instance_Pointers 
entonces tambin es  necesario  definir  si  cuando  el  rbol  es 
destruido es necesario destruir a las instancias a que cada uno de 
sus   nodos   apunta.    Para   esto   sirve   el   comportamiento 
Destroy_Pointed_Instances.

     Cuando  un programdor usa un  contenedor que tiene punteros a 
sus elementos, y no copias de sus elementos, es porque por  alguna 
razn  necesita que el mismo  elemento est en varios contenedores 
al mismo tiempo.

     En el  ejemplo que  se muestra  a continuacin  el valor  del 
arreglo A1 de seis elementos es (A,A,B,B,C,C), y el A2 es (A,B,C).  
Si el  elemento que  contien una  "B" cambiara  por "Z",  entonces 
inmediatamente el valor del primer arreglo sera (A,A,Z,Z,C,C)   y 
el del segundo sera (A,Z,C).  Precisamente esta simultaneidad  de 
valores  es  lo que  justifica usar  punteros a  instancias en  un 
contenedor.  Por ejemplo, si  los  valores  [A],  [B]  y  [C]  son 
mensajes de  los  entre  procesos  administrados  por  un  Sistema 
Operativo, conviene que al cambiar un mensaje, cambie en todos los 
contenedores que lo contienen.

                     A1 = (A, A, B, B, C, C)
                 Ŀ
                  @A  @A  @B  @B  @C  @C 
                 
                                        
                         
                                        
                     \ /       \ /       \ /
                    Ŀ     Ŀ     Ŀ
                    [A]     [B]     [C]
                              
                     / \       / \       / \
                                        
                      Ŀ         
                                    
                         Ŀ
                          @A  @B  @C 
                         
                          A2 = (A, B, C)

     El problema que resuelve el programador con el comportamiento 
Destroy_Pointed_Instances es evitar  que  los  objetos  que  estn 
referenciados desde ms de un contenedor no sean destruidos ms de 
una  vez.  Por eso slo uno  de estos dos contenedores puede tener 
este compartamiento, aunque tambin es posible que ninguno de  los 
dos lo tenga.  De todas maneras, el programador debe ser cuidadoso 
al usar  punteros a  instancias, pues  siempre debe  asegurarse de 
destruir los objetos cuando ya no los ocupa.

     Es por esta razn que las operaciones de grabado y lectura en 
disco del ADT  TTree, [Load(), Store(),  Read() y Print()]  evitan 
grabar  o  recuperar el  valor de  un contenedor  no que  tiene el 
comportamiento Destroy_Pointed_Instances, pues esa es la forma  de 
evitar que los objetos del contenedores sean indestructibles.


Detalles de implementacin
==========================

     En general la parte ms compleja en la implementacin del ADT 
TTree es  la manipulacin  de punteros,  pues un  pequeo descuido 
puede  resultar  en  puntero  roto, que  en general  tiene efectos 
impredecibles en el programa.  Precisamente por lo difcil que  es 
manipular  punteros   se  justifica   usar  ADTs,   pues  permiten 
encapsular  su   uso  en   un  mdulo   que  puede   ser  depurado 
independientemente del resto del programa.

     Desgraciadamente en este ADT no se logra una separacin total 
entre el ADT contenedor y su elemento contenido. De hecho, un nodo 
est compuesto de  la agregacin del  campo que contiene  al TElem 
con los campos que manipula el ADT TTree: una mayor modularidad se 
obtendra  si  estos dos  tipos de  datos estuvieran  separados de 
alguna manera.  Pero en la prctica todos los progamadores estamos 
acostumbrados  a usar  contenedores que no  hacen esta separacin, 
pues  la mayora de los ADTs  que se encuentran en las bibliotecas 
de programas estn programadas en forma similar al ADT TTree.  

     El  principal problema  de mezclar los  campos del contenedor 
con  los  del  elemento  contenidos es  que si  en un  programa se 
necesita usar dos tipos de rbol, ser necesario crear dos  copias 
completas del ADT TTree, una para cada tipo de elemento.  Ms an, 
es imposible que un mismo  elemento est en varios contenedores  a 
menos que el contenedor use  punteros a cada elemento. En  algunos 
lenguajes modernos, como C++ y ADA, esta restriccin se soluciona, 
de  forma  parcial   y  poco  elegante,   con  el  uso   de  Tipos 
Parametrizados, llamados plantillas o paquetes genricos.   Existe 
una   solucin  alterna,   pero  requiere  de   una  filosofa  de 
construccin de  programas  bastantes  diferente,  aunque  su  uso 
incrementa significativamente  la  modularidad  de  los  ADTs  as 
usados, lo que se logra con la unidad Binder.pas, que se  describe 
en otro documento.

     En la implementacin se hace un uso intenso de transferencias 
de tipo para evitar  que  los  cuatro  tipos  de  nodo  que  puede 
utilizar el ADT incrementen  demasiado la complejidad del  cdigo. 
Dos  operaciones  que  disminuyen  mucho  la  complejidad  de   la 
implementacin son Create_a_Node(T,p) y Destroy_a_Node(T,p),  pues 
se  encargan de crear y destruir  los nodos que son compatible con 
el comportamiento de "T".

     El  tipo PTpos  se implementa como  un puntero que  apunta al 
mismo tipo, de forma que el programador no puede  derreferenciarlo 
y  usarlo.   En  la  implementacin estos  PTpos son  covertidos a 
punteros a nodos, de tipo PNode_RepTree.

     Otra  incomodidad bastante grande  que debe sobrellevar quien 
use el ADT  TTree es que  debe definir un  ADT de tipo  TElem para 
usar el contendor. En muchas ocasiones los programdores encuentran 
esto tan  engorroso que  terminan cambiando  la implementacin  de 
TTree para evitar  la proliferacin de  tipos TElem.  Esto  ocurre 
cuando se necesita un rbol simple, que contiene nmeros o letras, 
pues  en  estos  casos  el definir  todo un  ADT para  objetos tan 
simples es  un  trabajo  demasiado  grande  (aburrido?)  para  el 
programador. Este es tambin el el caso del ADT TPList que se  usa 
en la implementacin de TTree, lo que se discute ms adelante.

     La mayora de las operaciones del TTree se implementan usando 
recursividad. Como el Rep del TTree no es simplemente un puntero a 
un   nodo,  entonces  en  la   implementacin  de  muchas  de  las 
operaciones de TTree  lo que hacen  es invocar a  un procedimiento 
recursivo que realmente realiza el trabajo, y como argumento se le 
enva la raz del rbol.  Por ejemplo, la operacin Clear()   est 
implementada en trminos  de Clear0(): el  trabajo de Clear(T)  es 
simplemente  llamar  a  Clear0(T.Rep._root),  y  Clear0()   es  el 
procedimiento recursivo que realiza todo el trabajo definido en la 
especificacin de Clear().

     Para almacenar en la memoria la lista de hijos de un nodo  se 
usa  el ADT  PList, que es  una versin modificada  del ADT TList.  
Cada nodo en la PLista contiene un puntero que apunta al hijo  del 
nodo; o sea, que el elemento contenido en la PLista es un "puntero 
a  nodo  del rbol".   A diferencia  de TTree,  los nodos  del ADT 
TPList no contienen un campo  de tipo TElem, sino que  simplemente 
contiene  un campo de tipo POINTER,  que es el puntero genrico de 
Pascal. Muchas operaciones  de TTree deben  manipular la lista  de 
hijos de un nodo, lo que se logra procesando la lista de hijos  de 
uno nodo por nodo.  El siguiente cdigo es un esqueleto de cmo se 
procesa la lista de hijos de un nodo:

     VAR
       pL   : PLpos;   { posicin la la PLista de hijos }
       p,                  { punteros a nodos del rbol }
       child: PNode_RepTree;

     { ... }

       { obtiene al primer hijo }
       pL := PList.First(p^.children);

       WHILE pL <> PList.Null DO BEGIN
         { todava hay hijos que procesar }

         { obtiene el puntero al siguiente nodo hijo }
         child := PNode( PList.Retrieve(p^.children, pL)^ );

         { procesa el nodo }
         Procese(child);

         { avanza en la lista de hijos }
         pL := PList.Next(p^.children, pL);
       END;

     { ... }

     La  funcin de  "pL" en este  cdigo es recorrer  la lista de 
hijos del nodo "p" del rbol. "p" es un puntero a un nodo, que fue 
obtenido despus de  hacer  una  transferencia  de  tipos  de  una 
variable de tipo PTpos.  "pL" es una posicin dentro de la  PLista 
de hijos de un nodo.

     Para  obtener  el  puntero  al  hijo  es  necesario  usar  la 
operacin PList.Retrieve()   que  convierte  una  posicin  en  la 
PLista, en  lo que  la PLista  contiene, que  en este  caso es  el 
puntero al nodo hijo de "p".

     Para  accesar el  nodo, es necesario  derreferenciar el valor 
que  PList.Retrieve() retorna, pues  Retrieve() siempre regresa un 
"puntero al valor".  Por eso PList.Retrieve() retorna un  "puntero 
al puntero" que apunta  al nodo. Por eso  es que dentro del  ciclo 
WHILE se toma el valor retornador por Retrieve() y se le agrega el 
operador (^) que sirve para derreferenciar punteros en Pascal:
     child := PNode( PList.Retrieve(p^.children, pL)^ );


Bibliografa
============

[1] Aho, Alfred V.; John E.  Hopcroft; Jefrrey  D.  Ullman:  "Data 
    Structures and Algorithms"; 1983. [AHO-83].

[2] Borland; "Turbo Pascal Version 5.5"; 1984.

[3] Liskov, Barbara; Gutag,  John; "Abstraction  and Specification 
    in Program Development"; McGraw-Hill; 1986.

[4] Di Mare, Adolfo:  "Convenciones de  Programacin para  Pascal, 
    Revisin 2"; Reporte tcnico ECCI-01-88, ECCI-UCR, 1988.

[5] Di  Mare, Adolfo:  "Abstraccin de  Datos en  Pascal"; Reporte 
    tcnico PIBDC-01-89, ECCI-UCR, 1991.

[6] Horowitz, E.; Sahni,  S.: "Fundamentals  of Data  Structures"; 
    Computer Science Press; 1982.


               Reportes tcnicos de Adolfo Di Mare
               ===================================

     Los siguientes Reportes Tcnicos, todos confeccionados por el 
mismo autor, describen todos  las implementaciones y algunos  usos 
importantes de los ADTs programados en Turbo Pascal en al  Escuela 
de Ciencias de la Computacin e Informtica, de la Universidad  de 
Costa Rica. 

     Todas estas  implementaciones estn  disponibles en  Internet
por medio de ftp annimo en el directorio:

     http://www.di-mare.com/adolfo/p/src/Tree.zip

     Los derechos de autor  estn reservados  a nombre  del autor,
Adolfo Di Mare.

     El texto de cada Reporte Tcnico se encuentra  en el  archivo
de texto nombrado entre parntesis cuadrados.

[R1]  "Prueba  interactiva  de  ADTs", Reporte  Tcnico ECCI-94-01
      [Archivo UseADT.doc]; Mayo, 1994.

[R2]  "La Implementacin de Elem.pas"; Reporte  Tcnico ECCI-94-02
      [Archivo Elem.doc]; Mayo 1994.

[R3]  "La   Implementacin   de  Rational.pas";   Reporte  Tcnico
      ECCI-94-03 [Archivo Rational.doc]; Mayo 1994.

[R4]  "La Implementacin de Poly.pas"; Reporte  Tcnico ECCI-94-04
      [Archivo Poly.doc]; Mayo 1994.

[R5]  "La    Implementacin  de   ListAHO.pas";  Reporte   Tcnico
      ECCI-94-05 [Archivo Aho.doc]; Mayo 1994.

[R6]  "La Implementacin de List.pas"; Reporte  Tcnico ECCI-94-06
      [Archivo List.doc]; Mayo 1994.

[R7]  "La Implementacin de Tree.pas"; Reporte  Tcnico ECCI-94-07
      [Archivo Tree.doc]; Mayo 1994.

[R8]  "La Implementacin de Heap.pas"; Reporte  Tcnico ECCI-94-08
      [Archivo Heap.doc]; Mayo 1994.

[R9]  "Uso  de  la  unidad Test.pas";  Reporte Tcnico  ECCI-94-09
      [Archivo Test.doc]; Mayo 1994.

[R10] "Manejo  de excepciones  en Turbo  Pascal"; Reporte  Tcnico
      ECCI-94-10 [Archivo Except.doc]; Mayo 1994.
