5.1 Concepto Arbol

Un árbol es una estructura que organiza sus  elementos, denominados nodos, 

formando jerarquías. Los científicos los utilizan los árboles generales para representar  

relaciones. Fundamentalmente, la relación  clave es la de «padre-hijo» entre los nodos 

del árbol. Si existen una arista (rama ) dirigida del nodo n al nodo m, entonces n es 

padre de m y m es hijo  de n.

Cada nodo de un árbol tiene al menos un padre  y existe un único nodo, denominado  raíz del árbol, que no tiene padre. El nodo A es la raíz del árbol. Un nodo que no tiene hijos se llama hoja (terminal) del árbol. Las hojas del árbol de la figura 1 son C,D,E,F. Todo nodo que no es raíz, ni hoja es conocido como interior como es B. 

 La relación Padre-Hijo entre los nodos se generaliza en las relaciones ascendente(antecesor) y descendiente. En la Fig.1 A es un antecesor de D y por consiguiente D es un descendiente de A. Un subárbol  de un árbol es cualquier nodo  del árbol junto con todos sus descendientes como en la figura 1, B y sus descendientes son un subárbol. El grado (aridad) es el numero de hijos del nodo.

 La aridad de un árbol se define como el máximo de la aridad de sus nodos. Se le denomina camino  a la secuencia de nodos conectados dentro de un árbol, donde la rama es un camino que termina en una hoja. Para determinar el nivel de un nodo, se calcula por medio de los nodos que se encuentra entre el y la raíz, por consiguiente el nivel de un árbol es el numero de nodos que se encuentran entre la raiz y la hoja mas profunda; al máximo nivel de un árbol es también conocido como Altura. 

Ejemplo 1.1 

Dado el árbol general de la figura 1.2, se hace sobre el las siguientes consideraciones.

Longitud de Camino  

Se define la longitud de camino X como el numero de arcos que debe ser recorridos para llegar desde la raíz al nodo X. Por definición la raiz tiene longitud de 1, sus descendientes directos longitud de camino 2 y así sucesivamente. Considérese la figura 

1.22  el nodo B tiene la longitud de camino 2, el nodo I longitud de camino 4 y el nodo Longitud de camino 3.

Longitud de Camino Interno 

La longitud de camino interno es la suma de las longitudes de camino de todos los nodos del árbol. Puede calcularse por medio de las siguientes formula:

donde i representa el nivel del árbol, h su altura y ni el numero de nodos en el nivel i. 

La LCI del árbol de la figura 1.22 se calcula  así: 

LCI = 1 * 1 + 2 * 2 + 5 * 3 + 4 * 4 = 36 

Ahora bien, la media de la longitud de camino interno (LCIM) se calcula dividiendo la LCI entre el numero de nodos del árbol (n). Se expresa: 

y significa el numero de arcos que deben ser recorridos en un promedio para llegar,  partiendo desde la raiz, a un nodo cualquiera del árbol. 

La LCIM del árbol de la figura 1.22 se calcula mediante:

LCIM= 36/12=3

Longitud de Camino Externo 

Para definir la longitud de camino externo es necesario primero definir los  conceptos árbol extendido y nodo especial. Un árbol extendido es aquel en el que  el numero de hijos de cada nodo es igual al grado del árbol. Si alguno de los nodos del  árbol no cumple con esta condición entonces debe incorporársele al mismo nodo  especial; tanto como sea necesario satisfacer la condición. Los nodos especiales tienen  como objetivo remplazar las ramas vacías o nulas, no pueden tener descendientes y  normalmente se representan con la forma de un cuadrado. En la figura  1.23 se  presenta el árbol extendido de la figura 1.22.  

El  numero de nodos especiales de este nodo es de 25. se puede definie ahora  la longitud de camino externo como la suma de las longitudes de caminos externo  como la suma de las longitudes  de caminos de todos los nodos especiales del árbol. 

Se calcula por medio de la siguiente formula: 

donde i representa el nivel del árbol ,h su altura y n el numero de nodos especiales en  el nivel i. Obsérvese que i comienza desde 2, puesto que la raiz se encuentra  en el  nivel 1 y no puede ser nodo especial. 

La LCE del árbol de la figura 1.23  se calcula de la siguiente manera: 

LCE = 1 * 2 + 1 * 3 + 11 * 4 + 12 * 5 = 109

Ahora bien la media  de la longitud d camino  externo (LCEM)se calcula dividiendo LCE entre el numero de nodos especiales del árbol (ne). Se expresa:

y significa el numero de arcos que debe ser recorridos en promedio para llegar  partiendo de la raiz, a un nodo especial cualquiera del árbol. 

LCEM=109/25=4.36

Ejemplo:  Dado el árbol general de la figura 1.24 y el árbol extendido de la figura 1.25 se calcula: 

La longitud de camino interno: 

LCI = 1 * 1 + 3 * 2 + 9 * 3 = 34 

La media  de la longitud de camino interno: 

LCIM = 34 / 13 = 2.61 

La longitud de camino externo: 

LCE = 1 * 2 + 3 * 3 + 36 * 4 = 155 

Y la media de la longitud de camino externo: 

LCEM = 155 / 40 = 3.87