Inge

Transparencias del libro Rodríguez Artalejo, M., González-Calero, P.A., Gómez Martín, M.A.: Estructuras de datos, un enfoque moderno. Editorial Complutense 2011.

ARBOLES
Modelo matemático y especificación Técnicas de implementación Recorridos de árboles binarios Arboles de búsqueda Colas de prioridad y montículos

— — — — —

i

Arboles

1

5.1 Modelo matemático y especificación
Los árboles son estructuras jerárquicas formadas por nodos, de acuerdo con la siguiente construcción inductiva:
—

Un solo nodo forma un árbol a; se dice que el nodo es raíz del árbol. a Dados n árboles ya construidos a1, … , an , se puede construir un nuevo árbol a añadiendo un nuevo nodo como raíz y conectándolo con las raíces de los ai. Se dice que los ai son los hijos de a.
a … …

—a1

an

a1

an



Los árboles tienen muchos usos para representar jerarquías y clasificaciones, dentro y fuera de la Informática: árboles genealógicos, árboles taxonómicos, organización de un libro en capítulos y secciones, estructura de directorios y archivos, árbol de llamadas de una función recursiva, … Se utilizan también para representar estructuras sintácticas, como expresiones* + 2 x y 3

Arboles

2

o incluso sentencias de un lenguaje
si condición < x y x + 2 x y entonces := * 3 2 y * x 3 sino := * y



Podemos clasificar los árboles atendiendo a distintos criterios
—

—

—

—

Ordenados o no ordenados Un árbol es ordenado si el orden de los hijos de cada nodo es relevante. Etiquetados o no etiquetados Un árbol está etiquetado si hayinformaciones asociadas a sus nodos. Generales o n-arios Un árbol se llama general si no hay una limitación fijada al número de hijos de cada nodo. Si el número de hijos está limitado a un valor fijo n, se dice que el árbol es n-ario (binario, ternario, …). Con o sin punto de interés En un árbol con punto de interés hay un nodo distinguido (aparte de la raíz, que es distinguida en cualquier árbol).Arboles

3

5.1.1 Modelo matemático
Arboles generales


Adoptamos un modelo de árbol basado en la idea de representar las posiciones de los nodos como cadenas de números naturales positivos: — La raíz de un árbol tiene como posición la cadena vacía ε. * — Si un cierto nodo de un árbol tiene posición α ∈ ℵ+ , el hijo número i de ese nodo tendrá posición α.i.
A B 1 A 1.1 C 1.2 A 2 E 3.1 B 3.2 D3.3.1 D 3

F

3.3

G

3.4



De esta forma, un árbol se puede modelar como una aplicación:
a : N → V

E 3.3.2

donde N ⊆ ℵ+* es el conjunto de posiciones de los nodos, y V es el conjunto de valores posibles (etiquetas) asociados a los nodos. En el ejemplo anterior
N = { ε, 1, 2, 3, 1.1, 1.2, 3.1, 3.2, 3.3, 3.4, 3.3.1, 3.3.2 } a(ε) = ‘A’ a(1) = ‘B’


a(2) = ‘A’

a(3) = ‘D’etc.

En general, un conjunto N ⊆ ℵ+* de cadenas de números naturales positivos, debe cumplir las siguientes condiciones para ser válido como conjunto de posiciones de los nodos de un árbol general:
— — — —

N es finito. ε∈N posición de la raíz. α.i ∈ N ⇒ α ∈ N cerrado bajo prefijos. α.i ∈ N ∧ 1 ≤ j < i ⇒ α.j ∈ N hijos consecutivos sin huecos.

Arboles

4

Terminología


Dadoun árbol a : N → V — Nodo es cada posición, junto con la información asociada: (α, a(α)) — Raíz es el nodo de posición ε. Hojas son los nodos de posición α tal que no existe i tal que α.i ∈ N. Nodos internos son los nodos que no son hojas. — Un nodo α.i tiene como padre a α, y se dice que es hijo de α. — Dos nodos de posiciones α.i, α.j (i ≠ j) se llaman hermanos. — Camino es una sucesión de nodostal que cada uno es padre del siguiente: α, α.i1, … , α.i1. … .in
— —

—

—

—

—

n es la longitud del camino. Rama es cualquier camino que comience en la raíz y termine en una hoja. El nivel o profundidad de un nodo de posición α es |α|+1. Es decir: n+1, siendo n la longitud del camino (único) que va de la raíz al nodo. En particular, — el nivel de la raíz es 1, y — el nivel de un...