1. Árboles

Publicado por: Gilber Briceño

1. DEFINICIÓN.

Un árbol es una estructura de datos ramificada (no lineal) que puede representarse como un conjunto de nodos enlazados entre sí por medio de  ramas. La información contenida en un nodo puede ser de cualquier tipo simple o estructura de datos.

Los árboles permiten modelar diversas entidades del mundo real tales como, por ejemplo, el índice de un libro, la clasificación del reino animal, el árbol genealógico de un apellido, etc.

La figura 1.1. muestra un ejemplo de estructura en árbol (la numeración de los nodos es arbitraria). Se entiende por “topología” de un árbol a su representación geométrica.

Figura 1.1.  Ejemplo de árbol

Una definición formal es la siguiente: 

Un árbol es una estructura de datos base que cumple una de estas dos condiciones:

• Es una estructura vacía, o
• Es un nodo de tipo base que tiene de 0 a N subárboles disjuntos entre sí.

Al nodo base, que debe ser único, se le denomina raíz y se establece el convenio de representarlo gráficamente en la parte superior.

En un árbol se representa una relación jerárquica a partir del nodo raíz en sentido vertical descendente, definiendo niveles. El nivel del nodo raíz es 1.

Desde la raíz se puede llegar a cualquier nodo progresando por las  ramas y atravesando los sucesivos niveles estableciendo así un camino. En la figura 1.1. el nodo 7 está a nivel 3 y la secuencia de nodos 4, 8 y 11 constituye un (sub)camino.

Se dice que un nodo es antecesor de otro cuando ambos forman parte de un camino y el primero se encuentra en un nivel superior (numeración más baja) al del segundo (numeración más alta). En el ejemplo anterior el nodo 4 es antecesor del 11. Por el contrario, el nodo 11 es descendiente del 4. 

La relación entre dos nodos separados de forma inmediata por una rama se denomina padre/hijo. En el ejemplo de la figura 1.1., el nodo 5 es hijo del nodo 2 y, recíprocamente, el nodo 2 es padre del nodo 5. En un árbol un padre puede tener varios hijos pero un hijo solo puede tener un padre.

Se denomina grado al número de hijos de un nodo. Por ejemplo, en la figura 1.1. el nodo 4 tiene grado 3 y el nodo 7 tiene grado 0.

Se dice que un nodo es hoja cuando no tiene descendientes (grado 0).

Se establecen los siguientes atributos para un árbol:

Altura / profundidad / nivel: La mayor altura / profundidad / nivel de sus nodos. La altura del árbol de la figura 1.1. es 4 (la alcanzan sus nodos 10, 11 y 12).

Amplitud / Anchura: El número de nodos del nivel más poblado. En el ejemplo, 5 (nivel 3).

Grado: el mayor de los grados de los nodos. En el ejemplo, 3 (nodos 1 y 4).

Finalmente, indicar que se dice que un árbol es  completo cuando todos sus nodos (excepto las hojas) tienen el mismo grado y los diferentes niveles están poblados por completo. A veces resulta necesario completar un árbol añadiéndole nodos  especiales. La figura 1.2. representa el resultado de completar el árbol de la figura 1.1. (en la figura los nodos especiales aparecen sombreados)

Figura 1.2.  Árbol completo de grado 3.

En un árbol completo de grado g, la amplitud del nivel n es , y el número total de nodos del árbol es: