Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


 Prev.

1.8  Estructura de la información (III)

§4.4  Árboles

Los árboles son estructuras parecidas a las listas enlazadas ( 1.8), en el sentido que tienen punteros que señalan a otros elementos, pero no tienen una estructura lógica de tipo "lineal" o secuencial como aquellas, sino ramificada. Tienen aspecto de árbol, de ahí su nombre (ver figura ).  Su estudio desde el punto de vista matemático pertenece a la teoría de grafos;  desde el punto de vista informático son estructuras de datos, lo que significa que cada elemento, denominado nodo u hoja, contiene uno o más valores. Su estudio corresponde a la teoría de bases de datos, y en esta terminología, los nodos que "cuelgan" de otros, se denominan hijos ("child nodes"). Cada hoja puede tener un máximo de hijos; es lo que se denomina grado máximo del árbol ("maximun degree"). Si no tiene ninguno, se dice que es un nodo terminal.

Son especialmente interesantes y útiles los árboles ordenados (denominados B-trees).  Esto significa que para su construcción, los nodos que se van agregando no se colocan al azar, colgando de cualquier nodo existente, sino según un criterio que tiene en consideración el "valor" de la hoja. Este tipo de estructura se usa extensivamente en las bases de datos [3] y en los sistemas de ficheros [1].  En los b-trees se distinguen varios parámetros que son determinantes en cuanto a su idoneidad como estructuras de datos.  El primero es el máximo número de hijos (y datos) que puede tener cada hoja; es lo que se denomina grado máximo del árbol ("maximun degree").  El número de hijos de una hoja o nodo, puede variar desde ninguno (nodos terminales) al máximun degree.  Otro parámetro importante es el número mínimo de datos que puede contener un nodo, grado mínimo ("minimun degree"). Este valor es utilizado en los procesos de inserción de nuevos datos, y determina la forma en que se desdoblan los nodos existentes para acomodar los nuevos valores (el conjunto debe permanecer ordenado).

Generalmente cada hoja de un árbol es en sí misma una estructura de datos (en el sentido C++ del término 4.5).  Uno o varios los campos de esta estructura se utilizan para la ordenación (campos-índice), y desde luego se exige que exista un criterio de ordenación para los valores de estos campos. Es decir: que se establezca una regla por la que se pueda determinar de forma inequívoca si dos valores son iguales, o desiguales, y en este último caso cual precede en el orden (este orden suele ser numérico o alfabético [2]).

§4.4.1  Árboles binarios

Existen varios tipos de árboles, pero con mucho, los más utilizados son los denominados árboles binarios. Son un caso particular de los B-trees en los que cada nodo puede contener dos datos y tener dos hijos como máximo.  Comparten la característica de las listas doblemente enlazadas de que cada elemento tiene dos punteros que señalan a otros dos elementos como máximo (aunque puede no utilizar ninguno o solo uno); comparten también la facilidad de inserción de elementos en cualquier posición, y que la información puede mantenerse ordenada, pero aventajan a las listas en que la ordenación es más fácil, ya que existen algoritmos muy rápidos para encontrar la posición de un dato y no es necesario modificar los punteros existentes para insertar un nuevo dato, aunque su eliminación puede resultar más problemática.

Aunque el caso teóricamente más desfavorable también supone tener que recorrer la totalidad del árbol, para datos aleatorios el número de pasos necesario tiende a Log2 n, siendo n el número de elementos del árbol. Como se verá a continuación, las listas simplemente enlazadas pueden considerarse casos extremos de árboles binarios (árboles degenerados).

Generalmente, el número de pasos necesario para encontrar un dato en una estructura se expresa mediante la denominada expresión O mayúscula ("Big O notation" en la literatura inglesa).  Una expresión como O(n) significa que el número de pasos es una expresión lineal del número n de elementos de la estructura, mientras que O(log(n)) representa que el número de pasos es proporcional al logaritmo de n.  Por ejemplo, en una estructura de 1M de nodos, la búsqueda en una pila o cola puede suponer un millón de pasos, mientras que en un árbol pueden ser solo 6 (logaritmo de 1.000.000).

Tenga en cuenta que en la práctica, los árboles utilizados no suelen ser binarios, sino que su grado máximo es mayor que 2.  En estos casos, la Big O notations indica el número de pasos hasta alcanzar el primer encuentro aproximado. A partir de ahí suele ser necesaria una búsqueda secuencial sobre un pequeño número de nodos hasta encontrar el elemento buscado.

Figura 7
En la figura 7 se muestra un árbol binario de 6 elementos y la nomenclatura utilizada. Como puede verse, además de los datos, cada elemento tiene dos enlaces: derecho Ed, e izquierdo Ei, que pueden estar o no ocupados. Los nodos terminales son los que tienen a cero sus dos enlaces (no ocupados).


Por lo general los nodos suelen ser estructuras que además de otros miembros conteniendo información útil, tiene dos punteros a estructuras, que son utilizados como enlaces a los otros nodos. Por ejemplo, el diseño C++ de un nodo puede ser el siguiente:

struct Nodo {

  tipoX contenido-de-nodo;

  Nodo* enlace-izquierdo;

  Nodo* enlace-derecho;

};

En el manejo de árboles es muy común el empleo de funciones recursivas; en el capítulo 4 se muestran algunos ejemplos concretos ( 4.5.8 Estructuras auto-referenciadas).

§4.4.2  Proceso de creación

Hemos dicho que los árboles son estructuras de datos, generalmente ordenadas; aunque pueden no estarlo, la mayoría de sus aplicaciones requieren que lo estén. Al igual que en las listas, el criterio de ordenación puede ser cualquiera. Sin embargo, es importante señalar que la disposición final de los nodos depende del orden de creación. Una vez establecido el criterio de ordenación que se utilizará, el proceso de construcción es el siguiente:  El primer elemento se coloca como nodo raíz; a continuación se añade el segundo elemento, que colgará del puntero derecho Ed (rama derecha) si es mayor que el raíz, y del izquierdo Ei en caso contrario (igual o menor). A continuación se añade el tercero, que se colocará en la rama izquierda si es mayor que el raíz y en la derecha si menor o igual. El proceso sigue indefinidamente hasta que se han colocado todos los elementos del árbol.


En la figura 8 se muestra el aspecto de un árbol de 6 elementos, suponiendo un orden de colocación numérico. Se han colocado elementos con valores  6, 8, 9, 10, 12 y 14 en el orden de creación siguiente: 10, 8, 9, 12, 6, 14.

Si el orden de inserción hubiese sido ligeramente distinto, por ejemplo: 8, 9, 12, 6, 14, 10, el aspecto sería el de la figura 9.


A su vez, en la figura 10 se muestra el aspecto con un tercer orden de creación, cambiando solo el orden del segundo y tercer elementos del caso anterior:  8, 12, 9, 6, 14, 10


En la figura 11 se muestra un caso extremo; el aspecto del árbol con un orden de creación 6, 8, 9, 10, 12 y 14, es decir: cuando los elementos han sido previamente ordenados.


Como puede observarse, con independencia de cual sea el orden de creación, ocurre que en cualquier nodo del árbol binario ordenado, los elementos de la rama inferior derecha (caso de existir) son mayores que el elemento del nodo, y los de la rama inferior izquierda son menores o iguales (suponiendo también su existencia).

§4.4.3  Equilibrio

Como se ha indicado, la forma de un árbol binario ordenado depende exclusivamente del orden de introducción de los datos. Cuando el árbol adopta la forma aproximada de la figura 8 se dice que está equilibrado; por el contrario, el de la figura 9 está desequilibrado.  A su vez, el caso representado en la figura 11 ha degenerado en una lista simplemente enlazada. Habrá observado que el árbol más desequilibrado (degenerado) se obtiene precisamente cuando se suministran los datos ordenados, y que los mejores resultados, en cuanto al equilibrio, se obtienen con un orden aleatorio.

En realidad la cuestión del equilibrio no es de tipo estético sino práctico. El número de saltos para para encontrar un dato en un árbol binario depende de su altura (número de niveles), que es menor cuanto más equilibrado esté. Como se ha señalado, en un árbol de n nodos este número tiende a Log2 n cuando está perfectamente equilibrado, y a n/2 en caso de que haya degenerado en una lista simplemente enlazada. Cuando se trata de árboles de cientos o miles de nodos en los que se repiten cientos o miles de accesos, las diferencias globales pueden ser muy significativas. Por ejemplo, para encontrar un dato en un árbol de 1.024 elementos los valores teóricos medios oscilan entre 10 pasos si está equilibrado y 512 si degenera en una lista. Puede concluirse por tanto, que un árbol equilibrado es una buena estructura de datos desde la óptica de los mecanismos de acceso a la información.

§4.4.4  Recorrido de un árbol binario


Suponiendo un árbol binario ordenado, como el de la figura 12, existen tres formas estándar de recorrer la totalidad de sus nodos: inorden, preorden y postorden.  La diferencia está en el criterio seguido en uno y otro caso para recorrer las ramas. El primero es el que produciría una salida ordenada de los valores de sus nodos.


La secuencia de los recorridos en los tres casos serían:

Inorden:       A D E b e g k

Preorden:    b D A E g e k

Postorden:   A E D e k g b


En el epígrafe dedicado a las Estructuras auto referenciadas se muestran ejemplos de los algoritmos recursivos utilizados en uno y otro caso ( 4.5.8).

  Inicio.


[1]  Denominados "File Systems";  estructuras de datos utilizadas para almacenar información en los soportes de memoria externa -discos- ( H1.8.2a) .

[2]  Generalmente los campos fecha se disponen de tal modo que su ordenación queda reducida a una comparación numérica. Por ejemplo:  yyyymmdd

[3]  Descripción detallada de la estructura en disco de una base de datos (un caso real) que utiliza una estructura B-tree   www.sqlite.org

 Prev.