Ensayo Sobre Arboles de Algoritmos y Datos

Ensayo Sobre Arboles de Algoritmos y Datos

Mervyn Armando Fuentes Villegas

Instituto Universitario Politécnico “Santiago Mariño” Barcelona

Ensayo Sobre Arboles de Algoritmos y Datos

Los árboles dentro de la informática se refieren a un tipo de abstracto de datos que imita la jerarquía de un árbol, utilizando un valor raíz y subárboles con nodos padres, representando un conjunto de nodos enlazados.

Una estructura de datos árbol se definen atraves de una forma recursiva como una colección de nodos, los cuales surgen desde un nodo raíz, donde cada estructura es representada por un valor y un conjunto de referencias a subsecuentes nodos, donde los nodos principales son denominados padres y los subsecuentes hijos. Alternativamente pueden ser definidos de manera abstracta como arboles ordenados, esto es debido a que los árboles, si bien pueden ser analizados bajo conceptos matemáticos, son representados generalmente como estructuras de datos donde se trabaja cada nodo por separado. Mientras que si son visualizados como conjuntos se habla de una estructura donde un nodo dado solo contiene referencias a sus hijos sin referir al padre del mismo, si es que tiene uno.

Los nodos tienen como características generales: Los nodos tienen uno o ningún padre (El único nodo que no cumple esta regla es el nodo raíz) y pueden tener cero o más de dos hijos; donde si no tienen hijos serán denominados como nodos hoja o externo, de lo contrario son denominados también como nodo interno.

Los árboles son caracterizados mediante su altura y profundidad, siendo el primero el camino más largo entre el nodo raíz y un nodo hoja dentro del árbol, mientras que el segundo es la longitud del este camino. Un ejemplo seria:  donde el camino más largo seria del nodo A al G, es decir , por lo tanto tendría una altura de tres () y una profundidad de tres (.[pic 1][pic 2][pic 3][pic 4]

Otra propiedad de los arboles es la existencia de los arboles binarios, que son árboles que  o están vacíos, o bien consta de un nodo raíz con dos subárboles binarios quienes son denominados izquierdo y derecho. Estos nodos vacíos son representados atraves de un cuadrado, para que no exista algún tipo de ambigüedad a la hora de identificarlos.

Los arboles binarios pueden presentarse en tres tipos: Estrictos, Llenos y Completos.

Los Estrictos son aquellos donde si un subárbol presenta un vacío el otro también lo presentara, cada nodo solo puede presentar cero o dos hijos. Ejemplo: [pic 5]

Los Llenos son aquellos en los cuales la altura de ambos subárboles es idéntica y están llenos. Ejemplo: [pic 6]

Los Completos son donde el árbol está lleno hasta el penúltimo nivel y en el último los nodos se encuentran agrupados a la izquierda. Ejemplo: [pic 7]

Dentro de los arboles binarios también existes los montículos que son los nodos  almacenan elementos comprables mediante el “menor o igual que” y donde los nodos hijos son siempre de un elemento mayor al del sus padres. Ejemplo:  [pic 8]

Dónde:  [pic 9]

...