6.2. Ejemplos de árboles¶
Ahora que hemos estudiado estructuras de datos lineales como pilas y colas y que tenemos cierta experiencia con la recursividad, examinaremos una estructura de datos común llamada árbol. Los árboles se usan en muchas áreas de las ciencias de la computación, incluyendo sistemas operativos, gráficos, sistemas de bases de datos y redes de computadoras. Las estructuras de datos tipo árbol tienen muchas cosas en común con sus primos botánicos. Una estructura de datos tipo árbol tiene una raíz, ramas y hojas. La diferencia entre un árbol de la naturaleza y un árbol de las ciencias de la computación es que una estructura de datos tipo árbol tiene su raíz en la parte superior y sus hojas en la parte inferior.
Antes de comenzar nuestro estudio de las estructuras de datos tipo árbol, veamos algunos ejemplos comunes. Nuestro primer ejemplo de un árbol es un árbol de clasificación de la biología. La Figura 1 muestra un ejemplo de la clasificación biológica de algunos animales. A partir de este sencillo ejemplo, podemos aprender sobre varias propiedades de los árboles. La primera propiedad que este ejemplo demuestra es que los árboles son jerárquicos. Por jerárquico, queremos decir que los árboles están estructurados en capas con las cosas más generales cerca de la parte superior y las cosas más específicas cerca de la parte inferior. La parte superior de la jerarquía es el Reino, la siguiente capa del árbol (los “hijos” de la capa superior) es el Filo, luego está la Clase, y así sucesivamente. Sin embargo, no importa cuán profundo vayamos en el árbol de clasificación, todos los organismos siguen siendo animales.
Figura 1: Taxonomía de algunos animales comunes mostrada como un árbol¶
Figura 1: Taxonomía de algunos animales comunes mostrada como un árbol
Note que usted puede comenzar en la parte superior del árbol y seguir una ruta formada por círculos y flechas hasta llegar a la parte inferior. En cada nivel del árbol podríamos hacernos una pregunta y luego seguir la ruta que coincida con nuestra respuesta. Por ejemplo, podríamos preguntar: “¿Es este animal un cordado o es un artrópodo?” Si la respuesta es “cordado” entonces seguimos esa ruta y preguntamos, “¿Es este cordado un mamífero?” Si no, estamos atrapados (pero únicamente en este ejemplo simplificado). Cuando estamos en el nivel de los Mamíferos preguntamos, “¿Es este Mamífero un Primate o es un Carnívoro?” Podemos seguir las rutas hasta llegar al fondo del árbol donde tenemos el nombre común de las especies.
Una segunda propiedad de los árboles es que todos los hijos de un nodo son independientes de los hijos de otro nodo. Por ejemplo, el género Felis tiene los hijos Domestica y Leo. El género Musca también tiene un hijo llamado Domestica, pero es un nodo diferente y es independiente del hijo Domestica de Felis. Esto significa que podemos cambiar el nodo que es hijo de Musca sin afectar al hijo de Felis.
Una tercera propiedad es que cada nodo hoja es único. Podemos especificar una ruta desde la raíz del árbol hasta una hoja que identifique de manera única a cada especie en el reino animal; Por ejemplo, Animalia \(\rightarrow\) Cordados \(\rightarrow\) Mamíferos \(\rightarrow\) Carnívoros \(\rightarrow\) Félidos \(\rightarrow\) Felis \(\rightarrow\) Domestica.
Otro ejemplo de una estructura de árbol que probablemente usted utilice todos los días es un sistema de archivos. En un sistema de archivos, los directorios o carpetas se estructuran como un árbol. La Figura 2 ilustra una pequeña parte de una jerarquía de un sistema de archivos en Unix.
Figura 2: Una pequeña parte de una jerarquía de un sistema de archivos en Unix¶
Figura 2: Una pequeña parte de una jerarquía de un sistema de archivos en Unix
El árbol del sistema de archivos tiene mucho en común con el árbol de clasificación biológica. Usted puede seguir una ruta desde la raíz a cualquier directorio. Esa ruta identificará de forma única a ese subdirectorio (y a todos los archivos del mismo). Otra propiedad importante de los árboles, derivada de su naturaleza jerárquica, es que usted puede mover secciones enteras de un árbol (llamada subárbol) a una posición diferente en el árbol sin afectar los niveles inferiores de la jerarquía. Por ejemplo, podríamos tomar el subárbol completo que comienza con /etc/, separar etc/ de la raíz y volver a conectarlo debajo de usr/. Esto cambiaría la ruta de acceso única a httpd de /etc/httpd a /usr/etc/httpd, pero no afectaría el contenido ni a los hijos del directorio httpd.
Un ejemplo final de un árbol es una página web. El siguiente es un ejemplo de una página web sencilla escrita usando HTML. La Figura 3 muestra el árbol que corresponde a cada una de las etiquetas HTML utilizadas para crear la página.
<html xmlns="http://www.w3.org/1999/xhtml"
xml:lang="es" lang="es">
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=utf-8" />
<title>Sencilla</title>
</head>
<body>
<h1>Una página web sencilla</h1>
<ul>
<li>Primer ítem de la lista</li>
<li>Segundo ítem de la lista</li>
</ul>
<h2><a href="http://www.cs.luther.edu">Luther CS </a><h2>
</body>
</html>
Figura 3: Un árbol que corresponde a los elementos de marcado de una página Web¶
Figura 3: Un árbol que corresponde a los elementos de marcado de una página Web
El código fuente HTML y el árbol que acompaña a dicho código fuente ilustran otra jerarquía. Observe que cada nivel del árbol corresponde a un nivel de anidamiento dentro de las etiquetas HTML. La primera etiqueta en el código fuente es <html> y la última es </html>. Todas las demás etiquetas de la página están dentro de esa pareja. Si usted comprueba, verá que esta propiedad de anidamiento es cierta en todos los niveles del árbol.