Arboles

Arboles
Introducción
Los arboles es una estructura de datos muy importante en informática y en ciencias de la computación. Son estructuras no lineales, al contrario que los arrays y las listas enlazadas.
Se utiliza para representar formulas algebraicas, para organizar objetos en tal forma que las búsquedas sean eficientes. Casi todos los Sistemas Operativos almacenan sus archivos en árboles.13.1. Arboles Generales y Terminología
Implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas.
Consta de un conjunto finito de elementos, denominados nodos y de un conjunto finito de líneas dirigidas, denominadas ramas. El número de ramas asociado con un nodo es el grado del nodo
Definición: El árbolconsta de un conjunto finito de elementos, llamados nodos y de un conjunto finito de líneas dirigidas, llamadas ramas, que conectan nodos.
Si el árbol no está vacío, entonces el primer nodo se llama raíz.

13.1.1. Terminología.
Además del nodo raíz, existen muchos términos utilizados en la descripción de los atributos de un árbol.
A los nodos sucesores se les llaman hijos. Los hijos de un nodo ylos hijos de estos hijos se les llaman descendientes, y los padres y los abuelos de un nodo son sus ascendientes.
El nivel de un nodo es su distancia al nodo raíz. La raíz tiene una distancia de cero de sí misma, por ello se dice que están en el nivel 0. Los hijos del nodo raíz están en el nivel 1, sus hijos están en el nivel 2, y así sucesivamente. Una cosa importante es la relación entreniveles y hermanos.

En camino es una secuencia de nodos en los que cada nodo es adyacente al siguiente. Si llega a él cada nodo del árbol puede ser alcanzado, siguiendo el único camino que comienza en el nodo raíz.
Definición: El nivel de un nodo es su distancia desde el nodo raíz. La altura o profundidad de un árbol es el nivel de la hoja del camino más largo desde la raíz mas uno

El árbol sedivide en subárboles.
Un subárbol es cualquier estructura conectada por debajo de un nodo raíz. Cada nodo de un árbol es la raíz de un subárbol que se define por el nodo y sus descendientes, Los subárboles se pueden subdividir en subárboles.
Definición recursiva: Un árbol es un conjunto de nodos que es vacío o tiene un nodo denominado, llamado raíz, de que jerárquicamente desciende cero o mássubárboles, que son también Arboles.
13.1.2. Representación gráfica de un árbol
Existen dos maneras fáciles:
Representación como árbol invertido
Es el diagrama o carta de organización hasta ahora en las diferentes figuras. Nodo raíz está en la parte más alta de una jerarquía de las que descienden ramas llamadas nodos hijos y así sucesivamente.

Representación de lista
Se usan paréntesis.Notación utilizada como expresiones algebraicas. Cada paréntesis abierto indica el comienzo de un nuevo nivel y cada paréntesis cerrado completa el nivel se mueve hacia arriba un nivel en el árbol.

13.2. ARBOLES BINARIOS
Sus nodos no pueden tener más de dos subárboles pueden tener cero, uno o dos hijos (subárboles). Se llama al nodo de la izquierda como hijo izquierdo y al de la derecha como hijoderecho

Es una estructura recursiva y se divide en tres subconjuntos


13.2.1. Equilibrio
La distancia de un nodo a la raíz determina la eficiencia con la que puede ser localizado. Para determinar si un árbol está equilibrado, se calcula su factor de equilibrio. El factor de equilibrio es la diferencia en altura entre subárboles derecho e izquierdo. Si la altura del subárbol izquierdo eshI y la altura del subárbol derecho es hD’ entonces el factor de equilibrio del árbol B se determina por la siguiente formilla: B= hD - hI
Un árbol está perfectamente equilibrado si su equilibrio es cero y sus subárboles so también perfectamente equilibrados.
13.2.2. Arboles binarios completos
Un árbol binario completo de profundidad n es un árbol en el que para cada nivel del 0 al nivel n-1,...