Árbol (tipo de datos abstracto)

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, de 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:

• Sistemas de archivos para:
  • Estructura de directorio utilizada para organizar subdirectorios y archivos ( los enlaces simbólicos crean gráficos que no son de árbol, al igual que múltiples enlaces duros al mismo archivo o directorio)
  • El mecanismo utilizado para asignar y vincular bloques de datos en el dispositivo de almacenamiento.
• Jerarquía de clases o "árbol de herencia" que muestra las relaciones entre clases en programación orientada a objetos ; la herencia múltiple produce gráficos que no son árboles
• Árboles de sintaxis abstracta para lenguajes informáticos
• Procesamiento del lenguaje natural :
  • Analizar árboles
  • Modelado de enunciados en una gramática generativa
  • Árbol de diálogo para generar conversaciones
• Modelos de objetos de documento ("árbol DOM") de documentos XML y HTML
• Los árboles de búsqueda almacenan datos de una manera que hace posible un algoritmo de búsqueda eficiente a través del recorrido del árbol.
  • Un árbol de búsqueda binario es un tipo de árbol binario
• Representación de listas ordenadas de datos
• Imágenes generadas por computadora :
  • Partición del espacio , incluida la partición del espacio binario
  • Composición digital
• Almacenamiento de árboles Barnes-Hut utilizados para simular galaxias
• Implementando montones
• Colecciones de conjuntos anidados
• Taxonomías jerárquicas como la Clasificación Decimal Dewey con secciones de especificidad creciente.
• Memoria temporal jerárquica
• Programación genética
• Agrupamiento jerárquico

Los árboles se pueden utilizar para representar y manipular diversas estructuras matemáticas, como:

• Rutas a través de un gráfico de nodos y aristas arbitrario (incluidos multigráficos ), creando múltiples nodos en el árbol para cada nodo de gráfico utilizado en múltiples rutas
• Cualquier jerarquía matemática

Las estructuras de árbol se utilizan a menudo para mapear las relaciones entre cosas, como por ejemplo:

• Componentes y subcomponentes que se pueden visualizar en un dibujo de vista explosionada
• Llamadas de subrutinas utilizadas para identificar qué subrutinas de un programa llaman a otras subrutinas de forma no recursiva
• Herencia del ADN entre especies por evolución , del código fuente por proyectos de software (por ejemplo, la línea de tiempo de distribución de Linux ), de diseños en varios tipos de automóviles, etc.
• El contenido de los espacios de nombres jerárquicos

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:

Vecino

Padre o hijo.

Antepasado

Un nodo al que se puede llegar mediante procedimientos repetidos del hijo al padre.

Descendiente

Nodo al que se puede llegar mediante el paso repetido del padre al hijo. También conocido como subhijo .

Grado

Para un nodo determinado, su número de hijos. Una hoja, por definición, tiene grado cero.

Grado de arbol

El grado de un árbol es el grado máximo de un nodo en el árbol.

Distancia

El número de aristas a lo largo de la ruta más corta entre dos nodos.

Nivel

El nivel de un nodo es el número de aristas a lo largo de la ruta única entre él y el nodo raíz. ^[3] Esto es lo mismo que la profundidad.

Ancho

El número de nodos en un nivel.

Amplitud

El número de hojas.

Bosque

Un conjunto de uno o más árboles disjuntos.

Árbol ordenado

Un árbol con raíz en el que se especifica un orden para los hijos de cada vértice.

Tamaño de un árbol

Número de nodos en el árbol.

• Enumerando todos los elementos
• Enumerar una sección de un árbol
• Buscando un articulo
• Agregar un nuevo elemento en una posición determinada del árbol
• Eliminar un elemento
• Poda : Quitar una sección entera de un árbol.
• Injerto: Añadir una sección entera a un árbol
• Encontrar la raíz de cualquier nodo
• Encontrar el ancestro común más bajo de dos nodos

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]

Esta sección no cita ninguna fuente . Por favor, ayude a mejorar esta sección añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado . ( Abril de 2022 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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:

valor: T → E

niños: V → F

nulo: () → F

nodo: E × F → T

con los axiomas:

valor(nodo( e , f )) = e

hijos(nodo( e , f )) = f

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).

Esta sección no cita ninguna fuente . Por favor, ayude a mejorar esta sección añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado . ( Abril de 2022 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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):

• Un árbol enraizado con la dirección "alejada de la raíz" (un término más específico es " arborescencia "), lo que significa:
  • Un gráfico dirigido ,
  • cuyo gráfico subyacente no dirigido es un árbol (cualquiera dos vértices están conectados por exactamente un camino simple), ^[5]
  • con una raíz distinguida (un vértice se designa como raíz),
  • que determina la dirección de los bordes (las flechas apuntan lejos de la raíz; dado un borde, el nodo desde el cual apunta el borde se llama padre y el nodo al cual apunta el borde se llama hijo ), junto con:
• un ordenamiento de los nodos secundarios de un nodo determinado, y
• un valor (de algún tipo de datos) en cada nodo.

A menudo, los árboles tienen un factor de ramificación fijo ( outdegree ) (más propiamente dicho, 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 hace que algunas definiciones sean más simples, otras más complicadas: un árbol con raíz no debe 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 con raíz tal que ..." Por otro lado, los árboles vacíos simplifican la definición de un factor de ramificación fijo: con árboles vacíos permitidos, 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).

• Búsqueda de árboles distribuidos
• Categoría: Árboles (estructuras de datos) (catálogos de tipos de árboles computacionales)

• Donald Knuth . El arte de la programación informática : algoritmos fundamentales , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Sección 2.3: Árboles, págs. 308–423. 
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introduction to Algorithms , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 10.4: Representación de árboles con raíz, págs. 214-217. Capítulos 12-14 (árboles binarios de búsqueda, árboles rojo-negros, aumento de estructuras de datos), págs. 253-320. 

Wikimedia Commons alberga una categoría multimedia sobre Estructuras de árboles .

• Descripción del Diccionario de Algoritmos y Estructuras de Datos