Arboles binarios

Tema 4: Árboles. Árboles binarios.

4

T.A.D. 04/05

ÁRBOLES. ÁRBOLES BINARIOS.

Hasta ahora nos hemos dedicado a estudiar TADes que de una u otra forma eran de
naturaleza lineal, o unidimensional. En los tipos abstractos de datos lineales existen exactamente
un elemento previo y otro siguiente (excepto para el primero y el último, si los hay); en las
estructuras no lineales, comoconjuntos o árboles, este tipo de secuencialidad no existe, aunque
en los árboles existe una estructura jerárquica, de manera que un elemento tiene un solo
predecesor, pero varios sucesores.
Una exploración algo amplia en el campo de la ciencia de la computación nos lleva a
situaciones en que las representaciones lineales son inadecuadas, tanto en sentido conceptual
como práctico. Un pasoimportante lo representan los árboles binarios, y el siguiente vendrá dado
con el estudio de la noción general de árbol. En capítulos posteriores, lo extenderemos hasta
llegar a los grafos.
Un árbol impone una estructura jerárquica sobre una colección de objetos. Ejemplos
claros de utiización de árboles se presentan tanto dentro como fuera del área de computación
(indices de libros, árbolesgenealógicos, etc.); en Informática constituyen una de las estructuras
más utilizadas, con aplicaciones que van desde los árboles sintácticos utilizados para la
representación y/o interpretación de términos de un lenguaje o expresiones aritméticas, pasando
por los arboles de activación de procedimientos recursivos, hasta la representación de datos que
se desea mantener ordenados con un tiempo de accesorelativamente bajo. En general, se usarán
árboles siempre que se quiera representar información jerarquizada, cuando esta converja en un
solo punto.

4.1

ARBOLES Y SUS PROPIEDADES

Intuitivamente, podemos visualizar árboles como una forma de organizar información de
forma jerárquica, con un único punto de entrada y una serie de caminos que van abriéndose en
cada punto hacia sussucesores.
Desde un punto de vista formal (teoría de conjuntos), un árbol se puede considerar como
una estructura A = (N,—), constituida por un conjunto, N, cuyos elementos se denominan nodos,
y una relación de orden parcial transitiva, —, definida sobre N, y caracterizada por la existencia
de
- Un elemento minimo (anterior a todos los demás) único, la raiz.
›! r 0 N ' (œ n…r 0 N, r — n).
- Unpredecesor único para cada nodo p distinto de la raiz, es decir, un nodo, q, tal que
q — p y para cualquier nodo q' con las mismas caracteristicas se cumple q' — q.
œ n 0 N ' n … r 6 (›! m 0 N, ((m — n) 1 (œ s…m 0 N ' s — n 6 s — m))).
Los ascendientes de un nodo se definen como el conjunto formado por su predecesor
único y los ascendientes de éste, cuando estos existan: Asc(n) = {m: m— n}.Antepasado y
ancestro suelen ser utilizados como sinónimos de ascendiente.

1

Tema 4: Árboles. Árboles binarios.

T.A.D. 04/05

Los descendientes de un nodo se definen como el conjunto formado por todos aquellos
nodos que lo tienen en su conjunto de ascendientes: Desc(n) = {m: n— m} = {m: n 0 Asc(m)}.
Esta estructura se puede considerar una estructura recursiva teniendo en cuenta que cadanodo del árbol, junto con todos sus descendientes, y manteniendo la ordenación original,
constituye también un árbol o subárbol del árbol principal, caracteristica esta que permite
definiciones simples de árbol, más apropiadas desde el punto de vista de la teoria de tipos
abstractos de datos, y, ajustadas, cada una de ellas, al uso que se vaya a hacer de la noción de
árbol.
Las dosdefiniciones más comunes son las de árbol general y la de árbol de orden N, que
se pueden dar en los términos siguientes:
Un árbol general con nodos de un tipo T es un par (r, LA) formado por un nodo
r (la raiz) y una lista (si se considera relevante el orden de los subárboles) o un conjunto
(si éste es irrelevante) LA (bosque), posiblemente vacio, de árboles generales del mismo
tipo (subárboles de...