Diseño y estructura de datos y especificación de problemas

Captulo 5 rboles

Los rboles (ing., tree) son estructuras que organizan sus elementos, denominados nodos,formando jerarquas. Su definicin inductiva es:

- Un nico nodo es un rbol; a este nodo se le llama raz del rbol.- Dados n rboles a1, ..., an, se puede construir uno nuevo como resultado de enraizar

un nuevo nodo con los n rboles ai. Generalmente, el orden de los ai es significante yas lo consideramos en el resto del captulo; algunos autores lo subrayan llamndolosrboles ordenados (ing., ordered trees). Los rboles ai pasan a ser subrboles delnuevo rbol y el nuevo nodo se convierte en raz del nuevo rbol.

La representacin grfica de los rboles refleja claramente la jerarqua resultante de sudefinicin.

...a1 a2 an...

a1 a2 an

Fig. 5.1: n rboles (a la izquierda) y su enraizamiento formando uno nuevo (a la derecha).

El concepto matemtico de rbol data de mediados del siglo XIX y su uso en el mundo de laprogramacin es habitual. Ya ha sido introducido en la seccin 1.2 como una representacinintuitiva de la idea de trmino; en general, los rboles permiten almacenar cmodamentecualquier tipo de expresin dado que la parentizacin, la asociatividad y la prioridad de losoperadores quedan implcitos y su evaluacin es la simple aplicacin de una estrategia derecorrido. Suelen utilizarse para representar jerarquas de todo tipo: taxonomas, relacionesentre mdulos, etc. Igualmente es destacable su contribucin a diversos campos de lainformtica: rboles de decisin en inteligencia artificial, representacin de gramticas yprogramas en el mbito de la compilacin, ayuda en tcnicas de programacin

rboles 2 1 9__________________________________________________________________________________

(transformacin de programas recursivos en iterativos, etc.), ndices en ficheros de accesopor clave, bases de datos jerrquicas, etc.

5.1 Modelo y especificacin

En esta seccin introducimos el modelo formal asociado a un rbol, que emplearemos paraformular diversas definiciones tiles, y tambin su especificacin ecuacional. Hablando conpropiedad, hay varios modelos de rboles que surgen a partir de todas las combinacionesposibles de las caractersticas siguientes:

- El proceso de enraizar puede involucrar un nmero indeterminado de subrboles obien un nmero fijo n. En el primer caso hablamos de rboles generales (ing., generaltree) y en el segundo caso de rboles n-arios (ing., n-ary tree)1; en estos ltimosdestaca el caso de n = 2, los denominados rboles binarios (ing., binary tree), sobre elcual nos centraremos a lo largo del texto dada su importancia, siendo inmediata laextensin a cualquier otro n. En los rboles n-arios se definir el concepto de rbolvaco que ampliar el conjunto de valores del tipo.

- Los nodos del rbol pueden contener informacin o no; el primer caso es el habitual yresponde al uso de rbol como almacn de informacin, pero tambin se puede dar lasituacin en que slo interese reflejar la jerarqua, sin necesidad de guardar ningndato adicional. En el resto del captulo nos centraremos en el primer tipo de rbol,porque generaliza el segundo. La informacin en los nodos se denominar etiqueta(ing., label) y los rboles con informacin rboles etiquetados (ing., labelled tree).

- La signatura definida en los rboles puede ser muy variada. Destacamos dos familias:en la primera se utilizan rboles enteros tal como se ha explicado en la introduccin,con operaciones de enraizar diversos rboles, obtener un subrbol y, si el rbol esetiquetado, obtener la etiqueta de la raz; la segunda familia define un nodo dereferencia para las actualizaciones y consultas, que puede cambiarse con otrasoperaciones. Llamaremos al segundo tipo rboles con punto de inters, por susimilitud respecto a las listas de las mismas caractersticas.

5.1.1 Modelo de rbol general

Un rbol general se caracteriza por su forma, que determina una relacin jerrquica, y por elvalor de la etiqueta asociada a cada uno de los nodos del rbol. La forma del rbol se puededescribir como un conjunto de cadenas de los naturales sin el cero, P(N0*), de manera quecada cadena del conjunto identifica un nodo del rbol segn una numeracin consecutiva deizquierda a derecha comenzando por el uno, tal como se muestra en la fig. 5.2. Hay que

2 2 0 Estructuras de datos. Especificacin, diseo e implementacin __________________________________________________________________________________

1 La nomenclatura no es estndar; es ms, diferentes textos pueden dar los mismos nombres adiferentes modelos y contradecirse entre s.

resaltar que este conjunto es cerrado por prefijo y compacto; cerrado por prefijo, porque si lacadena . est dentro del conjunto que denota la forma de un rbol, para , N0*,tambin lo est la cadena ; y compacto, porque si la cadena .k est dentro del conjunto,para N0*, kN0, tambin lo estn las cadenas .1, .2, ..., .(k-1).

1

11 122

3

31 32 33 34

331 332

Fig. 5.2: representacin del rbol de forma {, 1, 2, 3, 11, 12, 31, 32, 33, 34, 331, 332}.

Por lo que respecta a los valores de las etiquetas, se puede definir una funcin que asocie auna cadena un valor del conjunto de base de las etiquetas. Evidentemente, esta funcin esparcial y su dominio es justamente el conjunto de cadenas que da la forma del rbol.

marzo

febreroabril

mayo octubre

setiembre

junio

julio

agostoenero

nov.diciembre

Fig. 5.3: el mismo rbol que en la fig. 5.2, asignando etiquetas a sus elementos.

As, dado el conjunto base de las etiquetas V, definimos el modelo A V de los rbolesgenerales y etiquetados como las funciones que tienen como dominio las cadenas denaturales N0* y como codominio las etiquetas V, f : N0* V, tales que su dominio dom(f )cumple que no es vaco, es cerrado por prefijo y compacto; a dom( f ) le llamaremos la forma ocontorno del rbol. A partir de este modelo se formulan una serie de definiciones tiles parael resto del captulo, cuya especificacin ecuacional queda como ejercicio para el lector.

a) Definiciones sobre los nodosSea a A V un rbol general y etiquetado cualquiera.

- Un nodo del rbol (ing., node) es un componente determinado por la posicin que

rboles 2 2 1__________________________________________________________________________________

ocupa y por la etiqueta; es decir, n= es un nodo de a si sdom(a) y a(s) = v. En lafig. 5.3, es un nodo pero no lo son ni ni . Elconjunto Na = {n / n es un nodo de a}es el conjunto de todos los nodos del rbol a.

- La raz del rbol (ing., root) es el nodo que est ms arriba, . Por ejemplo, laraz del rbol de la fig. 5.3 es el nodo . Notemos que, a causa de laspropiedades del modelo, todo rbol a presenta una raz. A veces, por comodidad ycuando quede claro por el contexto, denominaremos raz simplemente a la etiqueta delnodo raz.

- Una hoja del rbol (ing., leaf ) es un nodo que est abajo de todo; es decir, el nodon=Na es hoja dentro de a si no existe N0+ tal que s.dom(a). En el rbolde la fig. 5.3, son hojas los nodos y , pero no lo es. El conjunto Fa = {n / n es hoja dentro de a} es el conjunto de todas lashojas del rbol a.

- Un camino dentro del rbol (ing., path) es una secuencia de nodos conectados dentrodel rbol; o sea, la secuencia c = n1...nr , i: 1 i r : ni = Na, es camino dentrode a si cada nodo cuelga del anterior, es decir, si i: 1 i r-1: (k : k N0: si+1 = si.k).La longitud del camino (ing., length) es el nmero de nodos menos uno, r - 1; si r > 1,se dice que el camino es propio (ing., proper). En el rbol de la fig. 5.3, la secuenciaformada por los nodos es un camino propio delongitud 2. El conjunto Ca = {c / c es camino dentro de a} es el conjunto de todos loscaminos del rbol a.

- La altura de un nodo del rbol (ing., height) es uno ms que la longitud del caminodesde el nodo a la hoja ms lejana que sea alcanzable desde l2; es decir, dado el nodonNa y el conjunto de caminos Can que salen de un nodo n y van a parar a una hoja,Can = {c = n1...nk / cCa n1 = n nk Fa}, definimos la altura de n dentro de a comola longitud ms uno del camino ms largo de Can. En el rbol de la fig. 5.3, el nodo tiene altura 3. La altura de un rbol se define como la altura de su raz; as, laaltura del rbol de la fig. 5.3 es 4.

- El nivel o profundidad de un nodo del rbol (ing., level o depth) es el nmero denodos que se encuentran entre l y la raz; es decir, dado el nodo n=Nadefinimos el nivel de n dentro de a como ||s ||+1, siendo ||s || la longitud de s ; tambin sedice que n est en el nivel ||s ||+1. En el rbol de la fig. 5.3, el nodo est en elnivel 2. Por extensin, cuando se habla del nivel i de un rbol (tambin primer nivel,segundo nivel, y as sucesivamente) se hace referencia al conjunto de nodos queestn en el nivel i. El nmero de niveles de un rbol a se define como el nivel de la hojams profunda; as, el nmero de niveles del rbol de la fig. 5.3 es 4. Notemos que, por


2 Las definiciones de altura, profundidad y nivel son tambin contradictorias en algunos textos. Hayautores que no definen alguno de estos conceptos, o los definen slo para un rbol y no para susnodos, o bien empiezan a numerar a partir del cero y no del uno, etc. En nuestro caso concreto,preferimos numerar a partir del uno para que el rbol vaco (que aparece en el caso n-ario) tenga unaaltura diferente al rbol con un nico nodo.

definicin, el nmero de niveles de un rbol es igual a la altura, por lo que puedenusarse ambas magnitudes indistintamente.

b) Definiciones sobre las relaciones entre nodosA partir del concepto de camino, damos diversas definiciones para establecer relacionesentre nodos. Sean a A V un rbol general y etiquetado y n,n' Na dos nodos del rbol,n = y n' = ; si hay un camino c = n1...nr Ca tal que n1 = n y nr = n', decimos que:

- El nodo n' es descendiente (ing., descendant) de n y el nodo n es antecesor (ing.,ancestor) de n'. Si, adems, r > 1, los llamamos descendiente o antecesor propio.

- Si, adems, r = 2 (es decir, si n' cuelga directamente de n), entonces: El nodo n' es hijo (ing., child) de n; en concreto, si s' = s.k, k N0, decimos que n'

es hijo k-simo de n (o tambin primer hijo, segundo hijo, y as hasta el ltimo hijo). n es padre (ing., parent) de n'. Hay una rama (ing., branch) entre n y n'.

- El grado o aridad (ing., degree o arity) de n es el nmero de hijos del nodo; es decir, sedefine gradon = ||{dom(a) / k,s : k N0 s N0*: = s.k }||. La aridad de un rbol sedefine como el mximo de la aridad de sus nodos.

Adems, dos nodos n y n' son hermanos (ing., sibling) si tienen el mismo padre, es decir, sise cumple que s = .k y s' = .k', para k,k'N0 y N0*. Si, adems, k = k'+1, a n' lollamaremos hermano izquierdo de n y a n, hermano derecho de n'. En el rbol de la fig. 5.3,el nodo es antecesor propio del nodo , tambin del y del (y, consecuentemente, estos tres nodos son descendientes propios delprimero). Adems, y son hijos de (y, en consecuencia, es padre de los nodos y , que son hermanos, y hay unarama entre y y entre y ). El grado del nodo razes 3 porque tiene tres hijos, mientras que el grado de todas las hojas es 0 porque no tienenninguno, siendo sta una propiedad comn a todos los rboles del modelo.

c) Definiciones sobre subrbolesSean a,a'A V dos rboles generales y etiquetados. Decimos que a es subrbol hijo de a', osimplemente subrbol (ing., subtree), si est contenido en l, o sea, si N0* tal que:

- Se superponen: # dom(a) = { / N0* . dom(a' )}, con #: N0* x P(N0*) P(N0*)definida como: # {s1, ..., sn} = {.s1, ..., .sn}.

- Las etiquetas de los nodos se mantienen: : Na: a' (.s) = v.

- No hay nodos por debajo de la superposicin: ( Na: N0+: .s. dom(a' )).

Concretamente, en este caso decimos que a es -subrbol de a' ; si, adems, |||| = 1, a sedenomina primer subrbol de a' si = 1, segundo subrbol de a' si = 2, etc., hasta elltimo subrbol. Por ejemplo, en la fig. 5.4 se presentan un rbol que es subrbol del rbolde la fig. 5.3 (a la izquierda, en concreto, su tercer subrbol) y otro que no lo es (a la derecha).

rboles 2 2 3__________________________________________________________________________________

mayo

marzo

octubre

setiembre

junio

julio nov.

enero

abril

agosto

febrero

diciembre

Fig. 5.4: un subrbol del rbol de la fig. 5.3 (a la izquierda) y otro que no lo es (a la derecha).

Una vez determinado completamente el modelo y las definiciones necesarias para hablar conpropiedad de los rboles generales, vamos a determinar su signatura y especificacin. Talcomo se ha dicho previamente, la operacin bsica de la signatura de este modelo esenraizar un nmero indeterminado de rboles para formar uno nuevo, que tendr en la razuna etiqueta dada, enraiza : A V* x V A V. Ahora bien, la sintaxis de las especificaciones deMerl (y, en general, de ningn lenguaje de especificacin o implementacin) no permitedeclarar un nmero indeterminado de parmetros como parece requerir esta signatura y, portanto, adoptamos un enfoque diferente. En concreto, introducimos el concepto de bosque(ing., forest), definido como una secuencia3 de rboles, de manera que enraiza tendr dosparmetros, el bosque que contiene los rboles para enraizar y la etiqueta de la raz4. As,dados el rbol a A V, el bosque b A V*, b = a1...an, y la etiqueta v V, la signatura es:

- Crear el bosque vaco: crea, devuelve el bosque sin rboles.- Aadir un rbol al final del bosque: inserta(b, a), devuelve el bosque b.a.- Averiguar el nmero de rboles que hay en el bosque: cuntos(b), devuelve n.- Obtener el rbol i-simo del bosque: i_simo(b, i), devuelve ai ; da error si i > n o vale 0.- Enraizar diversos rboles para formar uno nuevo: enraiza(b, v) , devuelve un nuevo

rbol a tal que la etiqueta de su raz es v y cada uno de los ai es el subrbol i-simo dea, es decir, devuelve el rbol a tal que:

dom(a) = i : 1 i n: i # dom(ai) {}. a() = v. i : 1 i n: : dom(ai): a(i.) = ai().

- Averiguar la aridad de la raz del rbol: nhijos(a), devuelve grado.

- Obtener el subrbol i-simo del rbol: subrbol(a, i) devuelve el subrbol i-simo de a oda error si i es mayor que la aridad de la raz o cero; es decir, devuelve el rbol a' tal que:

dom(a' ) = { / i.dom(a)}. : dom(a' ): a' () = a(i.).

- Consultar el valor de la etiqueta de la raz: raz(a), devuelve a().


3 No un conjunto, porque el orden de los elementos es significativo.4 Tambin podramos haber optado por un conjunto de operaciones enraiza1, ..., enraizan, donde nfuera un nmero lo bastante grande, de manera que enraizai enraizase i rboles con una etiqueta.

En la fig. 5.5 se muestra una especificacin para este modelo. Notemos que el bosque secrea fcilmente a partir de una instancia de las secuencias tal como fueron definidas en elapartado 1.5.1, pero considerando el gnero del alfabeto como parmetro formal (definidoen el universo de caracterizacin ELEM). La instancia va seguida de varios renombramientospara hacer corresponder los identificadores de un tipo con los del otro, y de la ocultacin delos smbolos no usables. La especificacin del tipo rbol es trivial tomando {enraiza} comoconjunto de constructoras generadoras (puro) y usando las operaciones sobre bosques.Como hay dos apariciones diferentes del universo ELEM, se prefija cada una de ellas con unidentificador. Es conveniente que los gneros del bosque y del rbol residan en el mismouniverso, porque se necesitan recprocamente.

universo RBOL_GENERAL (A es ELEM) esusa NAT, BOOLtipo rbolinstancia CADENA (B es ELEM) donde B.elem es rbolrenombra _._ por inserta, ||_|| por cuntos, cadena por bosqueesconde _._, [_], etc.ops enraiza: bosque A.elem rbol

nhijos: rbol natsubrbol: rbol nat rbolraz: rbol A.elem

error arbol; inat: [i > nhijos(a) NAT.ig(i, 0)] subrbol(a, i)ecns bbosque; inat; vA.elem

nhijos(enraiza(b, v)) = cuntos(b)subrbol(enraiza(b, v), i) = CADENA.i_simo(b, i)raz(enraiza(b, v)) = v

funiverso

Fig. 5.5: especificacin del TAD de los rboles generales.

5.1.2 Modelo de rbol binario

El modelo de rbol binario, denotado por A 2V, son las funciones f : {1, 2}* V, dado que unnodo puede tener, como mucho, dos hijos. Como en el caso de los rboles generales, eldominio de la funcin ha de ser cerrado por prefijo, pero, en cambio, se permite la existenciadel rbol vaco y, como consecuencia, el rbol binario presentar discontinuidades cuando laoperacin de enraizamiento involucre un rbol vaco como primer hijo y un rbol no vacocomo segundo hijo. En la fig. 5.6 se muestra algunos rboles binarios vlidos; notemos quesi interpretamos los rboles como generales, el de la derecha y el del medio son idnticos.

rboles 2 2 5__________________________________________________________________________________

AB C

A

B

A

C

Fig. 5.6: tres rboles binarios tales que la raz tiene: primer y segundo hijo (izquierda),primer hijo, pero no segundo (medio), y segundo hijo, pero no primero (derecha).

El resto del modelo no vara, siempre que se recuerde que el grado de todo nodo del rboles, como mucho, igual a dos. Las definiciones dadas tambin son vlidas respetando estaregla y considerando que la altura y la profundidad de un rbol vaco valen cero. Para mayorclaridad, el primer hijo de un nodo de un rbol binario se llama hijo izquierdo (ing., left child) yel segundo se llama hijo derecho (ing., right child). De un rbol vaco tambin se puede decirque no existe; refirindose a un nodo, si un hijo (o hermano o cualquier otra relacin deparentesco) de un nodo es vaco tambin podemos decir que el nodo no tiene este hijo (ohermano, etc.). Todas estas definiciones se pueden aplicar al caso de los subrboles.

Dados los rboles a,a1,a2 A 2V y la etiqueta v V, definimos las siguientes operaciones5:- Crear el rbol vaco: crea, devuelve la funcin de dominio vaco.

- Enraizar dos rboles y una etiqueta para formar un rbol: enraiza(a1, v, a2), devuelve elrbol a tal que a() = v, a1 es el subrbol izquierdo de a y a2 es su subrbol derecho.

- Obtener los subrboles izquierdo y derecho de un rbol: izq(a) y der(a), respectivamente;si a es el rbol vaco, dan error.

- Obtener la etiqueta de la raz: raz(a), devuelve a() o da error si a es vaco.- Averiguar si un rbol es vaco: vaco?(a), devuelve cierto si a es el rbol vaco y falso si no.

La aplicacin en el caso de rboles n-arios cualesquiera, A nV, es inmediata, considerando elmodelo como las funciones f : [1, n]* V, y queda como ejercicio para el lector.

5.1.3 Modelo de rbol con punto de inters

Los rboles con punto de inters, ya sea generales o n-arios, se caracterizan por la existenciade un nodo privilegiado identificado por el punto de inters, que sirve de referencia paradiversas operaciones de actualizacin. La etiqueta de este nodo es la nica que puedeconsultarse y, en consecuencia, tambin habr diversas operaciones de modificacin delpunto de inters. Vamos a estudiar el caso de rboles generales (el caso n-ario es parecido).


5 La descripcin formal es similar a los rboles generales y queda como ejercicio para el lector.

universo RBOL_BINARIO (ELEM) esusa BOOLtipo rbolops

crea: rbolenraiza: rbol elem rbol rbolizq, der: rbol rbolraz: rbol elemvaco?: rbol bool

errores izq(crea); der(crea); raz(crea)ecns a,a1,a2rbol; velem

izq(enraiza(a1, v, a2)) = a1der(enraiza(a1, v, a2)) = a2raz(enraiza(a1, v, a2)) = vvaco?(crea) = cierto; vaco?(enraiza(a1, v, a2)) = falso

funiverso

Fig. 5.7: especificacin del TAD de los rboles binarios.

El modelo de este tipo de rboles ha de recoger la posicin del punto de inters y, por tanto,podemos considerarlo un par ordenado < f : N0* V, N0>, donde V es el dominio de lasetiquetas y se cumple que el segundo componente, que identifica la posicin actual, estdentro del dominio de la funcin o bien tiene un valor nulo que denota la inexistencia deelemento distinguido. En cuanto a la signatura, el abanico es muy amplio tanto en lo que serefiere a las operaciones de actualizacin como a las de recorrido, y citamos a continuacinalgunas posibilidades sin entrar en detalle.

- Actualizacin. En las inserciones podemos plantearnos dos situaciones: insertar unnodo como hijo i-simo del punto de inters, o colgar todo un rbol a partir del punto deinters. En cualquier caso, parece lgico no cambiar el nodo distinguido. En cuanto alas supresiones, se presenta la misma disyuntiva: borrar nodos individualmente (quedeberan ser hojas e hijos del nodo distinguido, o bien el mismo nodo distinguido) obien subrboles enteros. Las diversas opciones no tienen por qu ser mutuamenteexclusivas, ya que un mismo universo puede ofrecer los dos tipos de operaciones.

- Recorrido. Tambin distinguimos dos situaciones: la primera consiste en ofrecer unconjunto de operaciones de inters general para mover el punto de inters al hijoi-simo, al padre o al hermano izquierdo o derecho. Tambin se puede disponer dediversas operaciones de ms alto nivel que incorporen las diversas estrategias derecorrido que se introducen en la seccin 5.3. En cualquier caso, las operaciones derecorrido tendrn que permitir que se examinen los n nodos del rbol.

rboles 2 2 7__________________________________________________________________________________

5.2 Implementacin

En esta seccin se presentan diversas estrategias de implementacin de los rboles. Noscentramos en las representaciones ms habituales para los modelos binario y general; en[Knu68, pp. 376-388] se presentan algunas variantes adicionales que pueden ser tiles encasos muy concretos. En el ltimo apartado de la seccin, se hace una breve referencia a laextensin de binario a n-ario y a los rboles con punto de inters.

5.2.1 Implementacin de los rboles binarios

Como en las estructuras lineales, las representaciones de rboles binarios se subdividen endos grandes familias: encadenadas (por punteros y vectores) y secuenciales.

a) Representacin encadenadaEn la fig. 5.8 se muestra una representacin encadenada por punteros. Hay un simpleapuntador de cada nodo a sus dos hijos; si un hijo no existe, el encadenamientocorrespondiente vale NULO. Las operaciones quedan de orden constante, mientras que elespacio utilizado para guardar el rbol es lineal respecto al nmero de nodos que lo forman.El invariante prohbe que haya ms de un encadenamiento apuntando al mismo nodo (lo cualconducira a una estructura en forma de grafo, v. captulo 6) mediante el uso de una funcinauxiliar correcto (necesaria para hacer comprobaciones recursivas siguiendo la estructura delrbol) que se define sobre otra, nodos, que obtiene el conjunto de punteros a nodos de unrbol, similar a la operacin cadena ya conocida (v. fig. 3.23).

Esta representacin presenta una caracterstica importante. Recordemos que, tal como seexpuso en el apartado 3.3.4, la asignacin a3 := enraiza(a1, v, a2) es en realidad unaabreviatura de duplica(enraiza(a1, v, a2), a3), por lo que la instruccin tiene un coste linealdebido a la duplicacin del rbol. Para evitar dichas duplicaciones, es necesario codificar lafuncin en forma de accin definiendo, por ejemplo, dos parmetros de entrada de tiporbol y uno de salida que almacene el resultado (v. fig. 5.9, arriba). Ahora bien, con estaestrategia, varios rboles pueden compartir fsicamente algunos o todos los nodos que losforman, de manera que la modificacin de uno de los rboles tenga como efecto lateral lamodificacin de los otros. Por ejemplo, dados los rboles a1, a2 y a3 y dada la invocacinenraiza(a1, v, a2, a3), es evidente que a1 y el subrbol izquierdo de a3 apuntan al mismo lugar,situacin en la que, si se ejecuta destruye(a1), se est modificando el valor del rbol a3, lo cualprobablemente sea incorrecto6. Si se considera que esta peculiaridad del funcionamento dela implementacin de los rboles binarios es perniciosa, es necesario duplicar los rboles aenraizar, ya sea desde el programa que usa el TAD, ya sea sustituyendo la simple asignacin


6 En realidad, ste no es un problema exclusivo de los rboles, sino en general de lasrepresentaciones por punteros. No lo hemos encontrado antes simplemente por la signatura de lasoperaciones definidas sobre secuencias y tablas. Por ejemplo, si considersemos la operacin deconcatenacin de dos listas, surgira la misma problemtica.

universo ARBOL_BINARIO_ENC_PUNTEROS (ELEM) esimplementa ARBOL_BINARIO (ELEM)usa BOOLtipo rbol es ^nodo ftipotipo privado nodo es

tuplaetiq es elem; hizq, hder son ^nodo

ftuplaftipoinvariante (a es rbol): correcto(a), donde correcto: ^nodo bool se define:

correcto(NULO) = ciertop NULO correcto(p) = correcto(p^.hizq) correcto(p^.hder)

nodos(p^.hizq) nodos(p^.hder) = {NULO} p nodos(p^.hizq) nodos(p^.hder)

y donde nodos: ^nodo P(^nodo) se define como:nodos(NULO) = {NULO}p NULO nodos(p) = {p} nodos(p^.hizq) nodos(p^.hder)

funcin crea devuelve rbol esdevuelve NULOfuncin enraiza (a1 es rbol; v es elem; a2 es rbol) devuelve rbol esvar p es ^nodo fvar

p := obtener_espaciosi p = NULO entonces error si no p^.v := v; p^.hizq := a1; p^.hder := a2 fsi

devuelve pfuncin izq (a es rbol) devuelve rbol es

si a = NULO entonces error si no a := a^.hizq fsidevuelve afuncin der (a es rbol) devuelve rbol es

si a = NULO entonces error si no a := a^.hder fsidevuelve afuncin raz (a es rbol) devuelve elem esvar v es elem fvar

si a = NULO entonces error si no v := a .^v fsidevuelve vfuncin vaco? (a es rbol) devuelve bool esdevuelve a = NULO

funiverso

Fig. 5.8: implementacin por punteros del TAD de los rboles binarios.

rboles 2 2 9__________________________________________________________________________________

de punteros de enraiza, izq y der por duplicaciones de los rboles implicados (v. fig. 5.9,abajo). Obviamente, la segunda alternativa resulta en un coste lineal incondicional de lasoperaciones que duplican rboles. Una opcin diferente consistira en poner a NULO losapuntadores a rboles que acten como parmetros de entrada (que dejaran de ser slo deentrada, obviamente) para evitar manipulaciones posteriores.

accin enraiza (ent a1 es rbol; ent v es elem; ent a2 es rbol; sal a3 es rbol) esa3 := obtener_espaciosi a3 = NULO entonces errorsi no a3^.v := v; a3^.hizq := a1; a3^.hder := a2fsi

faccin

accin enraiza (ent a1 es rbol; ent v es elem; ent a2 es rbol; sal a3 es rbol) esvar p es ^nodo fvar

a3 := obtener_espaciosi a3 = NULO entonces errorsi no a3^.v := v; duplica(a1, a3^.hizq); duplica(a2, a3^.hder)fsi

faccin

Fig. 5.9: implementacin mediante una accin de enraiza, sin duplicacin (arriba)y con duplicacin (abajo) de los rboles.

La representacin sin copia presenta un riesgo aadido: la posible generacin de basura.Este problema aparece porque las acciones izq y dr no aliberan espacio, de manera que alejecutar izq(a, a) o dr(a, a) el espacio del rbol que no aparece en el resultado quedarinaccessible si no hay otros apuntadores a l. Si, incluso con este problema, se quierenmantener las operaciones de coste constante, ser necesario controlar la situacin desde elprograma que usa los rboles.

La representacin encadenada con vectores sigue una estrategia similar. Ahora bien, en elcaso de representar cada rbol en un vector, tal como se muestra en la fig. 5.10, lasoperaciones de enraizar y obtener los subrboles izquierdo y derecho exigen duplicar todoslos nodos del resultado para pasar de un vector a otro y, por ello, quedan lineales sobre elnmero de nodos del rbol7. Para evitar este coste se debe permitir que diferentes rbolescompartan los nodos y, as, usar un nico vector que los almacene todos y que gestione lasposiciones libres en forma de pila, de manera que los rboles sern apuntadores (de tipoentero o natural) a la raz que reside en el vector.


7 El coste ser lineal aunque se transformen las funciones en acciones con parmetros de entrada yde salida segn las reglas del apartado 3.3.4.

tipo rbol es tuplaA es vector [de 0 a mx-1] de nodosl es nat

ftuplaftipo

tipo privado nodo es tupla etiq es elem; hizq, hder son entero ftupla ftipo

Fig. 5.10: representacin encadenada de los rboles usando un vector para cada rbol.

En la fig. 5.12 se presenta una implementacin posible usando un nico vector para todoslos rboles. Notemos que es necesario introducir el vector compartido como variable global yexterna al universo de definicin de los rboles, dado que es una estructura que utilizarnmuchos rboles diferentes y que no es propiedad de uno solo. Esta solucin viola todas lasreglas de modularidad dadas hasta ahora y se puede pensar que es totalmente descartable.No obstante, es necesario tener en cuenta que el vector desempea exactamente el mismopapel que la memoria dinmica en el caso de los punteros; la nica diferencia es que en elsegundo caso la memoria (que tambin es un objeto global y externo a cualquier mdulo quelo usa) es un objeto annimo y implcitamente referible desde cualquier punto de unprograma. Una opcin diferente (descartada por los motivos que se exponen ms adelante)consiste en declarar el vector como parmetro de las diferentes funciones de los rboles demanera que se encaje el esquema dentro del mtodo de desarrollo modular habitual. Ahorabien, como contrapartida, la signatura de las operaciones es diferente en la especificacin yen la implementacin y, por tanto, se viola el principio de transparencia de la representacin,porque un universo que use esta implementacin ha de seguir unas convencionestotalmente particulares y no extrapolables a cualquier otra situacin. Notemos, eso s, que elsegundo enfoque permite disponer de ms de un vector para almacenar rboles.

El invariante de la memoria es exhaustivo. En la primera lnea se afirma que todo rbolindividual que reside en la memoria est bien formado (en el mismo sentido que larepresentacin de la fig. 5.8) y no incluye ninguna posicin de la pila de sitios libres; acontinuacin, se asegura que toda posicin del vector est dentro de algn rbol, o bien enla pila de sitios libres y, por ltimo, se impide la comparticin de nodos entre los diferentesrboles. Para escribir comdamente el predicado se usan diversas funciones auxiliares: las yaconocidas correcto y nodos, simplemente adaptadas a la notacin vectorial; una funcincadena_der que devuelve la cadena de posiciones que cuelga a partir de una posicin porlos encadenamientos derechos (que se usan en las posiciones libres para formar la pila), yuna cuarta funcin, races, que devuelve el conjunto de posiciones del vector que sonraces de rboles, caracterizadas por el hecho de que no son apuntadas por ninguna otraposicin ni estn en la pila de sitios libres.

En la implementacin se incluye tambin una rutina de inicializacin de la memoria que ha de

rboles 2 3 1__________________________________________________________________________________

ser invocada antes de cualquier manipulacin y que se limita a crear la pila de sitios libres.Adems, se puede incluir otra funcin para averiguar si queda espacio en el vector.

tipo memoria es tuplaA es vector [de 0 a mx-1] de nodosl es nat

ftuplaftipo

tipo privado nodo es tupla etiq es elem; hizq, hder son entero ftupla ftipo

invariante (M es memoria):i: iraces(M): correcto(M, i) nodos(M, i) cadena_der(M, M.sl) = {-1} i: iraces(M): nodos(M, i) cadena_der(M, M.sl) = [-1, mx-1] i: iraces(M): nodos(M, i) = {-1}

donde correcto: memoria entero bool se define:correcto(M, -1) = ciertoi -1 correcto(M, i) = correcto(M, M[i].hizq) correcto(M, M[i].hder)

nodos(M, M[i].hizq) nodos(M, M[i].hder) = {-1} i nodos(M, M[i].hizq) nodos(M, M[i].hder),

donde nodos: memoria entero P(entero) se define como:nodos(M, -1) = {-1}i -1 nodos(M, i) = {i} nodos(M, M[i].hizq) nodos(M, M[i].hder),

donde cadena_der: memoria entero P(entero) se define como:cadena_der(M, -1) = {-1}i -1 cadena_der(M, i) = {i} cadena_der(M, M[i].hder)

y donde races: memoria P(entero) se define como:races(M) = {i[0, mx-1]-nodos(M, M.sl) /

( j: j[0, mx-1]-nodos(M, M.sl): M.A[j].hizq = i M.A[j].hder = i)}

{inicializa(M): accin que es necesario invocar una nica vez antes de crearcualquier rbol que use la memoria M, para crear la pila de sitios libres

P ciertoQ cadena_der(M, M.sl) = [-1, mx-1] }

accin inicializa (sal M es memoria) esvar i es nat fvar

{simplemente, se forma la pila de sitios libres usando el campo hder}para todo i desde 0 hasta mx-2 hacer M.A[i].hder := i+1 fpara todoM.A[mx-1].hder := -1; M.sl := 0

faccin

(a) definicin de la memoria y rutina de inicializacin.Fig. 5.12: implementacin encadenada por vector compartido de los rboles binarios.


universo RBOL_BINARIO_ENC_1_VECTOR (ELEM) esimplementa RBOL_BINARIO (ELEM)usa ENTERO, NAT, BOOLtipo rbol es entero ftipoinvariante (a es rbol): -1 a mx-1funcin crea devuelve rbol esdevuelve -1funcin enraiza (a1 es rbol; v es elem; a2 es rbol) devuelve rbol esvar i es entero fvar

si M.sl = -1 entonces error {el vector es lleno}si no {se obtiene un sitio libre y se deposita el nuevo nodo en l}

i := M.sl; M.sl := M.A[M.sl].hderM.A[i] :=

fsidevuelve ifuncin izq (a es rbol) devuelve rbol es

si a = -1 entonces error {rbol vaco}si no a := M[a].hizqfsi

devuelve afuncin der (a es rbol) devuelve rbol es

si a = -1 entonces error {rbol vaco}si no a := M[a].hderfsi

devuelve afuncin raz (a es rbol) devuelve elem esvar v es elem fvar

si a = -1 entonces error {rbol vaco}si no v := M[a].vfsi

devuelve vfuncin vaco? (a es rbol) devuelve bool esdevuelve a = -1

funiverso

(b) universo de los rboles.

Fig. 5.12: implementacin encadenada por vector compartido de los rboles binarios (cont.).

rboles 2 3 3__________________________________________________________________________________

b) Representacin secuencialSiguiendo la filosofa de la implementacin de estructuras lineales, una representacinsecuencial ha de almacenar los nodos del rbol sin usar campos adicionales deencadenamientos. Ahora bien, as como en las secuencias haba una ordenacin clara de loselementos, en los rboles no ocurre lo mismo. Por ejemplo, en el rbol de la fig. 5.3, qurelacin se puede establecer entre los nodos y ? Intuitivamente,podramos intentar guardar todos los nodos en el orden lexicogrfico dado por lassecuencias del dominio del rbol. Sin embargo, esta estrategia es totalmente ambiguaporque una nica configuracin del vector se puede corresponder con diversos rboles (v.fig. 5.11). Otra posibilidad consiste en deducir una frmula que asigne a cada posible nododel rbol una posicin dentro del vector; en el caso de nodos que no existan, la posicincorrespondiente del vector estar marcada como desocupada. Estudiemos este enfoque.

A

B C

A

BC

A B C

Fig. 5.11: una distribucin de elementos dentro de un vector (a la izquierda) y dos posiblesrboles que se pueden asociar segn el orden lexicogrfico (al medio y a la derecha).

La estrategia adoptada consiste en usar la cadena que identifica la posicin del nodo, demanera que la raz vaya a la primera posicin, el hijo izquierdo de la raz a la segunda, el hijoderecho de la raz a la tercera, el hijo izquierdo del hijo izquierdo de la raz a la cuarta, etc.Concretamente, dado un nodo n = ubicado en el nivel k+1 del rbol, s = s1...sk, sepuede definir la funcin que determina la posicin del vector a la que va a parar cada unode los nodos del rbol como:

Y(s) = (sii = 1

k-1).2k-i+

i = 0

k-1

2i(1+ )

El primer factor da la posicin que ocupa el primer nodo de nivel k+1-simo dentro del rbol8y cada uno de los sumandos del segundo trmino calcula el desplazamiento producido encada nivel.

A partir de esta frmula se pueden derivar las diversas relaciones entre la posicin que ocupaun nodo y la que ocupan sus hijos, hermano y padre, y que se muestran a continuacin. Suclculo por induccin queda como ejercicio para el lector, pero podemos comprobar suvalidez en el ejemplo dado en la fig. 5.13 de forma intuitiva.


8 Se puede demostrar por induccin que el nmero mximo de nodos en el nivel i-simo es 2i-1.

- Hijos: sea el nodo n = tal que (s) = i; su hijo izquierdo n1 = ocupa laposicin (s.1) = 2i y su hijo derecho n2 = la posicin (s.2) = 2i +1.

- Padre: simtricamente, dado el nodo n = tal que k [1, 2] y (sk) = i, i > 1, laposicin que ocupa su padre

5.2.2 Implementacin de los rboles generales

Por lo que respecta a la representacin encadenada, independientemente de si usamospunteros o vectores, la primera opcin puede ser fijar la aridad del rbol y reservar tantoscampos de encadenamiento como valga sta. Esta estrategia, no obstante, presenta elinconveniente de acotar el nmero de hijos de los nodos (cosa a veces imposible) y, adems,incluso cuando esto es posible, el espacio resultante es infrautilizado. Veamos porqu.

Sea n la aridad de un rbol general a, Nai el conjunto de nodos de a que tienen i hijos, y X eY el nmero de encadenamientos nulos y no nulos de a, respectivamente. Obviamente, secumplen:

X= i: 0 i n-1: ||Nai|| . (n-i) (5.1)||Na|| = i: 0 i n: ||Nai|| (5.2)X+ Y= n . ||Na|| (5.3)

Ahora, sea B el nmero de ramas que hay en a. Como que en cada nodo del rbol,exceptuando la raz, llega una y slo una rama, queda claro que:

||Na|| = B + 1 (5.4)y como que de un nodo con i hijos salen i ramas, entonces:

B = i: 1 i n: ||Nai|| . i (5.5)

Combinando (5.4) i (5.5), obtenemos:||Na|| = i: 1 i n: ||Nai|| . i +1 (5.6)

A continuacin, desarrollamos la parte derecha de (5.1) desdoblando el sumatorio en dos,manipulando sus cotas y usando (5.2) y (5.6) convenientmente:

i: 0 i n-1: ||Nai|| . (n-i) =( i: 0 i n-1: ||Nai|| . n) - ( i: 0 i n-1: ||Nai|| . i) =(n . i: 0 i n-1: ||Nai||) - ( i: 1 i n-1: ||Nai|| . i) =(n . i: 0 i n-1: ||Nai||) - ( i: 1 i n: ||Nai|| . i + ||Nan|| . n) =(n . i: 0 i n-1: ||Nai|| + ||Nan|| . n) - ( i: 1 i n: ||Nai|| . i) =(n . i: 0 i n: ||Nai||) - ( i: 1 i n: ||Nai|| . i) = (usando (5.2) y (5.6))(n . ||Na||) - (||Na|| + 1) = (n-1) . ||Na|| + 1

Resumiendo, hemos expresado el nmero X de encadenamientos nulos en funcin delnmero total de nodos, X = (n-1) . ||Na|| + 1, y usando (5.3) podemos comprobar que X esmayor que el nmero de encadenamientos no nulos en un factor n-1, de manera que larepresentacin encadenada propuesta desaprovecha mucho espacio.


La solucin intuitiva a este problema consiste en crear, para cada nodo, una lista deapuntadores a sus hijos. Desde el nodo se accede a la celda que contiene el apuntador alprimer hijo y, desde cada celda, se puede acceder a la celda que contiene el apuntador al hijocorrespondiente y a la que contiene el apuntador al hermano derecho. Ahora bien, estasolucin es claramente ineficiente porque introduce muchos apuntadores adicionales. Laalternativa ms eficiente surge al observar que, dado un nmero fijo de nodos, mientras msgrande es la aridad del rbol que los contiene, mayor es el nmero de encadenamientosdesaprovechados, porque el nmero total crece mientras que el de ramas no vara. Por esto,buscamos una estrategia que convierta el rbol general en binario, para optimizar el espacio.Tomando como punto de partida la lista de apuntadores a los hijos que acabamos deproponer, se puede modificar encadenando directamente los nodos del rbol de maneraque cada nodo tenga dos apuntadores, uno a su primer hijo y otro al hermano derecho. Estaimplementacin se denomina hijo izquierdo, hermano derecho (ing., leftmost-child,right-sibling) y, rotando el rbol resultante, se puede considerar como un rbol binario tal queel hijo izquierdo del rbol binario represente al hijo izquierdo del rbol general, pero el hijoderecho del rbol binario represente al hermano derecho del rbol general (v. fig. 5.14); poresto, la representacin tambin se denomina representacin por rbol binario.

A

B C D E

F G H I J K

A

C

B

D

E

F

GH

I

J

K

Fig. 5.14: un rbol general (izquierda) y su representacin por rbol binario (derecha).

Notemos que el hijo derecho de la raz ser siempre el rbol vaco, porque la raz no tienehermano, por definicin, de modo que se puede aprovechar para encadenar todos losrboles que forman un bosque y, as, un bosque tambin tendr la apariencia de rbolbinario, tal como se muestra en la fig. 5.15.

rboles 2 3 7__________________________________________________________________________________

A ID

B C JE F G

A

I

B D

E

H FC

H

J

G

Fig. 5.15: un bosque con tres rboles (izq.) y su representacin por rbol binario (der.).

En la fig. 5.16 se muestra la implementacin de esta estrategia por punteros. El bosque serepresenta como una cola de rboles encadenados, dado que se necesitan apuntadores alprimer y ltimo rboles; ahora bien, no se efecta una instancia de las colas para optimizar elespacio y aprovechar el encadenamiento a hermano derecho tal como se ha explicado. En lacola se podra poner un elemento fantasma para no distinguir el caso de cola vaca y tambinun contador, pero no se hace porque probablemente las colas sern cortas en el casogeneral; de lo contrario, sera necesario reconsiderar ambas decisiones. En lo que respectaal invariante, es necesario dar propiedades para ambos gneros; como los bosques sepueden considerar como rboles, ambos se ayudan de un predicado auxiliarcorrecto: ^nodo bool, que comprueba las propiedades habituales de los rboles binarios.En los rboles no se puede decir que el encadenamiento derecho sea nulo, porque un rbolque pase a formar parte del bosque no lo cumple.

La representacin secuencial de los rboles generales sigue la misma idea que el casobinario, pero comenzando a numerar por 0 y no por 1 para simplificar las frmulas deobtencin del padre y de los hijos. Es necesario, antes que nada, limitar a un mximo r laaridad mayor permitida en un nodo y tambin el nmero mximo de niveles (para poderdimensionar el vector). Entonces, definimos r como la funcin que asigna a cada nodo unaposicin en el vector tal que, dado s = s1...sk:

(sii = 1

k-1).r k-i+

i = 0

k-1r

i Y(s) =rEl resto de frmulas son tambin una extensin del caso binario y su deduccin quedaigualmente como ejercicio:

- Hijos: sea el nodo n = tal que r (s) = i ; la posicin que ocupa su hijo k-simon'=

- Hermanos: slo es necesario sumar o restar uno a la posicin del nodo en cuestin,segn se quiera obtener el hermano derecho o izquierdo, respectivamente.

5.2.3 Variaciones en los otros modelos de rboles

Por lo que respecta a la extensin de los rboles binarios a los rboles n-arios, en larepresentacin encadenada se puede optar por poner tantos campos como aridad tenga elrbol, o bien usar la estrategia hijo izquierdo, hermano derecho. En cuanto a larepresentacin secuencial, no hay ninguna diferencia en las frmulas del caso generaltomando como r la aridad del rbol.

El modelo de punto de inters presenta ciertas peculiaridades respecto al anterior. En larepresentacin encadenada, puede ser til tener apuntadores al padre para navegarconvenientemente dentro del rbol. Opcionalmente, si la representacin es por hijoizquierdo, hermano derecho, el apuntador al hermano derecho del hijo de la derecha deltodo (que es nulo) se puede reciclar como apuntador al padre y, as, todo nodo puedeacceder sin necesidad de utilizar ms espacio adicional que un campo booleano de marca(en caso de usar punteros), a costa de un recorrido que probablemente ser rpido. Larepresentacin secuencial queda igual y es necesario notar que es precisamente en estemodelo donde s ms til ya que, por un lado, el acceso al padre (y, en consecuencia, acualquier hermano) se consigue sin necesidad de usar ms encadenamientos y, por lo tanto,se puede implementar fcilmente cualquier estrategia de recorrido; por el otro, lasoperaciones individuales sobre nodos se pueden hacer en tiempo constante, porqueconsisten simplemente en modificar una posicin del vector calculada inmediatamente.

5.2.4 Estudio de eficiencia espacial

La cuestin primordial consiste en determinar cuando se comporta mejor una representacinencadenada que una secuencial. Un rbol k-ario de n nodos y k campos de encadenamientoocupa un espacio (k+X)n, siendo X la dimensin de las etiquetas y tomando como unidad elespacio ocupado por un encadenamiento. El mismo rbol representado con la estrategia hijoizquierdo, hermano derecho ocupa slo (X+2)n; el precio a pagar por este ahorro son lasbsquedas (que generalmente sern cortas) de los subrboles y, por ello, generalmente lasegunda implementacin ser preferible a la primera. Si se usa una representacinsecuencial, el rbol ocupar un espacio que depender de su forma: si los rboles con loscuales se trabaja son casi completos habr pocas posiciones desaprovechadas. En general,dada una aridad mxima r y un nmero mximo de niveles k, el espacio necesario para unarepresentacin secuencial es ( i: 1 i k : ri )X = [(rk-1) / (r-1)]X ; esta cifra es muy alta inclusopara r y k no demasiado grandes. Por ejemplo, un rbol 4-ario de 10 niveles como mximo,exige dimensionar el vector de 1.398.101 posiciones; suponiendo que las etiquetas sean

rboles 2 3 9__________________________________________________________________________________

enteros (caso usual), los rboles deben tener del orden de medio milln de nodos para quela representacin secuencial sea mejor. Por ello, slo se usa con rboles casi completos.

Para ser ms precisos, calculamos a continuacin cul es la relacin que debe haber entre elnmero de nodos y el nmero de niveles para que la representacin secuencial realmentesupere la encadenada (implementada por punteros). Supongamos que la aridad del rbol esr y fijemos el nmero k de niveles del rbol. Definimos el factor de carga de un rbol comoel cociente entre el nmero n de nodos y el nmero total de nodos que puede haber en unrbol de aridad r y altura k, = n(r-1) / (rk-1), que cumple 0 1. Sustituyendo, el espaciode la representacin por rbol binario queda (X+2)(r k-1) / (r -1); si comparamos este valorcon el espacio de la representacin secuencial, [(r k-1) / (r -1)]X, puede verse que el factor decarga debe superar X/(X+2) para que la representacin secuencial supere la encadenada. Esdecir, mientras ms grande sea el espacio necesario para almacenar la etiqueta, menosposiciones vacas pueden quedar en el vector propio de la representacin secuencial.

universo RBOL_GENERAL_POR_BINARIO (ELEM) esimplementa RBOL_GENERAL (ELEM)usa BOOLtipo bosque es tupla

prim, ult son ^nodoftupla

ftipotipo rbol es ^nodo ftipotipo privado nodo es tupla

etiq es elemhizq, hder son ^nodo

ftuplaftipoinvariante (b es bosque): correcto(b.prim) b.ultcadena_der(b.prim)

(a es rbol): a NULO correcto(a)donde correcto: ^nodo bool se define como en la fig. 5.8 ysiendo cadena_der: ^nodo P(^nodo) como en el caso binario (v. fig. 5.11)

funcin crea devuelve bosque esdevuelve

funcin cuntos (b es bosque) devuelve bosque esdevuelve cuenta(b.prim)

Fig. 5.16: implementacin hijo izquierdo, hermano derecho de los rboles generales.


funcin inserta (b es bosque; a es rbol) devuelve bosque essi b.ult = NULO entonces b.prim := a si no b.ult^.hder := a fsib.ult := a

devuelve b

funcin i_simo (b es bosque; i es nat) devuelve rbol esdevuelve hermano_derecho_i_simo(b.prim, i)funcin enraiza (b es bosque; v es elem) devuelve rbol esvar p es ^nodo fvar

p := obtener_espaciosi p = NULO entonces error {falta espacio} si no p^ := fsi

devuelve p

{Precondicin (asegurada por el invariante): el puntero a no puede ser NULO}funcin nhijos (a es rbol) devuelve nat esdevuelve cuenta(a^.hizq){Precondicin (asegurada por el invariante): el puntero a no puede ser NULO}funcin subrbol (a es rbol; i es nat) devuelve rbol esdevuelve hermano_derecho_i_simo(a^.hizq, i){Precondicin (asegurada por el invariante): el puntero a no puede ser NULO}funcin raz (a es rbol) devuelve elem esdevuelve a .^v

{Funcin auxiliar cuenta(p): devuelve la longitud de la cadena derecha quecuelga de p. }

funcin privada cuenta (p es ^nodo) devuelve nat esvar cnt es nat fvar

cnt := 0mientras p NULO hacer cnt := cnt + 1; p := p^.hder fmientras

devuelve cnt

{Funcin auxiliar hermano_derecho_i_simo(p, i): avanza i encadenamientosa la derecha a partir de p; da error si no hay suficientes encadenamientos}

funcin priv hermano_derecho_i_simo (p es ^nodo; i es nat) devuelve rbol esvar cnt es nat fvar

cnt := 1mientras (p NULO) (cnt < i) hacer p := p^.hder; cnt := cnt + 1 fmientrassi p = NULO entonces error fsi

devuelve p

funiverso

Fig. 5.16: implementacin hijo izquierdo, hermano derecho de los rboles generales (cont.).

rboles 2 4 1__________________________________________________________________________________

5.3 Recorridos

Usualmente, los programas que trabajan con rboles necesitan aplicar sistemticamente untratamiento a todos sus nodos en un orden dado por la forma del rbol; es lo que sedenomina visitar todos los nodos del rbol. Se distinguen dos categoras bsicas derecorridos: los que se basan en las relaciones padre-hijo de los nodos, que denominaremosrecorridos en profundidad , y los que se basan en la distancia del nodo a la raz, conocidoscomo recorridos en anchura o por niveles. Por lo que se refiere a la signatura, de momentolos consideramos como funciones recorrido : rbol lista_etiq, donde lista_etiq es elresultado de instanciar las listas con punto de inters con el tipo de las etiquetas.

En esta seccin estudiaremos detalladamente el caso de rboles binarios; la extensin alresto de modelos queda como ejercicio para el lector.

5.3.1 Recorridos en profundidad de los rboles binarios

Dado el rbol binario a A 2V, se definen tres recorridos en profundidad (v. fig. 5.17 y 5.18):- Recorrido en preorden (ing., preorder traversal ): si a es el rbol vaco, termina el

recorrido; si no lo es, primero se visita la raz de a y, a continuacin, se recorren enpreorden los subrboles izquierdo y derecho.

- Recorrido en inorden (ing., inorder traversal): si a es el rbol vaco, termina el recorrido;si no lo es, primero se recorre en inorden el subrbol izquierdo de a, a continuacin, sevisita su raz y, por ltimo, se recorre en inorden el subrbol derecho de a.

- Recorrido en postorden (ing., postorder traversal ): si a es el rbol vaco, termina elrecorrido; si no lo es, primero se recorren en postorden sus subrboles izquierdo yderecho y, a continuacin, se visita su raz.

preorden(crea) = creapreorden(enraiza(a1, v, a2)) =

concatena(concatena(inserta(crea, v), preorden(a1)), preorden(a2))inorden(crea) = creainorden(enraiza(a1, v, a2)) = concatena(inserta(inorden(a1), v), inorden(a2))postorden(crea) = creapostorden(enraiza(a1, v, a2)) = inserta(concatena(postorden(a1), postorden(a2)), v)

Fig. 5.17: especificacin ecuacional de los recorridos de rboles binarios, donde concatenaes la concatenacin de dos listas que deja el punto de inters a la derecha del todo.


AC

D E F

G H I

J

B

Recorrido preorden: A, B, D, G, J, C, E, F, H, IRecorrido inorden: D, J, G, B, A, E, C, H, F, IRecorrido postorden: J, G, D, B, E, H, I, F, C, A

Fig. 5.18: un rbol binario y sus recorridos preorden, inorden y postorden.

Notemos que el recorrido postorden se puede definir como el inverso especular delrecorrido preorden, es decir, para obtener el recorrido postorden de un rbol a se puederecorrer a en preorden, pero visitando siempre el subrbol derecho antes que el izquierdo(especular), considerando la lista de etiquetas resultante como el inverso de la solucin. Estavisin ser til posteriormente en la formulacin de los algoritmos de recorrido postorden.

Estos tres recorridos se usan en diferentes contextos de la informtica. Por ejemplo, elrecorrido preorden permite el clculo de atributos heredados de una gramtica.Precisamente, el calificativo "heredados" significa que el hijo de una estructura arborescentehereda (y, posiblemente, modifica) el valor del atributo en el padre. El recorrido inorden de unrbol que cumple ciertas relaciones de orden entre los nodos los obtiene ordenados; enconcreto, si todos los nodos del subrbol de la izquierda presentan una etiqueta menor quela raz y todos los del subrbol de la derecha una etiqueta mayor, y los subrboles cumplenrecursivamente esta propiedad, el rbol es un rbol de bsqueda que se caracterizaprecisamente por la ordenacin de los elementos en un recorrido inorden (v. la seccin 5.6).Por ltimo, el recorrido postorden de un rbol que represente una expresin es equivalentea su evaluacin; en las hojas residen los valores (que pueden ser literales o variables) y en losnodos intermedios los smbolos de operacin que se pueden aplicar sobre los operandos,cuando stos ya han sido evaluados (i.e., visitados).

La implementacin ms inmediata de los recorridos consiste en construir funcionesrecursivas a partir de la especificacin, aplicando tcnicas de derivacin de programas (eneste caso, incluso, por traduccin directa). Estas funciones pueden provocar problemas enla ejecucin aplicadas sobre rboles grandes y con un soporte hardware no demasiadopotente, por ello, es bueno disponer tambin de versiones iterativas, que puedenobtenerse a partir de la aplicacin de tcnicas de transformacin de las versiones recursivas,que se ayudan de una pila que simula los bloques de activacin del ordenador durante laejecucin de estas ltimas.

rboles 2 4 3__________________________________________________________________________________

En la fig. 5.19 se muestra la transformacin de recursivo a iterativo del recorrido en preorden.Se supone que tanto ste como otros recorridos residen en un universo parametrizado porel tipo de las etiquetas, RBOL_BINARIO_CON_RECORRIDOS(ELEM), que enriquece eluniverso de definicin de los rboles binarios, RBOL_BINARIO(ELEM), razn por la que nose accede a la representacin del tipo, sino que se utilizan las operaciones que ofrece suespecificacin. Notemos que los rboles se van guardando dentro de la pila siempre que noestn vacos, y se empila el hijo izquierdo despus del derecho para que salga antes. Quedaclaro que un nodo siempre se inserta en la lista resultado antes de que se inserten susdescendientes.

funcin preorden (a es rbol) devuelve lista_etiq esvar p es pila_rbol; l es lista_etiq; aaux es rbol fvar

p := PILA.crea; l := LISTA_INTERS.creasi vaco?(a) entonces p := empila(p, a) fsimientras vaca?(p) hacer

aaux := cima(p); p := desempila(p) {aaux no puede ser vaco}l := inserta(l, raz(aaux))si vaco?(hder(aaux)) entonces p := empila(p, der(aaux)) fsisi vaco?(hizq(aaux)) entonces p := empila(p, izq(aaux)) fsi

fmientrasdevuelve l

Fig. 5.19: implementacin del recorrido preorden con la ayuda de una pila.

En lo que respecta a la eficiencia, dado el coste constante de las operaciones sobre pilas ylistas, es obvio que el recorrido de un rbol de n nodos es (n), siempre que las operacioneshizq y hder no dupliquen rboles (parece lgico no hacerlo, porque los rboles no semodifican), puesto que a cada paso se inserta una y slo una etiqueta en la lista y, adems,una misma etiqueta se inserta slo una vez. En cuanto al espacio, el crecimiento de la pilaauxiliar depende de la forma del rbol; como sus elementos sern apuntadores (si realmenteestamos trabajando sin copiar los rboles), el espacio total tiene como coste asinttico elnmero esperado de elementos en la pila9. El clculo de la dimensin de la pila sigue elrazonamiento siguiente:

- Inicialmente, hay un nico rbol en la pila.- En la ejecucin de un paso del bucle, la longitud de la pila puede:

disminuir en una unidad, si el rbol que se desempila slo tiene un nodo; quedar igual, si el rbol que se desempila slo tiene subrbol izquierdo o derecho; incrementarse en una unidad, si el rbol que se desempila tiene ambos subrboles.


9 En realidad esta pila estaba implcita en la versin recursiva y, por ello, no se puede considerar unempeoramiento respecto a sta.

El caso peor, pues, es el rbol sin nodos de grado uno en el que todo nodo que es hijoderecho es a la vez una hoja. As, al empilar el rbol formado por el nico hijo izquierdo quetambin es hoja, dentro de la pila habr este rbol y todos los subrboles derechosencontrados en el camino, cada uno de ellos formado por un nico nodo (es decir, lo mspequeos posible); para un rbol de n nodos, la pila puede crecer hasta n/2 elementos. Encambio, el caso mejor es el rbol en el que todo nodo tiene exactamente un subrbol hijo demanera que la pila nunca guarda ms de un elemento. En el caso de un rbol completo la pilacrece hasta log2n al visitar las hojas del ltimo nivel.

A

GF

ED

CB

H I

HIGEC

Fig. 5.20: caso peor en el recorrido preorden en cuanto al tamao de la pila(se identifican los rboles por su raz dentro de la pila).

El recorrido en postorden sigue el mismo esquema, considerado como un recorridopreorden inverso especular (v. fig. 5.21). Para implementar la nocin de especular se empilaantes el hijo derecho que el hijo izquierdo, y para obtener la lista en orden inverso se colocael punto de inters al principio siempre que se inserta un nuevo elemento, de manera que lainsercin sea por la izquierda y no por la derecha (se podra haber requerido un modelo delistas con operacin de insertar por el principio). De acuerdo con la especificacin, al final delrecorrido es necesario mover el punto de inters a la derecha del todo, para dejar el resultadoen el mismo estado que los otros algoritmos vistos hasta ahora. El coste del algoritmo estotalmente equivalente al recorrido preorden.

Por ltimo, el recorrido en inorden se obtiene fcilmente a partir del algoritmo de la fig. 5.19:cuando se desempila un rbol, su raz no se inserta directamente en la lista sino que sevuelve a empilar, en forma de rbol con un nico nodo, entre los dos hijos, para obtenerla enel momento adecuado, tal como se presenta en la fig. 5.22. Consecuentemente, la pilapuede crecer todava ms que en los dos recorridos anteriores. En el caso peor, que es elmismo rbol que el de la fig. 5.20, puede llegar a guardar tantos elementos como nodostiene el rbol. Adems, el algoritmo es ms lento, porque en ese caso no todas lasiteraciones aadirn nodos a la lista solucin (eso s, no se empeorar el coste asinttico). Enel caso peor de la fig. 5.20, primero se empilan n subrboles de un nodo en n/2 iteracionesy, a continuacin, se visitan sus races en n vueltas adicionales del bucle.

rboles 2 4 5__________________________________________________________________________________

funcin postorden (a es rbol) devuelve lista_etiq esvar p es pila_rbol; l es lista_etiq; aaux es rbol fvar


aaux := cima(p); p := desempila(p)l := principio(inserta(l, raz(aaux)))si vaco?(hizq(aaux)) entonces p := empila(p, hizq(aaux)) fsisi vaco?(hder(aaux)) entonces p := empila(p, hder(aaux)) fsi

fmientrasmientras final?(l) hacer l := avanza(l) fmientras

devuelve l

Fig. 5.21: implementacin del recorrido postorden con la ayuda de una pila.

funcin inorden (a es rbol) devuelve lista_etiq esvar p es pila_rbol; l es lista_etiq; aaux es rbol fvar


aaux := cima(p); p := desempila(p) {aaux no puede ser vaco}si vaco?(hizq(aaux)) vaco?(hder(aaux)) entonces

l := inserta(l, raz(aaux)) {hay un nico nodo, que se visita}si no {se empila la raz entre los dos hijos}

si vaco?(hder(aaux)) entonces p := empila(p, hder(aaux)) fsip := empila(p, enraiza(crea, raz(aaux), crea)))si vaco?(hizq(aaux)) entonces p := empila(p, hizq(aaux)) fsi

fsifmientras

devuelve l

Fig. 5.22: implementacin del recorrido inorden con la ayuda de una pila.

Una variante habitual presente en diversos textos consiste en incluir la visita de los vrticesdentro del recorrido, de manera que no sea necesario construir una lista primero y despusrecorrerla. Evidentemente, el aumento de eficiencia de esta opcin choca frontalmente conla modularidad del enfoque anterior, porque es necesario construir un nuevo algoritmo derecorrido para cada tratamiento diferente que surja, a no ser que el lenguaje permitierafunciones de orden superior de manera que el tratamiento de los nodos fuera un parmetroms de los recorridos10. Una opcin diferente que apunta en el mismo sentido, pero sin


10 E incluso as hay restricciones, porque sera necesario declarar la signatura de este parmetro yesto limitara el conjunto de acciones vlidas

perder modularidad, es adoptar el modelo de los rboles binarios con punto de inters paraobtener los nodos uno a uno segn las diferentes estrategias.

5.3.2 rboles binarios enhebrados

Los rboles enhebrados (ing., threaded tree) son una representacin ideada por A.J. Perlis yC. Thornton en el ao 1960 (Communications ACM , 3), que permite implementar losrecorridos sin necesidad de espacio adicional (como mucho, un par de booleanos de marcaen cada nodo), y se basa en la propiedad ya conocida de que una representacinencadenada normal de los rboles desaprovecha muchos apuntadores que no apuntan aningn nodo. En el caso binario, y a partir de la frmula calculada en el apartado 5.2.2, de los2n encadenamientos existentes en un rbol de n nodos hay exactamente n+1 sin usar. Porello, es bueno plantearse si se pueden reciclar estos apuntadores para llevar a cabocualquier otra misin, y de ah surge el concepto de hebra (ing., thread): cuando un nodo notiene hijo derecho, se sustituye el valor nulo del encadenamiento derecho por su sucesor eninorden, y cuando no tiene hijo izquierdo, se sustituye el valor nulo del encadenamientoizquierdo por su predecesor en inorden (v. fig. 5.23); de esta manera, se favorece laimplementacin de los recorridos sobre el rbol.

A

C

D E F

G H I

J

B

Fig. 5.23: el rbol binario de la fig. 5.18, enhebrado en inorden(las hebras son las rayas discontinuas).

La eleccin del enhebrado inorden y no de otro se justifica por la fcil implementacin de losdiferentes recorridos. El punto clave consiste en definir cul es el primer nodo del rbol quese ha de visitar y como se calcula el siguiente nodo dentro del recorrido:

- Preorden: el primer nodo es la raz del rbol (si la hay). Dado un nodo n, su sucesor enpreorden es el hijo izquierdo, si tiene; si no, el hijo derecho, si tiene. Si es una hoja, esnecesario seguir las hebras derechas (que llevan a nodos antecesores de n, yavisitados por definicin de recorrido preorden, tales que n forma parte de su subrbolizquierdo) hasta llegar a un nodo que, en lugar de hebra derecha, tenga hijo derecho,

rboles 2 4 7__________________________________________________________________________________

que pasa a ser el sucesor en preorden.

- Inorden: el primer nodo (si lo hay) se localiza bajando recursivamente por la rama msizquierda del rbol. Dado un nodo n (que cumple que los nodos de su rbol izquierdoya han sido visitados, por definicin de recorrido inorden), su sucesor en inorden es elprimero en inorden del hijo derecho, si tiene; si no, simplemente se sigue la hebra (querecordamos que apunta precisamente al sucesor en inorden de n).

- Postorden: es inmediato a partir de la definicin como preorden inverso especular.

En la fig. 5.26 se presenta la implementacin de estos recorridos. Como se est explotandouna caracterstica de la representacin de los rboles, los algoritmos se incluyen dentro delmismo universo de definicin del tipo porque as pueden acceder a ella. En la figura se haoptado por una representacin con punteros (queda como ejercicio la representacin porvectores). El esquema de los tres recorridos es casi idntico y slo cambia la implementacinde la estrategia; notemos el uso de un puntero auxiliar que desempea el papel de elementoactual en el recorrido. El invariante incorpora el concepto de hebra y garantiza, por un lado,que tanto el hijo izquierdo del primero en inorden como el hijo derecho del ltimo en inordenvalen NULO y, por otro, que las hebras apuntan a los nodos correctos segn la estrategiaadoptada. Los predicados correcto, cadena_izq y cadena_der varan respecto a la fig. 5.11,porque el caso trivial deja de ser el puntero NULO y pasa a ser la existencia de hebra. Elpredicado nodos, en cambio, queda igual, porque la insercin reiterada de algunos nodosno afecta al resultado. Las pre y postcondiciones de las funciones auxiliares, as como losinvariantes de los bucles, son inmediatas y quedan como ejercicio para el lector.

Dado un rbol enhebrado de n nodos, su recorrido siguiendo cualquier estrategia queda(n). En concreto, dado que cada hebra se sigue una nica vez y, o bien slo las hebras de laizquierda, o bien slo las de la derecha, el nmero total de accesos adicionales a los nodosdel rbol durante el recorrido es (n+1) / 2.

El ltimo paso consiste en modificar las operaciones habituales de la signatura de los rbolesbinarios para adaptarlas a la estrategia del enhebrado. En la fig. 5.24 se presenta el esquemageneral de la operacin de enraizar (la obtencin de los hijos es la inversa); notemos que elmantenimiento del enhebrado exige buscar el primero y el ltimo en inorden del rbol y, portanto, la representacin clsica de los rboles binarios no asegura el coste constante de lasoperaciones que, en el caso peor, pueden llegar a ser incluso lineales. Si este inconvenientese considera importante, se pueden aadir a la representacin de los rboles dosapuntadores adicionales a estos elementos. En la fig. 5.25 se muestra la nuevarepresentacin del tipo y la codificacin de enraiza con esta estrategia; sera necesarioretocar los algoritmos de la fig. 5.26 para adaptarlos a la nueva situacin. Si la formacin delrbol es previa a cualquier recorrido y se prev recorrerlo mltiples veces, se puede optar pormantener la representacin no enhebrada durante los enraizamientos y enhebrar el rbolantes del primer recorrido.


B AA Benraizar

Fig. 5.24: esquema general del enraizamiento de rboles binarios enhebrados inorden.

tipo rbol estupla

prim, ult, raz son ^nodoftupla

ftipotipo privado nodo es

tuplav es etiqhizq, hder son boolhizq, hder son ^nodo

ftuplaftipoinvariante (a es rbol): el mismo que la fig. 5.24 y

(a.raz = NULO a.prim = NULO) (a.prim = NULO a.ult = NULO) a.raz NULO (a.prim^.hizq = NULO) (a.ult^.hder = NULO)

funcin enraiza (a1 es rbol; v es elem; a2 es rbol) devuelve rbol esvar a es rbol fvar

a.raz := obtener_espaciosi a.raz = NULO entonces error {no hay espacio}si no {primero enraizamos normalmente}

a.raz^.v := v; a.raz^.hizq := a1.raz; a.raz^.hder:= a2.raza.raz^.hizq := (a1.raz NULO); a.raz^.hder := (a2.raz NULO)

{a continuacin, se enhebra el rbol en inorden}si a1.prim NUL entonces a.prim := a1.prim si no a.prim := a fsisi a2.ult NUL entonces a.ult := a2.ult si no a.ult := a fsisi a1.ult NULO entonces a1.ult^.hder := a.raz fsisi a2.prim NULO entonces a2.prim^.hizq := a.raz fsi

fsidevuelve a

Fig. 5.25: algoritmo de enraizamiento de rboles binarios enhebrados inorden.

rboles 2 4 9__________________________________________________________________________________

tipo rbol es ^nodo ftipotipo privado nodo es

tuplav es etiq; hizq, hder son ^nodohizq, hder son bool11 {indican si los encadenamientos son hebras}

ftuplaftipoinvariante (a es rbol): correcto(a) p: pnodos(a)-{NULO}:

p^.hizq = NULO (pcadena_izq(a) p .^ hizq) p^.hder = NULO (pcadena_der(a) p .^ hder) ( p .^ hizq p^.hizq NULO) pcadena_izq(p^.hizq^.hder) ( p .^ hder p^.hder NULO) pcadena_der(p^.hder^.hizq)

donde correcto: ^nodo bool se define como:1) correcto(NULO) = cierto {caso trivial}2) p NULO p .^ hizq p .^ hder correcto(p) = cierto {hoja}3) p NULO p^. hizq p .^ hder correcto(p) = {tiene los dos hijos}

correcto(p^.hizq) correcto(p^.hder) nodos(p^.hizq) nodos(p^.hder) = pnodos(p^.hizq) nodos(p^.hder)

4) p NULO p .^ hizq p .^ hder {slo tiene hijo derecho}correcto(p) = correcto(p^.hder) pnodos(p^.hder)

5) p NULO p .^ hizq p .^ hder {slo tiene hijo izquierdo}correcto(p) = correcto(p^.hizq) pnodos(p^.hizq),

donde cadena_izq: ^nodo P(^nodo) se define (y cadena_der simtricamente): p .^ hizq cadena_izq(p) = p .^ hizq cadena_izq(p) = {p} cadena_izq(p^.hizq)

y donde nodos: ^nodo P(^nodo) se define de la manera habitual

funcin privada siguiente_preorden (act es rbol) devuelve rbol essi act^ . hizq entonces act := act^.hizq {si hay hijo izquierdo, ya lo tenemos}si no {es necesario remontar por las hebras hasta llegar a un nodo con hijo derecho}

mientras act^ . hder hacer act := act^.hder fmientrasact := act^.hder

fsidevuelve act

Fig. 5.26: implementacin de los recorridos en profundidad con rboles enhebrados.


11 Estos dos booleanos se pueden obviar en caso de representacin por vectores y puede codificarsela existencia o no de hijo con el signo de los encadenamientos: un valor negativo significa que elencadenamiento representa un hijo y es necesario tomar su valor absoluto para acceder a l.

funcin privada primero_inorden (act es ^nodo) devuelve ^nodo essi act NULO entonces {es necesario bajar por la rama izquierda, recursivamente}

mientras act^ . hizq hacer act := act^.hizq fmientrasfsi

devuelve actfuncin privada siguiente_inorden (act es ^nodo) devuelve ^nodo es

si act^. hder entonces act := act^.hder {se sigue la hebra}si no act := primero_inorden(act^.hder) {busca primero en inorden del hijo derecho}fsi

devuelve actfuncin privada siguiente_preorden_especular (act es ^nodo) devuelve ^nodo es

si act^ . hder entonces act := act^.hder {si hay hijo derecho, ya lo tenemos}si no {es necesario remontar por las hebras hasta llegar a un nodo con hijo izquierdo}

mientras act^ . hizq hacer act := act^.hizq fmientrasact := act^.hizq

fsidevuelve actfuncin preorden (a es rbol) devuelve lista_etiq esvar l es lista_etiq; act es ^nodo fvar

l := LLISTA_INTERS.crea; act := amientras act NULO hacer l := inserta(l, act^.v); act := siguiente_preorden(act) fmientras

devuelve lfuncin inorden (a es rbol) devuelve lista_etiq: como preorden, pero inicializando act

al primero inorden, act := primero_inorden(act), y avanzando con siguiente_inordenfuncin postorden (a es rbol) devuelve lista_etiq: como preorden, pero avanzando

con siguiente_preorden_especular, colocando la lista al inicio justo antes de insertarel elemento actual y, al acabar, colocarla al final

Fig. 5.26: implementacin de los recorridos en profundidad con rboles enhebrados (cont.).

5.3.3 Recorrido por niveles de los rboles binarios

El recorrido por niveles o por anchura (ing., level order o breadth traversal ) de un rbolbinario consiste en visitar primero la raz del rbol, despus los nodos que estn en el nivel 2,despus los que estn en el nivel 3, etc., hasta visitar los nodos del ltimo nivel del rbol;para cada nivel, los nodos se visitan de izquierda a derecha. Como resultado, el orden devisita se corresponde con la numeracin presentada en el punto 5.2.1 b, ya que se basa enla misma idea. Por ejemplo, en el rbol de la fig. 5.18 se obtiene el recorrido A, B, C, D, E, F,G, H, I, J. Esta poltica de visita por distancia a la raz es til en determinados contextos dondelas ramas tienen algn significado especialmente significativo.

rboles 2 5 1__________________________________________________________________________________

La especificacin del recorrido por niveles no es tan sencilla como la de los recorridos enprofundidad dado que, en este caso, no importa tanto la estructura recursiva del rbol comola distribucin de los nodos en los diferentes niveles. En la fig. 5.27 se muestra unapropuesta que usa una cola para guardar los subrboles pendientes de recorrer en el ordenadecuado. Notemos que la cola mantiene la distribucin por niveles de los nodos y obliga a laintroduccin de una operacin auxiliar niveles_con_cola. Otra opcin es formar listas depares etiqueta-nivel que, correctamente combinadas, ordenen los nodos segn laestrategia. Sea como sea, el resultado peca de una sobreespecificacin causada por laadopcin de la semntica inicial como marco de trabajo.

niveles(a) = niveles_con_cola(encola(COLA.crea, a))niveles_con_cola(crea) = LISTA_INTERS.crea[vaco?(cabeza(encola(c, a)))]

niveles_con_cola(encola(c, a)) = niveles_con_cola(desencola(encola(c, a)))[vaco?(cabeza(encola(c, a)))]

niveles_con_cola(encola(c, a)) =concatena(inserta(crea, raz(cabeza(encola(c, a)))),

niveles_con_cola(encola(encola(desencola(encola(c, a),hizq(cabeza(encola(c, a))),

hder(cabeza(encola(c, a)))))Fig. 5.27: especificacin del recorrido por niveles con la ayuda de una cola.

En la fig. 5.28 se presenta la implementacin del algoritmo siguiendo la misma estrategia quela especificacin, procurando simplemente no encolar rboles vacos. Observemos lasimilitud con el algoritmo iterativo del recorrido postorden de la fig. 5.21, cambiando la pila poruna cola. As mismo, su coste asinttico es tambin (n) para un rbol de n nodos.

funcin niveles (a es rbol) devuelve lista_etiq esvar c es cola_rbol; l es lista_etiq; aaux es rbol fvar

c := COLA.crea; l := LISTA_INTERS.creasi vaco?(a) entonces c := encola(p, a) fsimientras vaca?(c) hacer

aaux := cabeza(c); c := desencola(c) {aaux no puede ser vaco}l := inserta(l, raz(aaux))si vaco?(hizq(aaux)) entonces c := encola(c, hizq(aaux)) fsisi vaco?(hder(aaux)) entonces c := encola(c, hder(aaux)) fsi

fmientrasdevuelve l

Fig. 5.28: implementacin del recorrido por niveles con la ayuda de una cola.


En lo que respecta a la dimensin de la cola, es necesario notar que, al visitar el nodo n Naresidente en el nivel k del rbol a, en la cola slo habr los subrboles tales que su raz x esten el nivel k de a (porque x estar ms a la derecha que n dentro de a), o bien en el nivel k+1de a (porque x ser hijo de un nodo ya visitado en el nivel k ). Por este motivo, el caso peores el rbol en que, despus de visitar el ltimo nodo del penltimo nivel, en la cola hay todoslos subrboles posibles cuya raz est en el ltimo nivel. Es decir, el rbol peor es el rbolcompleto, donde hay n = 2k-1 nodos dentro del rbol y, as, en el ltimo nivel hayexactamente 2k-1 nodos.

5.4 Relaciones de equivalencia

En el resto del captulo se estudia la aplicacin de los rboles en la implementacin eficientede diversos tipos de datos. Para empezar, en esta seccin se quieren implementar losconjuntos compuestos de conjuntos de elementos, con la particularidad de que ningnelemento puede aparecer en ms de un conjunto componente. A esta clase de conjuntoslos denominamos relaciones de equivalencia dado que, normalmente, los conjuntoscomponentes representan clases formadas a partir de una relacin reflexiva, simtrica ytransitiva. No obstante, en la literatura del tema los podemos encontrar bajo otrasdenominaciones: estructuras de particin, MFsets, union-find sets y otras que, aun cuandoreflejan las operaciones que ofrecen, no denotan tan fielmente su significado.

Hay diversos modelos posibles para el TAD de las relaciones de equivalencia que se puedenadaptar los unos mejor que los otros a determinados contextos. En esta seccin definimosun modelo que asocia un identificador a cada clase de equivalencia para poder referirse aellas desde otras estructuras externas; para simplificar, consideramos que los identificadoresson naturales. Dado V el conjunto base de los elementos de la relacin, podemos definir lasrelaciones de equivalencia R V como funciones de los elementos a los naturales, f : V N ,siendo f(v) el identificador de la clase a la que pertenece el elemento v, v V.

Para R R V, v V e i1,i2 N , definimos las siguientes operaciones sobre el TAD:

- Crear la relacin vaca: crea, devuelve la relacin tal que cada elemento forma una clasepor s mismo; es decir, devuelve la relacin I que cumple: v,w V : v w I(v) I(w).

- Determinar la clase en la que se halla un elemento: clase(R, v), devuelve el natural queidentifica la clase de equivalencia dentro de R que contiene v ; es decir, devuelve R(v).

- Establecer la congruencia entre dos clases: fusiona(R, i1, i2), devuelve la relacinresultado de fusionar todos los elementos de las dos clases identificadas por i1 e i2 enuna misma clase, o deja la relacin inalterada si i1 o i2 no identifican ninguna clase dentrode la relacin, o bien si i1 = i2; es decir, devuelve la relacin R' que cumple:

rboles 2 5 3__________________________________________________________________________________

v: vV: (R(v) = i1 R(v) = i2) R'(v) = i1 v: vV: (R(v) = i1 R(v) = i2) R'(v) = i2

v: vV: (R(v) i1 R(v) i2) R'(v) = R(v).- Averiguar el nmero de clases de la relacin: cuntos?(R), devuelve el nmero de

naturales que son imagen de algn elemento, ||{i / i codom(R)}||.

Notemos que el modelo no determina cules son los identificadores iniciales de las clases,porque no afecta al funcionamiento del tipo, slo obliga a que sean diferentes entre ellos. Sepuede decir lo mismo por lo que se refiere al identificador de la clase resultante de hacer unafusin y, por ello, no se obliga a que sea uno u otro, sino que simplemente se establece quetodos los elementos de una de las dos clases fusionadas vayan a parar a la otra.

En la fig. 5.29 se muestra el contexto de uso habitual de este TAD de las relaciones. Primero,se forma la relacin con tantas clases como elementos, a continuacin, se organiza un bucleque selecciona dos elementos segn un criterio dependiente del algoritmo concreto y, siestn en clases diferentes, las fusiona, y el proceso se repite hasta que la relacin consta deuna nica clase. En el apartado 6.5.2 se muestra un algoritmo sobre grafos, el algoritmo deKruskal para el clculo de rboles de expansin minimales, que se basa en este esquema.Notemos que el nmero mximo de fusiones que se pueden efectuar sobre una relacin esn -1, siendo n = ||V||, pues cada fusin junta dos clases en una, por lo que n-1 fusionesconducen a una relacin con una nica clase. En cambio, el nmero de ejecuciones declase y cuntos no puede determinarse con exactitud, ya que el criterio de seleccin puedegenerar pares de elementos congruentes un nmero elevado de veces. Eso s, comomnimo el algoritmo ejecutar clase 2(n-1) veces y cuntos, n veces. Adems, si la seleccinasegura que no puede generarse el mismo par de elementos ms de una vez, la cotasuperior del nmero de ejecuciones de estas operaciones es n(n-1) para clase y n(n-1)/2 + 1para cuntos, porque el nmero diferente de pares (no ordenados) es k : 1 k n : k.

R := creamientras cuntos?(R) > 1 hacer

seleccionar dos elementos v1 y v2 segn cierto criterioi1 := clase(R, v1); i2 := clase(R, v2)si i1 i2 entonces R := fusiona(R, i1, i2) fsi

fmientras

Fig. 5.29: algoritmo que usa las relaciones de equivalencia.

A veces este modelo de las relaciones de equivalencia no se adapta totalmente a losrequerimientos de una aplicacin concreta; las variantes ms habituales son:


- Considerar la relacin como una funcin parcial, de manera que haya elementos delconjunto de base que no estn en ninguna clase, en cuyo caso, se acostumbra asustituir la operacin crea por otras dos: la primera, para crear la relacin "vaca" (esdecir, sin ninguna clase), y una segunda para aadir a la relacin una nueva clase quecontenga un nico elemento que se explicita como parmetro. A veces, el identificadorde la clase vendr asignado por el contexto (es decir, ser un parmetro ms).

- Identificar las clases no por naturales, sino por los elementos que la forman. Segn esteesquema, la operacin clase se sustituye por otra que, dados dos elementos,comprueba si son congruentes o no, mientras que la operacin fusiona tiene comoparmetros dos elementos que representan las clases que es necesario fusionar.

En la fig. 5.31 se muestra la especificacin del tipo releq de las relaciones de equivalencia.Para dotar al TAD de un significado dentro de la semntica inicial (es decir, para construir ellgebra cociente de trminos asociada al tipo con la cual se establece un isomorfismo) esnecesario resolver las dos indeterminaciones citadas al describir el modelo. Por lo querespecta al identificador de la fusin, se elige arbitrariamente el ltimo parmetro de la funcincomo identificador de la clase resultado. En lo que se refiere a los identificadores iniciales, setoma la opcin de numerar las clases de uno al nmero de elementos. Para poder escribir laespecificacin con estas convenciones, se requieren diversas operaciones y propiedadessobre los elementos: han de ser un tipo con un orden total definido que permita identificarcul es el primer elemento, prim, cul es el ltimo, ult, y cmo se obtiene el sucesor a unelemento dado, suc ; as, se podrn generar todos los elementos en la creacin uno trasotro. Tambin se dispondr de las operaciones de igualdad. Adems, para uso futuro,requerimos una constante n que d el nmero de elementos dentro del gnero y unaoperacin de comparacin < que representa el orden total. En la fig. 5.30 se muestra eluniverso de caracterizacin que responde a esta descripcin.

universo ELEM_ORDENADO caracterizausa NAT, BOOLtipo elemops prim, ult: elem

suc: elem elem_=_, __, _ 0 = cierto

...reflexividad, simetra y transitividad de _=_(v w) = (v = w)...antireflexividad, antisimetra y transitividad de _

Por lo que respecta a la estrategia de la especificacin, se introducen dos operacionesprivadas, vaca (que representa la relacin sin ninguna clase) e inserta (que aade unelemento a una clase dada, que puede no existir), que forman un conjunto de constructorasgeneradoras impuras que facilitan considerablemente la especificacin. Tambin surgenotras operaciones auxiliares: vaca?, que comprueba si el identificador dado denota una claseexistente, y pon_todos, que se encarga de construir una a una las clases iniciales aadiendolos elementos desde el primero hasta el ltimo. Los errores que aparecen se escriben por laaplicacin estricta del mtodo general de especificacin presentado en la seccin 1.3, peroes imposible que se produzcan, dado el uso que se hace de las operaciones.

universo RELACIN_DE_EQUIVALENCIA(ELEM_ORDENADO) esusa NAT, BOOLtipo releqops privada vaca: releq

privada inserta: releq elem nat releqcrea: releqclase: releq elem natfusiona: releq nat nat releqcuntos?: releq natprivada vaca?: releq nat boolprivada pon_todos: elem nat releq

errores rreleq; i1,i2nat; veleminserta(inserta(r, v, i1), v, i2); clase(vaca); [i > n NAT.ig(i, cero)] inserta(R, v, i)

ecns rreleq; i,i1,i2nat; v,v1,v2eleminserta(inserta(r, v1, i1), v2, i2) = inserta(inserta(r, v2, i2), v1, i1)crea = pon_todos(prim, 1)clase(inserta(r, v, i), v) = i[v1 v2] clase(inserta(r, v1, i), v2) = clase(r, v2)fusiona(vaca, i1, i2) = vaca[NAT.ig(i, i1)] fusiona(inserta(r, v, i), i1, i2) = inserta(fusiona(r, i1, i2), v, i2) [NAT.ig(i, i1)] fusiona(inserta(r, v, i), i1, i2) = inserta(fusiona(r, i1, i2), v, i) cuntos?(vaca) = 0[vaca?(r, i)] cuntos?(inserta(r, v, i)) = cuntos?(r) + 1[ vaca?(r, i)] cuntos?(inserta(r, v, i)) = cuntos?(r)vaca?(vaca, i) = cierto; vaca?(inserta(c, v, i1), i2) = vaca?(c, i2) NAT.ig(i1, i2)pon_todos(ult, n) = inserta(vaca, ult, n)[v ult] pon_todos(v, i) = inserta(pon_todos(suc(v), i+1), v, i)

funiverso

Fig. 5.31: especificacin del TAD de las relaciones de equivalencia.


En el resto del apartado nos ocupamos de la implementacin del TAD, partiendo de dosrepresentaciones lineales diferentes y llegando a una arborescente que asegura un costeasinttico medio constante en todas las operaciones. Supondremos que el conjunto debase es un tipo escalar que permite indexar directamente un vector12; en caso contrario, seranecesario organizar una tabla de dispersin para mantener los costes que aqu se darn o,en el caso que la dispersin no sea aconsejable (v. seccin 5.6), cualquier otra estructuraque incrementar el coste de las operaciones.

5.4.1 Implementaciones lineales

Dado que el algoritmo de la fig. 5.29 ejecuta ms veces clase que fusiona, nos planteamossu optimizacin. Una representacin intuitiva consiste en organizar un vector indexado porlos elementos, tal que en cada posicin se almacene el identificador de la clase en la queresida el elemento. As, el coste temporal de clase queda constante (acceso directo a unaposicin del vector), mientras que fusiona es lineal, porque su ejecucin exige modificar elidentificador de todos aquellos elementos que cambien de clase mediante un recorrido delvector; el coste de n -1 ejecuciones de fusiona es, pues, (n2). Por otro lado, el coste decrea es lineal (suficientemente bueno, puesto que con toda probabilidad slo se ejecutaruna vez) y el de cuntos? ser constante si aadimos un contador.

En la fig. 5.32 se muestra una variante de este esquema que puede llegar a mejorar el costeasinttico de fusiona sin perjudicar clase. Por un lado, se encadenan todos los elementosque estn en la misma clase; as, al fusionar dos clases no es necesario recorrer todo elvector para buscar los elementos que cambian de clase. Por otro lado, se introduce unnuevo vector indexado por identificadores que da acceso al primer elemento de la cadena decada clase.

identificadores

elementos

k

kv1 v2 v3

k k

Fig. 5.32: implementacin lineal del TAD de las relaciones de equivalencia.

rboles 2 5 7__________________________________________________________________________________

12 Esta suposicin es lgica, dados los requerimientos sobre los elementos establecidos en laespecificacin.

Est claro que la nica operacin que vara de coste es fusiona; concretamente, la ejecucinde fusiona(R, i1, i2) exige modificar slo las posiciones del vector de elementos que estndentro d

Documents

Diseño y estructura de datos y especificación de problemas