Estructuras de Datos de Árboles

Árboles en General

• Un árbol es una estructura de datos no lineal y jerárquica compuesta por nodos conectados mediante aristas.
• Las estructuras de datos forman la columna vertebral de cualquier lenguaje de programación, permitiendo organizar y almacenar datos eficientemente.
• Los árboles se utilizan en varios aspectos de la informática, desde sistemas de bases de datos hasta la inteligencia artificial.
• Un árbol representa una estructura jerárquica con un conjunto de nodos conectados.
• Cada nodo en el árbol puede conectar a muchos hijos (según el tipo de árbol), pero debe estar conectado exactamente a un padre, excepto el nodo raíz, que no tiene padre.
• No hay ciclos o "bucles" (ningún nodo puede ser su propio ancestro).
• Cada hijo puede ser tratado como el nodo raíz de su propio subárbol, haciendo de la recursividad una técnica útil para atravesar árboles.
• A diferencia de estructuras de datos lineales, muchos árboles no se pueden representar mediante relaciones entre nodos vecinos en una sola línea recta.

Ejemplos y Aplicaciones de Árboles

• La organización de una empresa (organigrama) es un ejemplo común de un árbol.
• Un árbol genealógico de una persona es una representación de un árbol.
• La organización de torneos deportivos (tabla de partidos) puede ser representada como un árbol.
• Los árboles se aplican computacionalmente para realizar ordenaciones de datos.
• Los árboles se aplican computacionalmente para realizar búsquedas.
• Los árboles se aplican computacionalmente para asignar bloques de memoria de tamaño variable.
• Los árboles se aplican computacionalmente para organizar tablas de símbolos en compiladores.
• Los árboles se aplican computacionalmente para representar tablas de decisión.
• Los árboles se aplican computacionalmente para solucionar juegos.
• Los árboles se aplican computacionalmente para probar teoremas.
• Formalmente, un árbol es un conjunto finito de uno o más nodos tal que: a) Existe un nodo especial llamado la raíz del árbol. b) Los nodos restantes están particionados en m >= 0 conjuntos distintos disjuntos T1... Tm, y cada uno de estos conjuntos es a su vez un árbol. Los árboles T1... Tm son llamados subárboles de la raíz.
• Cualquier nodo es la raíz de un subárbol que consiste de él y los nodos debajo de él; por ello, la definición de árbol es recursiva.
• La forma más común para representar un árbol es usando un grafo.

Características y Propiedades de Árboles

• Dado un conjunto de elementos:
• Un árbol puede estar vacío.
• Un árbol no vacío puede consistir de un solo elemento llamado nodo raíz.
• Un árbol consta de un nodo raíz que está conectado mediante arcos directos a un número finito de otros árboles.
• Un vértice o nodo del árbol puede tener un nombre y puede tener asociada a él información.
• El primer nodo de un árbol es llamado raíz.
• Las flechas que conectan un nodo a otro se llaman arcos o ramas.
• Los nodos terminales son aquellos que no conducen a algún nodo, y se llaman hojas.
• Los nodos que no son hojas se llaman nodos no terminales o nodos internos.
• Si un nodo n1 tiene una rama hacia el nodo n2, se dice que n2 es un nodo hijo de n1.
• Un camino es una lista de ramas contiguas que van de n1 a n2.
• Una propiedad que define a los árboles es que existe exactamente un camino entre la raíz y cada uno de los otros nodos en el árbol.
• La longitud de un camino es el número de nodos del camino menos uno, o equivalentemente, el número de arcos que contiene el camino.
• Por tanto, hay un camino de longitud cero de cualquier nodo a sí mismo.
• El número de hijos que parten de un nodo es llamado grado del nodo.
• El grado de un árbol es el grado máximo de los nodos del árbol.
• El nivel de un nodo es la longitud del camino que lo conecta al nodo raíz.
• La profundidad del nodo n es el largo del camino entre la raiz del árbol y el nodo nk.
• La profundidad de la raíz es siempre 0.
• La altura de un nodo nk es el máximo largo de camino desde nk hasta alguna hoja.
• Esto implica que la altura de toda hoja es 0.
• La altura de un árbol es igual a la altura de la raíz y tiene el mismo valor que la profundidad de la hoja más profunda.
• La altura de un árbol vacío es -1.
• Un subárbol de un árbol es un subconjunto de nodos del árbol conectados por ramas del propio árbol; éste es, a su vez, un árbol.
• Considerar un árbol con raíz A, nodos no-terminales A, B, C, D, E, G, J, padres A cuyos hijos son B, C; B cuyos hijos son D, E; C cuyos hijos son F, G, H; D cuyos hijos son I, J; E cuyos hijos son K, L; G cuyos hijos son M, N, O y J cuyos hijos son P.
• Los nodos hojas son I, P, K, L, F, M, N, O, P, Y H.
• Los nodos de grado 0 son: I, P, K, L, F, M, N, O, P, Y H (son las hojas del árbol).
• El nodo de grado 1 es J.
• Los nodos de grado 2 son A, B, D, E.
• Los nodos de grado 3 es C y G.
• El grado del árbol es 3.
• El camino del Nodo A al nodo P es (A,B,D, J,P) y longitud de camino es 4.
• Un conjunto de árboles es llamado un bosque.

Bosques

• Existe una pequeña diferencia entre un árbol y un bosque; si se elimina la raíz de un árbol, se obtiene un bosque, y reciprocamente, si se añade un nodo a un bosque, se obtiene un árbol.
• En los árboles de búsqueda, la búsqueda de un elemento en el árbol se realiza de manera eficiente, ya que se puede descartar la mitad de los elementos en cada comparación.
• Los árboles permiten la inserción y eliminación de elementos de manera eficiente, manteniendo la estructura del árbol balanceada.
• Los árboles son ideales para representar jerarquías, como la estructura de un sitio web o la organización de una empresa.
• Los árboles permiten recorrer los elementos de manera ordenada, ya sea ascendente o descendente.

Longitud de Camino Interno y Externo

• Nodos: Cada elemento que contiene un árbol.
• Nodo Raíz: Primer nodo; solo un nodo del árbol puede ser la raíz.
• Nodo Padre: Todos aquellos nodos que tienen al menos un hijo.
• Nodo Hijo: Todos aquellos que tienen un padre.
• Nodo Hermano: Aquellos nodos que comparten un mismo padre en común dentro de la estructura.
• Nodo Hoja: Nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura.
• Nodo Rama: Nodos que no son la raíz y que, además, tienen al menos un hijo.
• Nivel: Nos referimos como nivel a cada generación dentro del árbol.
• Cuando a un nodo hoja le agregamos un hijo, el nodo hoja pasa a ser un nodo rama.
• El árbol crece una generación.
• Cada generación tiene un número de nivel distinto que las demás generaciones.
• Un árbol vacío tiene 0 niveles.
• El nivel de la raíz es 1.
• El nivel de cada nodo se calcula contando cuantos nodos existen sobre él, hasta llegar a la raíz +1, y de forma inversa también se podría contar cuantos nodos existen desde la raíz hasta el nodo buscado +1.
• Imágen muestra los tipos de nodos, Raíz, Rama y Hoja.

Altura, Peso y Orden de Árboles

• Altura: Número máximo de niveles de un árbol.
• La altura se calcula mediante recursividad, tomando el nivel más grande de los dos subárboles de forma recursiva.
• La altura del árbol es 4.
• Peso: Conocemos como peso al número de nodos que tiene un árbol.
• Este factor es importante porque nos da una idea del tamaño del árbol y el tamaño en memoria que nos puede ocupar en tiempo de ejecución.
• El peso total del árbol es 15.
• El peso se puede calcular mediante cualquier tipo de recorrido donde se cuentan los nodos a medida que se avanza sobre la estructura.
• El peso de un árbol es igual a la suma del peso de los subárboles hijos + 1.
• Orden: El orden de un árbol es el número máximo de hijos que puede tener un nodo.
• Un árbol con orden = 1 no tendría sentido, ya que sería una estructura lineal; cada nodo solo podría tener un hijo y tendríamos un árbol degenerado.
• El árbol con orden = 2 tiene un grado máximo de 2 hijos por nodo.
• El árbol con orden = 3 tiene un grado máximo de 3 hijos por nodo.

Grado de un Árbol

• Este valor no lo calculamos, sino que ya lo debemos conocer cuando diseñamos nuestra estructura; ya que si queremos calcular esto es lo que obtendremos es el grado.
• Grado: Se refiere al número mayor de hijos que tiene algunos de los nodos del árbol, y está limitado por el orden, ya que éste indica el número máximo de hijos que puede tener un nodo.
• El árbol con grado = 2 tiene un máximo de 2 hijos por nodo.
• El árbol con grado = 3 tiene un máximo de 3 hijos por nodo.
• El grado se calcula contando de forma recursiva el número de hijos de cada sub-árbol hijo y el número de hijos del nodo actual para tomar el mayor; esta operación se hace de forma recursiva para recorrer todo el árbol.
• Sub-Árbol: Conocemos como sub-árbol a todo árbol generado a partir de una sección determinada del árbol.
• Por lo que podemos decir que un árbol es un nodo raíz con N sub-árboles.
• Existen escenarios donde podemos separar sub-árboles del árbol para procesarlo de forma separada; de esta forma, el sub-árbol pasa a ser un árbol independiente.
• También podemos eliminar sub-arboles completos.

Árboles Binarios

• Es un árbol en el que ningún nodo puede tener más de dos subárboles.
• En un árbol binario, cada nodo puede tener cero, uno o dos hijos.
• El nodo de la izquierda representa al hijo izquierdo, y el nodo de la derecha representa al hijo derecho.
• Un árbol binario (AB) es una estructura recursiva porque cada nodo es la raíz de su propio subárbol y tiene hijos, que son a su vez raíces de sus subárboles izquierdo y derecho.
• Esta estructura se caracteriza porque cada nodo solo puede tener un máximo de 2 hijos; es un árbol de grado 2.
• Árbol binario lleno: Es aquel en el que todos los nodos tienen cero o dos hijos, con excepción de la raíz.
• Árbol binario no lleno: No todos los nodos tienen cero ó dos hijos.
• Árbol binario perfecto: Es un árbol lleno en donde todas las hojas están en el mismo nivel.

Árboles Degenerados, Equilibrados y Completos

• Árbol degenerado: Un árbol se llama degenerado cuando solo contiene una hoja, y cada nodo no hoja solo tiene un hijo.
• Este tipo de árbol equivale a una lista enlazada.
• Árbol equilibrado: Para determinar si un AB está equilibrado, se calcula su factor de equilibrio (FE).
• El FE es la diferencia entre la altura del subárbol derecho menos el izquierdo.
• FE = hsd - hsi
• FE(a) =, FE(b) =, FE(c) =, FE(d)
• Un árbol está perfectamente equilibrado si su FE es 0, al igual que el de sus subárboles (caso raro).
• Un AB está equilibrado si la altura de sus subárboles difiere en no más de -1, 0, +1, y sus subárboles son también equilibrados.
• AB Completos
• Un AB completo (ABC) de profundidad N es un árbol en el que, para cada nivel, del 0 al nivel N-1, tiene un conjunto lleno de nodos, y todos los nodos hoja a nivel N ocupan las posiciones más a la izquierda del árbol.

Re-Presentación de Árboles Generales como Árboles Binarios

• Resulta más complejo manipular nodos de grado variable (número variable de relaciones) que nodos de grado fijo.
• Una posibilidad evidente para fijar un límite en el número de relaciones sería seleccionar un número K de hijos para cada nodo, donde K es el grado máximo para un nodo del árbol; sin embargo, esta solución desaprovecha mucho espacio de memoria.
• Para un árbol K-ario (es decir, grado k) con n nodos cada uno de tamaño fijo, el número de enlaces nulos en el árbol es n * (k-1) + 1 de los n*k campos de tipo enlace existentes n >= 1.
• Esto implica que, para un árbol de grado 3, más de 2/3 de los enlaces serán nulos, y la proporción de enlaces nulos se aproxima a 1 a medida que el grado del árbol aumenta.
• La importancia de poder utilizar árboles binarios para representar árboles generales reside en el hecho de que solo la mitad de los enlaces son nulos, además de facilitar su manipulación.
• Para representar cualquier árbol por un árbol binario, vamos a hacer uso implícito de que el orden de los hijos de un nodo en un árbol general no es importante.
• La razón por la cual, para representar un árbol general, se necesitarían nodos con muchos enlaces es que, hasta ahora, hemos pensado en una representación basada en la relación padre-hijo dentro del árbol, y un nodo pueden tener un gran número de hijos.

Representación de Árboles con Hijos y Hermanos más Cercanos

• Sin embargo, se puede encontrar una forma de representación donde cada nodo solo necesite tener dos relaciones: una que lo una con el hijo que tenga más a la izquierda, y otra que lo una con el siguiente nodo hermano por la derecha.
• Estrictamente hablando, como el orden de los hijos en un árbol no es importante, cualquiera de los hijos de un nodo podría ser el siguiente hijo que está más a la izquierda al nodo padre, y cualquiera de los nodos hermanos podría ser el siguiente hermano por la derecha.
• Por lo tanto, la elección de estos nodos no dejará de ser, hasta cierto punto, arbitraria; podemos basarnos para esta elección en la representación gráfica del árbol que se desea almacenar.
• En el árbol binario correspondiente al árbol de la figura, se obtiene conectando juntos a todos los hermanos de un node, eliminando los enlaces de un nodo con sus hijos, excepto el enlace con el hijo que tiene más a la izquierda.
• Este tipo de representación se puede identificar con los árboles binarios, asociando el enlace izquierdo del árbol con el enlace al hijo de la izquierda y el enlace derecho con el enlace al nodo hermano.
• Se observa que, de esta manera, el nodo raíz nunca tendrá un subárbol derecho ya que no tiene ningún nodo hermano, pero esto nos permite representar un bosque de árboles generales como un único árbol binario, obteniendo primero la transformación binaria de cada árbol y después uniendo todos los árboles binarios considerando que todos los nodos raíz son hermanos.

Representación de Árboles Binarios en Memoria

• Existen dos formas de representar un árbol binario en memoria:
• Por medio de punteros.
• Por medio de arreglos.

Representación Mediante Punteros

• La mejor solución para evitar los problemas asociados con la manipulación de arrays es la representación de los árboles binarios mediante estructuras dinámicas "puras" en el sentido de la creación en tiempo de ejecución de los nodos que sean necesarios (más) y la utilización de punteros para enlazar estos nodos.
• La estructura de cada nodo en esta representación coincide con la estructura de tres campos vistas.
• La única diferencia reside en la naturaleza de los campos de enlace; en este caso, se trata de punteros y no índices de un array.
• Tipos:
• Arbol = Puntero a Nodo Arbol;
• Nodo Arbol = registro --Info: valor; --izq, Der: Arbol; --Fin;
• Se puede comprobar como la representación en memoria de la estructura, en cuanto a definición de datos, coincide exactamente con la de, por ejemplo, una lista doblemente ligada sin que ello implique que se está hablando de la misma estructura de datos.
• De nuevo, hay que dejar muy claro que es la interpretación que hacemos de la representación en memoria la que define una estructura de datos (definición de operaciones), no la representación en sí misma.
• La representación enlazada tiene como principal desventaja que no resulta inmediato la determinación del padre de un nodo; es necesario buscar el camino de acceso al nodo dentro del árbol para poder obtener esa información.
• Sin embargo, en la mayoría de las aplicaciones es la representación más adecuada.
• En el caso de que la determinación del padre de un nodo sea una operación importante y frecuente en una aplicación concreta, se puede modificar ligeramente la estructura de cada nodo añadiendo un cuarto campo, también de tipo puntero a nodo árbol , que guarde la posición del padre de cada nodo.

Representación mediante Arrays

• Si el árbol binario que se desea representar cumple las condiciones de árbol lleno o árbol completo, es posible encontrar una buena representación secuencial del mismo.
• En esos casos, los nodos pueden ser almacenados en un array unidimensional A, de manera que el nodo enumerado como i se almacena en A[i].
• Esto permite localizar fácilmente las posiciones de los nodos padre, hijo izquierdo e hijo derecho de cualquier nodo i en un árbol binario arbitrario que cumpla tales condiciones.
• Si un árbol binario completo con n nodos se representa secuencialmente, se cumple que, para cualquier nodo con índice i, 0 <= i <= (n-1) se tiene que:
• El padre del nodo i estará localizado en la posición (i-1)/2 si i > 0. Si i = 0, se trata del nodo raíz y no tiene padre.
• El hijo izquierdo del nodo i estará localizado en la posición (2*(i+1)) - 1 si (2*(i+1)) - 1 < n. Si (2*(i+1)) - 1 >= n, el nodo no tiene hijo izquierdo.
• El hijo derecho del nodo i estará localizado en la posición (2*(i+1*)) si (2*(i+1)) < n. Si (2*(i+1)) >= n, el nodo no tiene hijo derecho.
• Evidentemente la representación puramente secuencial de un árbol se podría extender inmediatamente a cualquier árbol binario, pero esto implicaría en la mayoría de los casos desaprovechar gran cantidad del espacio reservado en memoria para el array.
• Así, aunque para árboles binarios completos la representación ideal y no se desaprovecha espacio, en el peor de los casos (para un árbol lineal (una lista) de profundidad K) se necesitará espacio para representar 2^K - 1 nodos, y sólo K de esas posiciones estarían realmente ocupadas.
• Además de los problemas de eficiencia, desde el punto de vista del almacenamiento en memoria, hay que tener en cuenta los problemas generales de manipulación de estructuras secuenciales.
• Las operaciones de inserción y borrado de elementos en cualquier posición del array implican necesariamente el movimiento potencial de muchos nodos.
• Estos problemas se pueden solventar adecuadamente mediante la utilización de una representación enlazada de nodos.