Análisis y Diseño de Algoritmos

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

Árboles

Introducción árboles

Una de las estructuras las datos más importantes y prominentes que existen es el árbol. No es un árbol en el sentido botánico de la palabra, sino uno de naturaleza más abstracta. Todos hemos visto usar tales árboles para describir conexiones familiares. Los dos tipos más comunes de árboles familiares son el ‘árbol de antecesores’, que empieza en un individuo y va hacia atrás a través de padres, abuelos, etc., y el ‘árbol de descendientes’, que va hacia delante a través de hijos, nietos, etc.

David Harel, ‘The Spirit of Computing’

Definición.

Ø Definición de Árbol. Similitud con las Listas.

l Árbol Degenerado.

l ¿Cómo representarlos?

o Mediante Grafos:

Figura - 1.
Representación de un árbol
mediante un grafo

o Mediante Conjuntos.

wpe7.jpg (7907 bytes)

Figura - 2.
Representación
de un árbol mediante un grafo

Ø Una estructura árbol con tipo base T es:

l Bien la estructura vacía.

l O bien un nodo de tipo T junto con un número finito de estructuras árbol, de tipo base T, disjuntas, llamadas subárboles.

Ø Declaración:

TArbol = ^TNodo;

TNodo = Record

Clave: TClave;

Izq, Der: TArbol

End;

2. Conceptos

Antecesor

Antecesor Directo

Sucesor

Sucesor Directo

Nodo Raíz.

Nodo Hoja

Nodo Interno

Nivel de un Nodo

Grado de un Nodo

Grado de un Árbol

Altura de un Árbol

Longitud de Camino

Longitud de Camino Interno

Árbol de expansión

Longitud de Camino Externo

Tabla - 1. Conceptos diversos sobre árboles.

*Concepto*	*Definiciones*	*Ejemplo*	*Observaciones*
Antecesor Directo	La clave "X" está inmediatamente por encima de la clave "Y" en el árbol y además están unidas.	El 2 es antecesor directo del 4, del 5 y del 6	La clave "X" es antecesora directa de la clave "Y"
Antecesor	Existe una sucesión de claves antecesoras directas para llegar desde "Y" hasta "X".	El 1 es antecesor del 4	La clave "X" es antecesora de "Y"
Sucesor Directo	La clave "X" está inmediatamente por debajo de la clave "Y" en el árbol y además están unidas.	El 5, el 4 y el 6 son sucesores directos del 2	Una clave "X" es sucesora directa de otra clave "Y"
Sucesor	Existe una sucesión de claves sucesoras directas para llegar desde "X" hasta "Y".	El 4 es sucesor del 1	La clave "X" es sucesora de "Y")
Nodo Raíz	aquel que no tiene antecesores.	El 1

Tabla -2. Conceptos básicos. Los ejemplos hacen referencia a la Figura - 1 (I).

*Concepto*	*Definiciones*	*Ejemplo*	*Observaciones*
Nodo Hoja	Aquel que no tiene sucesores.	El 4, el 5, el 6 y el 7
Nodo Interno	Aquel que no es ni raíz ni hoja.	El 2 y el 3
Nivel de un Nodo	Nº de tramos que hay que recorrer desde el nodo raíz hasta el nodo del que quiero calcular su nivel.	El nodo 7 tiene nivel 3.	Se considera que la raíz está en el nivel 1.
Grado de un Nodo	Nº de descendientes directos que tiene.	El 1 tiene grado 2. El 2 tiene grado tiene grado 3.
Grado de un Árbol	Mayor de los grados de los nodos que componen el árbol.	Grado del árbol = 3.	Un árbol de grado 1 ® Lista Un árbol de grado 2 ® Árbol Binario
Altura de un Árbol	Mayor de los niveles de los nodos que forman el árbol.	Altura del árbol = 3.

Tabla -3. Conceptos básicos. Los ejemplos hacen referencia a la Figura - 1 (II).

*Concepto*	*Definiciones*	*Ejemplo*	*Observaciones*
Longitud de Camino	Nº de arcos que hay que atravesar para ir desde la raíz hasta un nodo.	Longitud de camino del nodo 7 = 3.	La longitud de camino del nodo raíz se considera 1. Coincide con el NIVEL DE UN NODO.
Longitud de camino Interno	Nº de arcos que hay que atravesar para ir desde la raíz hasta un nodo. La longitud de camino del nodo raíz se considera 1.	1+2+2+3+3+3+3 = 17	n å i _* nº de claves i = 1
Árbol de expansión	Resultante de hacer que todos los nodos del árbol tengan el mismo grado.		Implica que hay que añadir una serie de Nodos Especiales que no pertenecen al árbol para conseguir esto (ver figura-3 ).
Longitud de camino externo	Suma de las longitudes de camino de los nodos especiales.	412 + 23 + 2 = 56

Tabla -4. Conceptos básicos. Los ejemplos hacen referencia a la Figura - 1 (III).

wpeF.jpg (8676 bytes) Nodo Especial

Figura - 3. Árbol de expansión de uno dado.