.svg/1280px-Tree_(computer_science).svg.png)
En informática , un árbol es un tipo de datos abstracto ampliamente utilizado que representa una estructura de árbol jerárquica con un conjunto de nodos conectados . Cada nodo del árbol puede estar conectado 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 el nodo más alto en la jerarquía del árbol). Estas restricciones significan que no hay ciclos o "bucles" (ningún nodo puede ser su propio antecesor), y también que cada hijo puede ser tratado como el nodo raíz de su propio subárbol, lo que hace que la recursión sea una técnica útil para el recorrido de árboles . A diferencia de las estructuras de datos lineales , muchos árboles no pueden representarse mediante relaciones entre nodos vecinos (nodos padre e hijos de un nodo en consideración, si existen) en una sola línea recta (llamada borde o enlace entre dos nodos adyacentes).
Los árboles binarios son un tipo de uso común que limita 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 la teoría de grafos . Un valor o puntero a otros datos puede estar asociado con cada nodo del árbol o, a veces, solo con los nodos hoja , que no tienen nodos hijos.
El tipo de datos abstracto (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 antecesores para mejorar el rendimiento.
Los árboles que se utilizan en informática son similares, pero pueden ser diferentes, a las construcciones matemáticas de árboles en teoría de grafos , árboles en teoría de conjuntos y árboles en 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:
Las estructuras de árbol se utilizan a menudo para mapear las relaciones entre cosas, como por ejemplo:
Los documentos JSON y YAML pueden considerarse como árboles, pero normalmente se representan mediante listas anidadas y diccionarios .
Un nodo es una estructura que puede contener datos y conexiones a otros nodos, a veces llamados aristas o enlaces . Cada nodo de un árbol tiene cero o más nodos secundarios , que están debajo de él en el árbol (por convención, los árboles se dibujan con descendientes que van hacia abajo). Un nodo que tiene un hijo se llama nodo padre del hijo (o superior ). 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 . Normalmente, 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 (es decir, raíz y hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (árbol sin nodos, si se permiten) tiene altura −1.
Cada nodo no raíz puede ser tratado como el nodo raíz de su propio subárbol , que incluye ese nodo y todos sus descendientes. [a] [2]
Otros términos utilizados con árboles:
El recorrido por los elementos de un árbol, mediante las conexiones entre padres e hijos, se denomina " recorrer el árbol" , y la acción es un "recorrido del árbol". A menudo, se puede realizar una operación cuando un puntero llega a un nodo en particular. Un recorrido en el que se recorre cada nodo padre antes que sus hijos se denomina " recorrido en preorden" ; un recorrido en el que se recorre a los hijos antes de que se recorra a sus respectivos padres se denomina " recorrido en posorden" ; un recorrido en el que se recorre 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 nivel realiza efectivamente una búsqueda en amplitud sobre la totalidad de un árbol; Los nodos se recorren nivel por nivel, donde primero se visita el nodo raíz, seguido de sus nodos secundarios directos y sus hermanos, seguido de sus nodos nietos y sus hermanos, etc., hasta que se hayan recorrido todos los nodos del árbol.
Existen muchas formas diferentes de representar árboles. En la memoria de trabajo, los nodos suelen ser registros asignados dinámicamente con punteros a sus hijos, a sus padres o a 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 independiente de lista de adyacencia . En las bases de datos relacionales , los nodos suelen representarse como filas de tabla, con identificadores de fila indexados 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: la cabeza 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 los términos subsiguientes) es el hijo derecho (subárbol). Esto se puede modificar para permitir valores también, como en las S-expresiones 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 los términos subsiguientes) es el hijo derecho.
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 node (árbol con nodo raíz con valor dado e hijos).
En conjunto, una estructura de datos en forma de árbol es un árbol ordenado , generalmente con valores asociados a cada nodo. En concreto, es (si se requiere que no esté vacío):
A menudo, los árboles tienen un factor de ramificación fijo ( outdegree ) (más propiamente, acotado ), en particular 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 simplifica algunas definiciones, y otras las complica: un árbol con raíz no debe estar vacío, por lo que si se permiten árboles vacíos, la definición anterior se convierte en "un árbol vacío o un árbol con raíz tal que...". Por otro lado, los árboles vacíos simplifican la definición de un 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).
secundario no puede tener varios padres. Si un nodo secundario tiene varios padres, entonces es lo que llamamos un gráfico.
