.svg/1280px-Tree_(computer_science).svg.png)
En informática , un árbol es un tipo de datos abstractos ampliamente utilizado que representa una estructura de árbol jerárquica con un conjunto de nodos conectados . Cada nodo del árbol se puede conectar a muchos hijos (dependiendo del tipo de árbol), pero debe estar conectado exactamente a un padre, [1] excepto el nodo raíz , que no tiene padre (es decir, el nodo raíz como nodo superior en la jerarquía del árbol). Estas restricciones significan que no hay ciclos o "bucles" (ningún nodo puede ser su propio ancestro) y también que cada hijo puede ser tratado como el nodo raíz de su propio subárbol, lo que hace que la recursividad sea una técnica útil para atravesar árboles . A diferencia de las estructuras de datos lineales , muchos árboles no pueden representarse mediante relaciones entre nodos vecinos (nodos padre e hijo de un nodo considerado, si existen) en una sola línea recta (llamada borde o enlace entre dos nodos adyacentes).
Los árboles binarios son un tipo comúnmente utilizado, que limitan el número de hijos de cada padre a dos como máximo. Cuando se especifica el orden de los hijos, esta estructura de datos corresponde a un árbol ordenado en teoría de grafos . Se puede asociar un valor o puntero a otros datos con cada nodo del árbol o, a veces, solo con los nodos hoja , que no tienen nodos secundarios.
El tipo de datos abstractos (ADT) se puede representar de varias maneras, incluida una lista de padres con punteros a hijos, una lista de hijos con punteros a padres o una lista de nodos y una lista separada de relaciones padre-hijo ( un tipo específico de lista de adyacencia ). Las representaciones también pueden ser más complicadas, por ejemplo, utilizando índices o listas de antepasados para el rendimiento.
Los árboles tal como se utilizan en informática son similares, pero pueden ser diferentes, a las construcciones matemáticas de árboles en la teoría de grafos , árboles en la teoría de conjuntos y árboles en la teoría descriptiva de conjuntos .
Los árboles se utilizan comúnmente para representar o manipular datos jerárquicos en aplicaciones como:
Los árboles se pueden utilizar para representar y manipular diversas estructuras matemáticas, como por ejemplo:
Las estructuras de árbol se utilizan a menudo para mapear las relaciones entre cosas, como por ejemplo:
Los documentos JSON y YAML se pueden considerar como árboles, pero normalmente se representan mediante listas y diccionarios anidados .
Un nodo es una estructura que puede contener datos y conexiones con otros nodos, a veces llamados bordes o enlaces . Cada nodo de un árbol tiene cero o más nodos secundarios , que se encuentran debajo de él en el árbol (por convención, los árboles se dibujan con los descendientes hacia abajo). Un nodo que tiene un hijo se denomina nodo padre (o superior ) del hijo . Todos los nodos tienen exactamente un padre, excepto el nodo raíz superior , que no tiene ninguno. Un nodo puede tener muchos nodos ancestros , como el padre del padre. Los nodos secundarios con el mismo padre son nodos hermanos . Por lo general, los hermanos tienen un orden, y el primero se dibuja convencionalmente a la izquierda. Algunas definiciones permiten que un árbol no tenga ningún nodo, en cuyo caso se llama vacío .
Un nodo interno (también conocido como nodo interno , inodo para abreviar o nodo de rama ) es cualquier nodo de un árbol que tiene nodos secundarios. De manera similar, un nodo externo (también conocido como nodo externo , nodo hoja o nodo terminal ) es cualquier nodo que no tiene nodos secundarios.
La altura de un nodo es la longitud del camino descendente más largo hasta una hoja desde ese nodo. La altura de la raíz es la altura del árbol. La profundidad de un nodo es la longitud del camino hasta su raíz (es decir, su camino raíz ). Por lo tanto, el nodo raíz tiene profundidad cero, los nodos hoja tienen altura cero y un árbol con un solo nodo (por lo tanto, raíz y hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (árbol sin nodos, si están permitidos) tiene una altura −1.
Cada nodo no raíz puede tratarse como el nodo raíz de su propio subárbol , que incluye ese nodo y todos sus descendientes. [un] [2]
Otros términos utilizados con árboles:
Pasar por los elementos de un árbol, a través de las conexiones entre padres e hijos, se llama caminar por el árbol , y la acción es un caminar por el árbol. A menudo, se puede realizar una operación cuando un puntero llega a un nodo en particular. Un recorrido en el que cada nodo principal se recorre antes que sus hijos se denomina recorrido de preorden ; un recorrido en el que se recorre a los hijos antes de que se recorra a sus respectivos padres se denomina recorrido posterior a la orden ; un recorrido en el que se atraviesa el subárbol izquierdo de un nodo, luego el nodo mismo y finalmente su subárbol derecho se denomina recorrido en orden . (Este último escenario, que se refiere exactamente a dos subárboles, un subárbol izquierdo y un subárbol derecho, supone específicamente un árbol binario ). Un recorrido por orden de niveles realiza efectivamente una búsqueda en amplitud en la totalidad de un árbol; Los nodos se recorren nivel por nivel, donde se visita primero el nodo raíz, seguido por sus nodos secundarios directos y sus hermanos, seguido por sus nodos nietos y sus hermanos, etc., hasta que se hayan atravesado todos los nodos del árbol.
Hay muchas formas diferentes de representar árboles. En la memoria de trabajo, los nodos suelen ser registros asignados dinámicamente con punteros a sus hijos, sus padres o ambos, así como a cualquier dato asociado. Si tienen un tamaño fijo, los nodos pueden almacenarse en una lista. Los nodos y las relaciones entre nodos pueden almacenarse en un tipo especial separado de lista de adyacencia . En las bases de datos relacionales , los nodos generalmente se representan como filas de una tabla, con ID de fila indexadas que facilitan los punteros entre padres e hijos.
Los nodos también se pueden almacenar como elementos en una matriz , con relaciones entre ellos determinadas por sus posiciones en la matriz (como en un montón binario ).
Un árbol binario se puede implementar como una lista de listas: el encabezado de una lista (el valor del primer término) es el hijo izquierdo (subárbol), mientras que la cola (la lista del segundo término y siguientes) es el hijo derecho ( subárbol). Esto se puede modificar para permitir valores también, como en las expresiones S de Lisp , donde la cabeza (valor del primer término) es el valor del nodo, la cabeza de la cola (valor del segundo término) es el hijo izquierdo y la cola de la cola (lista del tercer término y siguientes) es el hijo correcto.
Los árboles ordenados pueden codificarse naturalmente mediante secuencias finitas, por ejemplo con números naturales. [4]
Como tipo de datos abstracto , el tipo de árbol abstracto T con valores de algún tipo E se define, utilizando el tipo de bosque abstracto F (lista de árboles), mediante las funciones:
con los axiomas:
En términos de teoría de tipos , un árbol es un tipo inductivo definido por los constructores nil (bosque vacío) y nodo (árbol con nodo raíz con valor e hijos dados).
Vista en su conjunto, una estructura de datos de árbol es un árbol ordenado , generalmente con valores adjuntos a cada nodo. Concretamente, es (si se requiere que no esté vacío):
A menudo, los árboles tienen un factor de ramificación fijo (más propiamente, acotado) ( outgrado ), particularmente siempre tienen dos nodos secundarios (posiblemente vacíos, por lo tanto, como máximo dos nodos secundarios no vacíos ), de ahí un "árbol binario".
Permitir árboles vacíos hace que algunas definiciones sean más simples, otras más complicadas: un árbol enraizado debe no estar vacío, por lo tanto, si se permiten árboles vacíos, la definición anterior se convierte en "un árbol vacío o un árbol enraizado tal que ...". Por otro lado, los árboles vacíos simplifican la definición del factor de ramificación fijo: si se permiten árboles vacíos, un árbol binario es un árbol tal que cada nodo tiene exactamente dos hijos, cada uno de los cuales es un árbol (posiblemente vacío).
Un padre puede tener varios nodos secundarios. ... Sin embargo, un nodo hijo no puede tener varios padres. Si un nodo hijo tiene varios padres, entonces es lo que llamamos un gráfico.
