Estructuras de datos

5 (ii). Árboles

5.7 Representación de árboles generales como árboles binarios

   Vamos a ver en este apartado que cualquier árbol se puede representar como un árbol binario. Esto es importante porque resulta más complejo manipular nodos de grado variable (número variable de relaciones) que nodos de grado fijo. Una posibilidad evidente de fijar un límite en el número de relaciones sería seleccionar un número k de hijos para cada nodo, donde k es el grado máximo para un nodo del árbol. Sin embargo, esta solución desaprovecha mucho espacio de memoria.

• Lema 4:para un árbol k-ario (es decir, de grado k) con n nodos, cada uno de tamaño fijo, el número de enlaces nulos en el árbol es (n * (k-1) + 1) de los (n*k) campos de tipo enlace existentes.

   Esto implica que para un árbol de grado 3, más de 2/3 de los enlaces serán nulos. Y la proporción de enlaces nulos se aproxima a 1 a medida que el grado del árbol aumenta. La importancia de poder utilizar árboles binarios para representar árboles generales reside en el hecho de que sólo la mitad de los enlaces son nulos, además de facilitar su manipulación.

   Para representar cualquier árbol por un árbol binario, vamos a hacer uso implícito de que el orden de los hijos de un nodo en un árbol general no es importante.

   La razón por la cual, para representar un árbol general, se necesitarían nodos con muchos enlaces es que, hemos pensado en una representación basada en la relación padre-hijo dentro del árbol, y un nodo puede tener un gran número de hijos. Sin embargo, se puede encontrar una forma de representación donde cada nodo sólo necesite tener dos relaciones, una que lo una con el hijo que tenga más a la izquierda y otra que lo una con el siguiente nodo hermano por la derecha. Estrictamente hablando, como el orden de los hijos en un árbol no es importante, cualquiera de los hijos de un nodo podría ser el hijo que está más a la izquierda, el nodo padre y cualquiera de los nodos hermanos podría ser el siguiente hermano por la derecha. Por lo tanto, la elección de estos nodos no dejará de ser, hasta cierto punto, arbitraria. Podemos basarnos para esta elección en la representación gráfica del árbol que se desea almacenar. Veamos el siguiente ejemplo, el árbol binario correspondiente al árbol de la figura se obtiene conectando juntos todos los hermanos de un nodo y eliminando los enlaces de un nodo con sus hijos, excepto el enlace con el hijo que tiene más a la izquierda.

   Este tipo de representación se puede identificar con los árboles binarios que ya hemos visto, asociando el enlace izquierdo del árbol con el enlace al hijo de la izquierda y el enlace derecho con el enlace al nodo hermano. Se observa que de esta manera el nodo raíz nunca tendrá un subárbol derecho, ya que no tiene ningún hermano. Pero esto nos permite representar un bosque de árboles generales como un único árbol binario, obteniendo primero la transformación binaria de cada árbol y después uniendo todos los árboles binarios considerando que todos los nodos raíz son hermanos. Ver el ejemplo de la figura:

   En todas estas representaciones de árbol general a árbol binario hay que tener en cuenta la interpretación que se deben hacer de las relaciones, no es lo mismo que un nodo esté a la izquierda o a la derecha de otro, ya que los enlaces izquierdos unen un nodo con su hijo mientras que los enlaces derechos unen dos nodos hermanos. De cualquier forma, teniendo en cuenta este aspecto, es posible aplicar los algoritmos de manipulación de árboles binarios que se han visto hasta ahora. De hecho, en todos estos algoritmos se diferenciaba claramente entre el tratamiento del subárbol izquierdo y el del subárbol derecho.

5.8 Árboles binarios de búsqueda

   Los árboles binarios de búsqueda son estructuras de datos que presentan un gran rendimiento cuando las funciones a realizar implican búsquedas, inserciones y eliminación de nodos. De hecho, con un árbol de búsqueda, dichas operaciones se pueden realizar tanto a partir de un valor clave, como por un valor ordinal (es decir, encontrar un elemento con clave x, encontrar el sexto elemento más pequeño, borrar el elemento con clave x, borrar el sexto elemento más pequeño, insertar un elemento y determinar su ordinal dentro del árbol).

• (1) Todos los nodos están identificados por una clave y no existen dos elementos con la misma clave.
• (2) Las claves de los nodos del subárbol izquierdo son menores que la clave del nodo raíz.
• (3) Las claves de los nodos del subárbol derecho son mayores que la clave del nodo raíz.
• (4) Los subárboles izquierdo y derecho son también árboles binarios de búsqueda.

   La primera propiedad resultaría redundante, ya que de las propiedades (2), (3) y (4) se puede deducir que la clave de un nodo es única. Sin embargo, la aparición explícita de esta propiedad hace que la definición sea más clara.

   Ejemplos de árboles binarios de búsqueda:

   Veamos ahora cómo manipular este tipo especial de árboles binarios. Estudiaremos las operaciones de búsqueda, inserción y borrado.

Búsqueda

   La definición de árbol binario de búsqueda especifica un criterio en la estructuración del árbol en función de las claves de los nodos. En este caso, existe un criterio de ordenación de los nodos. Por lo tanto, será bastante simple describir un método eficiente de búsqueda que explote esta ordenación.

   Suponer que se busca un elemento que posea la clave x. La búsqueda comenzará por el nodo raíz del árbol. La clave de ese nodo informará por dónde debe continuar la búsqueda, ya no es necesario recorrer exhaustivamente todos los nodos del árbol. Si la clave del nodo es igual a x, la búsqueda finaliza con éxito. Si la clave es menor que x, se sabe que si existe un nodo en el árbol que posea como clave el valor x deberá estar en el subárbol derecho, por lo tanto la búsqueda deberá continuar por esa parte del árbol. Si, por el contrario, la clave del nodo es mayor que x, entonces la búsqueda deberá continuar por el subárbol izquierdo. El proceso continuará hasta que se encuentre un nodo con clave igual a x o un subárbol vacío, en cuyo caso se puede asegurar que no existe ningún nodo con clave x en el árbol. Este método de búsqueda sugiere seguir un esquema recursivo.

   Suponiendo que la clave que identifica cada nodo es un campo contenido en la información general del nodo, el algoritmo de búsqueda quedaría como sigue:

Algoritmo Buscar (recursivo)

  Entradas

   p: arbol 
   x: Valor (valor a buscar)

  Variable

   aux: ABB (arbol binario de busqueda)

  Inicio

   si (p = NULO) entonces devolver(NULO)
   sino
       si (x = p^.info.clave) entonces devolver(p)
       sino 
           si (x < p^.info.clave) entonces devolver(Buscar(x, p^.Izq))
           sino 
               devolver(Buscar(x, p^.Der))
       fin_sino
   fin_sino

  Fin 

   En este ejemplo, la recursividad puede ser fácilmente sustituida por un esquema iterativo mediante la utilización de un bucle de repetición "mientras". En ese caso, el algoritmo de búsqueda iterativo sería:

Algoritmo Buscar (iterativo)

  Entradas

   p: arbol 
   x: Valor (valor a buscar)

  Variables

   aux: arbol
   enc: (cierto, falso)

  Inicio

   aux <-- p
   enc <-- FALSO
   
   mientras (aux <> NULO) Y (enc = FALSO) hacer    
       si (aux^.info = x) entonces
           enc <-- CIERTO
       sino    
           si (x < aux^.info) entonces aux <-- aux^.Izq       
           sino
               aux <-- aux^.Der
       fin_sino
  
       Buscar <-- enc
  
   fin_mientras

  Fin 

   El proceso de búsqueda en un árbol binario de búsqueda resulta muy eficaz. El coste asociado sería del orden de O(h), donde h es la altura del árbol. Hay que hacer notar que la dependencia es lineal con la áltura del árbol y no con el número de elementos del mismo. En función del número de nodos del árbol, n, el coste sería logarítmico (O(log n)).

   El método de búsqueda se asemeja mucho al método de búsqueda binaria sobre arrays ordenados, tras la comparación con un elemento se puede decidir en qué región de la estructura se puede encontrar la información buscada, descartándose el resto de los elementos de la estructura. De esta forma, se reduce considerablemente el número de comparaciones necesarias para localizar el elemento.

Inserción

   La inserción de un nuevo nodo en un árbol binario de búsqueda debe realizarse de tal forma que se mantengan las propiedades del árbol. De modo que lo primero que hay que hacer es comprobar que en el árbol no existe ningún nodo con clave igual a la del elemento que se desea insertar. Si la búsqueda de dicha clave falla, entonces se insertará el nuevo nodo en el punto donde se ha parado la búsqueda, que será el punto del árbol donde, de existir, debería estar ubicada dicha clave. Hay que considerar que todo proceso de búsqueda fallido termina en un enlace nulo, por tanto, el nodo a insertar siempre será un nodo terminal, lo que facilitará la operación.

El algoritmo que implementa la estrategia de inserción es el siguiente:

Algoritmo Insertar

  Entradas

   arb: arbol  (por referencia)
   x: Valor 

  Salida

   (cierto, falso) 

  Variables

   p, q: arbol
   enc: (cierto, falso)

  Inicio

   (buscar la clave en el arbol, p indica su localización)
   (si p = NULO entonces no está, q es el padre de p)
   
   q <-- NULO   
   p <-- arb    
   enc <-- FALSO        
   mientras (p <> NULO) Y (enc = FALSO) hacer        
       q <-- p               
       si (x.clave = p^.info.clave) entonces enc <-- CIERTO    
       sino        
           si (x.clave < p^.info.clave) entonces p <-- p^.Izq 
  	   sino p <-- p^.Der
       fin_sino
   fin_mientras
  
   (insertamos)
  
   si (enc = FALSO) entonces
       crear_espacio(p)
       p^.Izq <-- NULO
       p^.Der <-- NULO
       p^.info <-- x
       si (q = NULO) entonces arb <-- p   (insertar la raíz)
       sino
           si (x.clave < q^.info.clave) entonces q^.Izq <-- p
  	   sino q^.Der <-- p  	
       fin_sino
       devolver(cierto)
   sino devolver(falso)

  Fin 

Borrado

   La operación de borrado en un árbol de búsqueda es muy simple. Hay que tener en cuenta que en todo árbol de búsqueda los nodos se pueden ordenar por su clave si se recorre el árbol siguiendo el criterio infijo. El orden establecido por este recorrido se debe mantener aunque se elimine un nodo del árbol. Por tanto, no hay más que utilizar el algoritmo de borrado sobre árboles binarios cuando se desea mantener el orden infijo de los nodos. Este algoritmo ha sido visto con anterioridad en este capítulo y no es necesario repetirlo en este apartado.

5.9 Montículos binarios (heaps)

   Veamos otro tipo especial de árbol binario, los llamados heaps (montículos), que se pueden representar eficazmente con un vector.

   De la definición se deduce que la clave contenida en el nodo raíz de un montículo de máximos es la mayor clave del árbol, pero esto no quiere decir que sea la única con ese valor. Análogamente sucede con los montículos de mínimos y la menor clave del árbol.

   La estructura del montículo tiene interesantes aplicaciones, por ejemplo, la ordenación de arrays (algoritmo heapsort) o el mantenimiento de las llamadas colas de prioridad. Las colas de prioridad son un tipo especial de colas donde todo elemento que se inserta en la cola lleva asociado una prioridad, de forma que el elemento que se borra de la cola es el primero entre los que tengan la máxima prioridad (en montículos de máximos).

   Los montículos, como árboles binarios completos que son, se pueden representar de forma eficaz mediante una estructura secuencial (un array). A cada nodo del árbol se le asigna una posición dentro de la secuencia en función del nivel del árbol en el que se encuentra y dentro de ese nivel de la posición ocupada de izquierda a derecha.

   De forma que para representado por el elemento A[i] se cumplen las propiedades que vimos al principio del tema para árboles completos, es decir, el nodo padre estará localizado en A[i div 2], si i>1, y los hijos estaran localizados en A[2i] y A[2i+1].

   Una característica fundamental de esta estructura de datos es que la propiedad que caracteriza a un montículo puede ser restaurada eficazmente tras cualquier modificación de un nodo (cambio de su valor, inserción, borrado, etc).

   Supongamos que se trata de un montículo de máximos (cualquier comentario sobre este tipo de montículos se puede extender fácilmente a los montículos de mínimos). En este caso, se debe cumplir que la clave de cualquier nodo sea mayor o igual que las claves de sus hijos.

   Si se modifica el valor de un nodo incrementando su valor, entonces es posible que la propiedad del montículo no se cumpla con respecto a sus nodos antecesores, no respecto a sus hijos. Esto implicaría ir ascendiendo por el árbol comprobando si el nodo modificado es mayor que el padre, si es así intercambiarlos y repetir el proceso en un nivel superior hasta que se encuentre que no es necesario realizar ningún intercambio o que se llegue al nodo raíz. En cualquier caso, tras ese proceso se habrá restaurado la propiedad del montículo. Si por el contrario, modificamos un nodo disminuyendo su valor, el problema consistirá en comprobar la propiedad respecto a sus descendientes. Si la clave del nodo es mayor que las claves de sus hijos, entonces la propiedad se sigue cumpliendo, si no es así, hay que intercambiar la clave de este nodo con la del hijo que tenga la clave máxima y repetir todo el proceso desde el principio con este nodo hijo hasta que no se realice el intercambio. Estas dos posibilidades de restauración del montículo se pueden expresar en forma de los dos siguientes algoritmos:

Algoritmo Subir

  Entradas

   p: arbol[1..n] 
   i: indice

  Inicio

   si (i > 1) Y (A[i] > A[i div 2]) entonces 
       intercambiar(A[i], A[i div 2])        
       Subir(A, i div 2)        
   fin_si

  Fin 

Algoritmo Bajar

  Entradas

   p: arbol[1..n] 
   i: indice

  Variable

   max: indice

  Inicio

   max <-- i
   si (2i <= n) Y (A[2i] > A[max]) entonces 
       max <-- (2i)    
   si (2i + 1 <= n) Y (A[2i + 1] > A[max]) entonces     
       max <-- (2i + 1)
  
   si (max <> i) entonces
       intercambiar(A[i], A[max])
       Bajar(A, max)
   fin_si

  Fin 

   A partir de estos dos algoritmos básicos que permiten restaurar la propiedad del montículo, se pueden definir las operaciones de inserción y borrado de elementos en esta estructura de datos.

Inserción

   Al intentar añadir un nuevo elemento al montículo, no se sabe cuál será la posición que ocupará el nuevo elemento de la estructura, pero lo que si se sabe es que, por tratarse de un árbol completo, dónde se debe enlazar el nuevo nodo, siempre será en la última posición de la estructura. Por ejemplo, en el siguiente montículo formado por cinco elementos, si se intenta añadir un nuevo elemento, sea el que sea, se conoce cuál será la estructura final del árbol:

   Si se almacena en el nuevo nodo la información que se desea insertar, lo más probable será que la propiedad del montículo no se conserve. Como el nuevo nodo siempre es terminal, para mantener la propiedad del montículo bastará con aplicar el algoritmo Subir a partir del nodo insertado. Con esto, el algoritmo de inserción resulta verdaderamente simple:

Algoritmo Insertar

  Entradas

   A: arbol[1..n] 
   x: Valor

  Inicio

   si (A.num < MAX_NODOS) entonces
       A.num <-- A.num + 1
       A[n] <-- x  
       Subir(A, n)      
   fin_si 

  Fin 

Borrado

   Al igual que en la operación de inserción, hay que tener en cuenta que el montículo es un árbol completo y que, para que se mantenga esa propiedad, el nodo que debe desaparecer realmente es el último. Por lo tanto, la estrategia a seguir para borrar cualquier nodo del montículo podría ser: sustituir la información del nodo a borrar por la del último nodo del montículo y considerar que el árbol tiene un nodo menos; como esta modificación seguramente habrá alterado la propiedad del montículo, entonces aplicar el algoritmo Subir o Bajar, lo que sea preciso, para restaurar esa propiedad. La aplicación de cualquiera de los algoritmos dependerá de que la modificación de la información del nodo haya implicado un incremento o disminución de la clave.

Algoritmo Borrar

  Entradas

   p: arbol[1..n] 
   i: indice

  Variable

   x: Valor

  Inicio

   x <-- A[i]
   A[i] <-- A[n]    
   n <-- n - 1      
   si (A[i] <> x) entonces 
       si (A[i] > x) entonces Bajar(A, i)
       sino Subir(A, i)
   fin_si

  Fin 

Aplicación de los montículos

   Los montículos tienen como aplicación fundamental el mantenimiento de las llamadas colas de prioridad. Esta estructura de datos es un tipo especial de cola, donde cada elemento lleva asociado un valor de prioridad, de forma que cuando se borra un elemento de la estructura éste será el primero de los elementos con la mayor prioridad. En cualquier instante se puede insertar un elemento con prioridad arbitraria. Si la utilización de la cola de prioridad requiere borrar el elemento con la mayor prioridad, entonces se utiliza para su representación un montículo de máximos, donde resulta inmediata la localización de ese elemento. De forma análoga se haría si necesitamos borrar el elemento con la menor prioridad, utilizariamos un montículo de mínimos.

   En un montículo de máximos resulta inmediato obtener el valor máximo de las claves del árbol. Como se ha visto anteriormente, este valor está siempre situado en la raíz del árbol, por lo tanto bastaría con acceder al primer elemento del array A[1].

Algoritmo EliminarMaximo

  Entradas

   p: arbol[1..n] 

  Inicio

   si (p.num = 0) entonces "Error: arbol vacío."
   A[i] <-- A[n]    
   n <-- n - 1      
   si (A[i] <> x) entonces 
       si (A[i] > x) entonces Bajar(A, i)
       sino Subir(A, i)
   fin_si

  Fin 

   Desde el punto de vista de programación del proceso, se podría utilizar una representación de la lista de espera en función de un montículo de máximos, siendo la información asociada con los nodos del árbol los datos de cada enfermo y la clave de identificación la prioridad de los mismos. Cuando un enfermo ingresa para ser operado en el hospital, se le asigna una prioridad y se insertan sus datos como un nuevo nodo del montículo (operación insertar), cuando el quirófano queda libre, se ocupará con el enfermo cuyos datos estén situados en la raíz del montículo (máxima prioridad) y se reestructurará el mismo.

5.10 Ordenación con árboles

   En los últimos tipos de árboles binarios comentados, se ha visto como se puede organizar eficientemente la información en estas estructuras en base a una clave de información, de manera que sea fácil extraer información relacionada con esa clave (buscar por clave, acceder a la clave máxima, acceder a la clave mínima, etc..). Esto hace que parezca evidente la utilización de estas estructuras de datos para resolver un problema tan habitual como pueda ser el problema de la ordenación de información.

   Si nos centramos en el problema de la ordenación interna sobre arrays, que fue el problema estudiado en su momento, se puede pensar en los montículos como el tipo de árboles que podrían resolver el problema. Hay que tener en cuenta que, normalmente, la representación de los montículos se hace precisamente con arrays y que en estas estructuras es muy fácil acceder al elemento con clave máxima (o mínima, según sea la organización del montículo), con lo que se podría establecer algún tipo de algoritmo que aprovechando esta propiedad ordene la información del array.

   Si consideramos que inicialmente el array puede estar arbitrariamente ordenado, esto implicará que, en general, no se cumplirá la propiedad del montículo de máximos, por lo que habría que empezar por formar un montículo a partir de ese array. Una vez formado el montículo, es fácil saber qué elemento debe ocupar la última posición del array ordenado, ese elemento siempre será el que ocupa la raíz del array (el primero). Si se intercambia el primer elemento con el último, se habrá logrado ubicar correctamente el elemento máximo. Se puede ahora considerar que el array tiene un elemento menos (el que está bien colocado) y reorganizar el montículo con un elemento menos. Si se repite este proceso hasta que se tenga un montículo con un único elemento, se puede asegurar que el array estará finalmente ordenado. Este método de ordenacion se conoce como Heapsort y el algoritmo sería el siguiente:

Algoritmo Heapsort

  Entradas

   v: vector[1..n] 

  Variable

  num_el: entero

  Inicio

   HacerMonticulo(v)
   num_el <-- v.num   
       
   mientras (v.num > 1) hacer 
       v.info[1] <--> v.info[v.num]    
       v.num <-- v.num - 1
       Bajar(v, 1)
   fin_mientras 
  
   v.num = num_el

  Fin 

   Haría falta especificar cómo se puede construir un montículo de máximos a partir de un array arbitrariamente ordenado:

Algoritmo HacerMonticulo

  Entradas

   v: vector[1..n] 

  Variable

  num_el: entero

  Inicio

   num_el <-- v.num
   
   desde (v.num <-- 2) hasta num_el hacer 
       Subir(v, v.num) 

  Fin 

   En cuanto al coste del algoritmo de ordenación hay que tener en cuenta el coste de cada una de las dos partes del algoritmo, HacerMonticulo y la reorganización de (n-1) montículos mediante el algoritmo Bajar. La formación del montículo tiene un coste lineal con el tamaño del array, O(n), mientras que el coste del bucle que reorganiza los montículos de tamaño decreciente es O(n * log n). Asintóticamente, la función logarítmica domina a la lineal y el coste final del algoritmo de ordenación será O(n * log n). Por lo tanto, resulta que el método de ordenación Heapsort es más eficiente que los métodos directos vistos en el tema dedicado a vectores.