Programación Estructuras de Datos 5

Árboles
219
__________________________________________________________________________________

Capítulo 5 Árboles

Los árboles (ing., tree) son estructuras que organizan sus elementos, denominados nodos,
formando jerarquías. Su definición inductiva es:
- Un único nodo es un árbol; a este nodo se le llama raíz del árbol.
- Dados n árboles a1, ..., an, se puede construir uno nuevo como resultadode enraizar
un nuevo nodo con los n árboles ai . Generalmente, el orden de los ai es significante y
así lo consideramos en el resto del capítulo; algunos autores lo subrayan llamándolos
árboles ordenados (ing., ordered trees). Los árboles ai pasan a ser subárboles del
nuevo árbol y el nuevo nodo se convierte en raíz del nuevo árbol.
La representación gráfica de los árboles refleja claramente lajerarquía resultante de su
definición.

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 matemático de árbol data de mediados del siglo XIX y su uso en el mundo de la
programación es habitual. Ya ha sido introducido en la sección 1.2 como una representación
intuitiva de la idea de término; en general, los árbolespermiten almacenar cómodamente
cualquier tipo de expresión dado que la parentización, la asociatividad y la prioridad de los
operadores quedan implícitos y su evaluación es la simple aplicación de una estrategia de
recorrido. Suelen utilizarse para representar jerarquías de todo tipo: taxonomías, relaciones
entre módulos, etc. Igualmente es destacable su contribución a diversos campos de lainformática: árboles de decisión en inteligencia artificial, representación de gramáticas y
programas en el ámbito de la compilación, ayuda en técnicas de programación

© Los autores, 1998; © Edicions UPC, 1998.

2
20
Estructuras de datos. Especificación, diseño e implementación
__________________________________________________________________________________

(transformación de programas recursivosen iterativos, etc.), índices en ficheros de acceso
por clave, bases de datos jerárquicas, etc.

5.1 Modelo y especificación
En esta sección introducimos el modelo formal asociado a un árbol, que emplearemos para
formular diversas definiciones útiles, y también su especificación ecuacional. Hablando con
propiedad, hay varios modelos de árboles que surgen a partir de todas las combinacionesposibles de las características siguientes:
- El proceso de enraizar puede involucrar un número indeterminado de subárboles o
bien un número fijo n. En el primer caso hablamos de árboles generales (ing., general
tree) y en el segundo caso de árboles n-arios (ing., n-ary tree)1; en estos últimos
destaca el caso de n = 2, los denominados árboles binarios (ing., binary tree), sobre el
cual nos centraremos alo largo del texto dada su importancia, siendo inmediata la
extensión a cualquier otro n. En los árboles n-arios se definirá el concepto de árbol
vacío que ampliará el conjunto de valores del tipo.
- Los nodos del árbol pueden contener información o no; el primer caso es el habitual y
responde al uso de árbol como almacén de información, pero también se puede dar la
situación en que sólo interesereflejar la jerarquía, sin necesidad de guardar ningún
dato adicional. En el resto del capítulo nos centraremos en el primer tipo de árbol,
porque generaliza el segundo. La información en los nodos se denominará etiqueta
(ing., label) y los árboles con información árboles etiquetados (ing., labelled tree).
- La signatura definida en los árboles puede ser muy variada. Destacamos dos familias:
enla primera se utilizan árboles enteros tal como se ha explicado en la introducción,
con operaciones de enraizar diversos árboles, obtener un subárbol y, si el árbol es
etiquetado, obtener la etiqueta de la raíz; la segunda familia define un nodo de
referencia para las actualizaciones y consultas, que puede cambiarse con otras
operaciones. Llamaremos al segundo tipo árboles con punto de interés,...