ARBOLES GENERALES

ARBOLES GENERALES 1. INTRODUCCIÓN. Hasta ahora las estructuras de datos que hemos estudiado eran de tipo lineal, o sea,existía una relación de anterior y siguiente entre los elementos que la componían(cada elemento tendrá uno anterior y otro posterior , salvo los casos de primero y último).Pues bien, aquí se va a estudiar una estructuración de los datos más compleja: los árboles. Este tipo de estructura es usual incluso fuera del campo de la informática.El lector seguramente conoce casos como los árboles gramaticales para analizar oraciones,los árboles genealógicos ,representación de jerarquías,etc...La estructuración en árbol de los elementos es fundamental dentro del campo de la informática aplicándose en una amplia variedad de problemas como veremos más adelante. En principio podemos considerar la estructura de árbol de manera intuitiva como una estructura jerárquica.Por tanto,para estructurar un conjunto de elementos ei en árbol, deberemos escoger uno de ellos e1 al que llamaremos raíz del árbol.Del resto de los elementos se selecciona un subconjunto e2,...,ek estableciendo una relación padre-hijo entre la raíz y cada uno de dichos elementos de manera que e1 es llamado el padre de e2,de e3,...ek y cada uno de ellos es llamado un hijo de e1.Iterativamente podemos realizar la misma operación para cada uno de estos elementos asignando a cada uno de ellos un número de 0 o más hijos hasta que no tengamos más elementos que insertar.El único elemento que no tiene padre es e1,la raíz del árbol.Por otro lado hay un conjunto de elementos que no tienen hijos aunque sí padre que son llamados hojas.Como hemos visto la relación de paternidad es una relación uno a muchos. Para tratar esta estructura cambiaremos la notación: Las listas tienen posiciones.Los árboles tienen nodos. Las listas tienen un elemento en cada posición.Los árboles tienen una etiqueta en cada nodo (algunos autores distinguen entre árboles con y sin etiquetas.Un árbol sin etiquetas tiene sentido aunque en la inmensa mayoría de los problemas necesitaremos etiquetar los nodos. Es por ello por lo que a partir de ahora sólo haremos referencia a árboles etiquetados). Usando esta notación,un árbol tiene uno y sólo un nodo raíz y uno o más nodos hoja. Desde un punto de vista formal la estructura de datos árbol es un caso particular de grafo, más concretamente,en la teoría de grafos se denota de forma similar como árbol dirigido. A pesar de ello,la definición formal más usual de árbol en ciencias de la computación es la recursiva: El caso básico es un árbol con un único nodo.Lógicamente este nodo es a la vez raíz y hoja del árbol. Para construir un nuevo árbol a partir de un nodo nr y k árboles A1 ,A2,...,Ak de raíces n1,n2,...,nk con N1,N2,...,Nk elementos cada uno establecemos una relación padre-hijo entre nr y cada una de las raíces de los k árboles.El árbol resultante de N=1 + N1 + ... + Nk nodos tiene como raíz el nodo nr, los nodos n1,n2,...,nk son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. Además a cada uno de los Ai se les denota subárboles de la raíz. Ejemplo: Consideremos el ejemplo de la siguiente figura. Podemos observar que cada uno de los identificadores representa un nodo y la relación padre-hijo se señala con una línea.Los árboles normalmente se presentan en forma descendente y se interpretan de la siguiente forma: E es la raíz del árbol. S1,S2,S3 son los hijos de E. S1,D1 componen un subárbol de la raíz. D1,T1,T2,T3,D3,S3 son las hojas del árbol. etc... Además de los términos introducidos consideraremos la siguiente terminología: Grado de salida o simplemente grado.Se denomina grado de un nodo al número de hijos que tiene.Así el grado de un nodo hoja es cero.En la figura anterior el nodo con etiqueta E tiene grado 3. Caminos.Si n1,n2,...,nk es una sucesión de nodos en un árbol tal que ni es el padre de ni+1 para 1<=i<=k-1 ,entonces esta sucesión se llama un camino del nodo ni al nodo nk.La longitud de un camino es el número de nodos menos uno, que haya en el mismo.Existe un camino de longitud cero de cada nodo a sí mismo.Ejemplos sobre la figura anterior: E,S2,D2,T3 es un camino de E a T3 ya que E es padre de S2,éste es padre de D2,etc. S1,E,S2 no es un camino de S1 a S2 ya que S1 no es padre de E. Ancestros y descendientes.Si existe un camino,del nodo a al nodo b ,entonces a es un ancestro de b y b es un descendiente de a.En el ejemplo anterior los ancestros de D2 son D2,S2 y E y sus descendientes D2,T1,T2 y T3(cualquier nodo es a la vez ancestro y descendiente de sí mismo). Un ancestro o descendiente de un nodo,distinto de sí mismo,se llama un ancestro propio o descendiente propio respectivamente.Podemos definir en términos de ancestros y descendientes los conceptos de raíz,hoja y subárbol: En un árbol,la raíz es el único nodo que no tiene ancestros propios. Una hoja es un nodo sin descendientes propios. Un subárbol de un árbol es un nodo,junto con todos sus descendientes. Algunos autores prescinden de las definiciones de ancestro propio y descendiente propio asumiendo que un nodo no es ancestro ni descendiente de sí mismo. Altura.La altura de un nodo en un árbol es la longitud del mayor de los caminos del nodo a cada hoja.La altura de un árbol es la altura de la raíz.Ejemplo: en la figura anterior la altura de S2 es 2 y la del árbol es 3. Profundidad.La profundidad de un nodo es la longitud del único camino de la raíz a ese nodo.Ejemplo: en la figura anterior la profundidad de S2 es 1. Niveles.Dado un árbol de altura h se definen los niveles 0...h de manera que el nivel i está compuesto por todos los nodos de profundidad i. Orden de los nodos.Los hijos de un nodo usualmente están ordenados de izquierda a derecha.Si deseamos explícitamente ignorar el orden de los dos hijos, nos referiremos a un árbol como un árbol no-ordenado. La ordenación izquierda-derecha de hermanos puede ser extendida para comparar cualesquiera dos nodos que no están relacionados por la relación ancestro-descendiente.La regla a usar es que si n1 y n2 son hermanos y n1 está a la izquierda de n2, entonces todos los descendientes de n1 están a la izquierda de todos los descendientes de n2. RECORRIDOS DE UN ÁRBOL. En una estructura lineal resulta trivial establecer un criterio de movimiento por la misma para acceder a los elementos, pero en un árbol esa tarea no resulta tan simple.No obstante, existen distintos métodos útiles en que podemos sistemáticamente recorrer todos los nodos de un árbol.Los tres recorridos más importantes se denominan preorden,inorden y postorden aunque hay otros recorridos como es el recorrido por niveles. Si consideramos el esquema general de un árbol tal como muestra la figura siguiente,los recorridos se definen como sigue: El listado en preorden es: Si el árbol tiene un único elemento, dicho elemento es el listado en preorden. Si el árbol tiene más de un elemento,es decir,una estructura como muestra la figura 2,el listado en preorden es listar el nodo raíz seguido del listado en preorden de cada uno de los subárboles hijos de izquierda a derecha. El listado en inorden es: Si el árbol tiene un único elemento,dicho elemento es el listado en inorden. Si el árbol tiene una estructura como muestra la figura 2,el listado en inorden es listar el subárbol A1 en inorden,y listar el nodo raíz seguido del listado en inorden de cada uno de los subárboles hijos de izquierda a derecha restantes. El listado en postorden es: Si el árbol tiene un único elemento,dicho elemento es el listado en postorden. Si el árbol tiene una estructura como muestra la figura 2,el listado en postorden es listar en postorden cada uno de los subárboles hijos de izquierda a derecha seguidos por el nodo raíz. El listado por niveles es: desde i=0 hasta la altura h del árbol,listar de izquierda a derecha los elementos de profundidad i.Como podemos observar,un nodo n1 aparece antes que n2 en el listado por niveles si la profundidad de n1 es menor que la profundidad de n2 usando el orden de los nodos definido anteriormente para el caso en que tengan la misma profundidad. Como ejemplo de listados veamos el resultado que se obtendría sobre el árbol A de la figura 3. Los resultados de los listados de preorden,postorden e inorden son los siguientes: Listado preorden. A=Ar=rAvAs=rvAuAwAs= rvuAwAs=rvuwAxAyAzAs= rvuwxAyAzAs=rvuwxyAzAs=rvuwxyzAs =rvuwxyzsApAq=rvuwxyzspAq=rvuwxyzspq. Listado postorden. A=Ar=AvAsr=AuAwvAsr= uAwvAsr=uAxAyAzwvAsr= uxAyAzwvAsr=uxyAzwvAsr=uxyzwvAsr= uxyzwvApAqsr=uxyzwvpAqsr=uxyzwvpqsr. Listado inorden. A=Ar=AvrAs=AuvAwrAs= uvAwrAs=uvAxwAyAzrAs=uvxw AyAzrAs=uvxwyAzrAs=uvxwyzrAs= uvxwyzrApsAq=uvxwyzrpsAq=uvxwyzrpsq. Por último,el listado por niveles de este árbol es el siguiente:r,v,s,u,w,p,q,x,y,z. Finalmente es interesante conocer que un árbol no puede,en general,recuperarse con uno solo de sus recorridos.Por ejemplo:Dada la lista en inorden:vwyxzrtupsq,los árboles de la figura 4 tienen ese mismo recorrido en inorden. 2. UNA APLICACIÓN: ARBOLES DE EXPRESIÓN. Una importante aplicación de los árboles en la informática es la representación de árboles sintácticos,es decir,árboles que contienen las derivaciones de una gramática necesarias para obtener una determinada frase de un lenguaje. Podemos etiquetar los nodos de un árbol con operandos y operadores de manera que un árbol represente una expresión.Por ejemplo. en la figura 5 se representa un árbol con la expresión aritmética (x-y)*(z/t). Para que un árbol represente una expresión,hay que tener en cuenta que: Cualquier hoja está etiquetada con uno y sólo un operando. Cualquier nodo interior n está etiquetado por un operador. En los árboles de expresión,la sucesión del preorden de etiquetas nos da lo que se conoce como la forma prefijo de una expresión, en la que el operador precede a su operando izquierdo y su operando derecho.En el ejemplo de la figura 5,el preorden de etiquetas del árbol es *-xy/zt . Análogamente,la sucesión postorden de las etiquetas de un árbol expresión nos da lo que se conoce como la representación postfijo de una expresión.Así en el ejemplo,la expresión postfijo del árbol es xy-zt/*. Finalmente,el inorden de una expresión en un árbol de expresión da la expresión infijo en sí misma,pero sin paréntesis.En el ejemplo,la sucesión inorden del árbol anterior es x-y*z/t. 3. EL TIPO DE DATO ABSTRACTO "ARBOL". La estructura de árbol puede ser tratada como un tipo de dato abstracto.A continuación presentaremos varias operaciones sobre árboles y veremos como los algoritmos de árboles pueden diseñarse en términos de estas operaciones.Al igual que con otros TDA,existe una gran variedad de operaciones que pueden llevarse a cabo sobre árboles. Como podremos observar,cuando se construye una instancia de este tipo,tiene al menos un elemento, es decir,hasta ahora no hemos hablado de la existencia de un árbol vacío .Realmente, según la definición que vimos,efectivamente el número mínimo de nodos de un árbol es 1.En las implementaciones usaremos un valor especial ARBOL_VACIO para el caso en que el árbol no contenga nodos,al igual que en listas existe el concepto de lista vacía. De igual forma es necesario expresar en algunos casos que un nodo no existe para lo cual también usaremos otro valor especial NODO_NULO.Un ejemplo de su uso puede ser cuando intentemos extraer el nodo hijo a la izquierda de un nodo hoja. A continuación mostramos el conjunto de primitivas que nosotros consideraremos: CREAR_RAIZ(u).Construye un nuevo nodo r con etiqueta u y sin hijos.Se devuelve el árbol con raíz r,es decir,un árbol con un único nodo. DESTRUIR(T).Libera los recursos que mantienen el árbol T de forma que para volver a usarlo se debe de asignar un nuevo valor con la operación de creación. PADRE(n,T).Esta función devuelve el padre del nodo n en el árbol T .Si n es la raíz ,que no tiene padre,devuelve NODO_NULO(un valor que será usado para indicar que hemos intentado salirnos del árbol).Como precondición n no es NODO_NULO (por tanto T no es vacío). . HIJO_IZQDA(n,T).Devuelve el descendente más a la izquierda en el siguiente nivel del nodo n en el árbol T, y devuelve NODO_NULO si n no tiene hijo a la izquierda.Como precondición n no es NODO_NULO. HERMANO_DRCHA(n,T).Devuelve el descendiente a la derecha del nodo n en el árbol T ,definido para ser aquel nodo m con el mismo padre que n ,es decir, padre p,de tal manera que m cae inmediatamente a la derecha de n en la ordenación de los hijos de p (Por ejemplo,véase el árbol de la figura 6). Devuelve NODO_NULO si n no tiene hermano a la derecha.Como precondición n no es NODO_NULO. ETIQUETA(n,T).Devuelve la etiqueta del nodo n en el árbol T (manejaremos árboles etiquetados,sin embargo no es obligatorio definir etiquetas para cada árbol).Como precondición n no es NODO_NULO. REETIQUETA(e,n,T).Asigna una nueva etiqueta e al nodo n en el árbol T.Como precondición n no es NODO_NULO. RAIZ(T).Devuelve el nodo que está en la raíz del árbol T o NODO_NULO si T es el árbol vacío. INSERTAR_HIJO_IZQDA(n,Ti,T).Inserta el árbol Ti como hijo a la izquierda del nodo n que pertenece al árbol T.Como precondición n no es NODO_NULO y Ti no es el árbol vacío. INSERTAR_HERMANO_DRCHA(n,Td,T).Inserta el árbol Td como hermano a la derecha del nodo n que pertenece al árbol T.Como precondición n no es NODO_NULO y Td no es el árbol vacío. PODAR_HIJO_IZQDA(n,T).Devuelve el subárbol con raíz hijo a la izquierda de n del árbol T el cual se ve privado de estos nodos.Como precondición n no es NODO_NULO. PODAR_HERMANO_DRCHA(n,T).Devuelve el subárbol con raíz hermano a la derecha de n del árbol T el cual se ve privado de estos nodos.Como precondición n no es NODO_NULO. A continuación veremos cómo implementar el TDA árbol y posteriormente implementaremos los algoritmos de recorrido:PREORDEN,POSTORDEN,INORDEN. IMPLEMENTACIÓN DE ÁRBOLES. UNA IMPLEMENTACIÓN MATRICIAL Sea A un árbol en el cual los nodos se etiquetan 0,1,2,...,n-1,es decir,cada nodo contiene un campo de información que contendrá estos valores.La representación más simple de A que soporta la operación PADRE es una matriz lineal P en la cual el valor de P[i] es un valor o un cursor al padre del nodo i.La raíz de A puede distinguirse dándole un valor nulo o un valor a él mismo como padre.Por ejemplo.,podemos usar un esquema de cursores donde P[i]=j si el nodo j es el padre del nodo i,y P[i]=-1 (suponemos que NODO_NULO=-1) si el nodo i es la raíz.La definición del tipo sería: #define MAXNODOS 100 /*Por ejemplo*/ #define NODO_NULO -1 typedef int nodo; /*Indica una casilla de la matriz*/ typedef int *ARBOL; Esta representación usa la propiedad de los árboles de que cada nodo tiene un único padre.Con esta representación el padre de un nodo puede encontrarse en tiempo constante.Un camino hacia arriba en el árbol puede seguirse atravesando el árbol en tiempo proporcional al número de nodos en el camino.Podemos soportar también el operador ETIQUETA añadiendo otra matriz L ,tal que L[i] es la etiqueta del nodo i ,o haciendo que los elementos de la matriz A sean registros consistiendo en un entero(cursor)y una etiqueta.EJEMPLO:Véase el árbol de la figura 7: La representación de padre por cursores no facilita las operaciones que requieren información de hijos.Dado un nodo n ,es costoso determinar los hijos de n o la altura de n.Además,la representación por cursores del padre no especifica el orden de los hijos de un nodo.Por tanto,operaciones como HIJO_IZQDA y HERMANO_DRCHA no están bien definidas.Podríamos imponer un orden artificial,por ejemplo,numerando los hijos de cada nodo después de numerar el padre,y numerar los hijos en orden creciente de izquierda a derecha. Nota:Téngase en cuenta que aunque esta implementación no parece muy adecuada, es posible ampliarla con la utilización de nuevos campos de cursores.Por ejemplo:Podemos añadir dos matrices adicionales para almacenar para cada nodo tanto el hijo a la izquierda como el hermano a la derecha.