Árbol (tipo de dato abstracto)

En informática , un árbol es un tipo de dato abstracto ampliamente utilizado que representa una estructura de árbol jerárquica con un conjunto de nodos conectados . Cada nodo en el árbol puede estar conectado a muchos hijos (dependiendo del tipo de árbol), pero debe estar conectado a exactamente un padre, ^{[ 1 ] [ 2 ]} 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 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 recursión sea una técnica útil para el recorrido del árbol . 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 arista o enlace entre dos nodos adyacentes).

Los árboles binarios son un tipo de estructura de datos muy utilizado, que limita el número de hijos de cada nodo padre a un máximo de dos. Cuando se especifica el orden de los hijos, esta estructura de datos corresponde a un árbol ordenado en la teoría de grafos . Se puede asociar un valor o un puntero a otros datos a cada nodo del árbol, o a veces solo a los nodos hoja , que no tienen nodos hijos.

El tipo de dato abstracto (TDA) puede representarse de diversas maneras, como mediante una lista de nodos padres con punteros a nodos hijos, una lista de nodos hijos con punteros a nodos 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 complejas, por ejemplo, utilizando índices o listas de ancestros para optimizar el rendimiento.

Los árboles utilizados en informática son similares, pero pueden ser diferentes, a las construcciones matemáticas de árboles en la teoría de grafos , los árboles en la teoría de conjuntos y los árboles en la teoría descriptiva de conjuntos .

Un nodo es una estructura que puede contener datos y conexiones a otros nodos, a veces llamados aristas o enlaces . Cada nodo en un árbol tiene cero o más nodos hijos , 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 llama nodo padre del hijo (o superior ). Todos los nodos tienen exactamente un padre, excepto el nodo raíz más alto , que no tiene ninguno. Un nodo puede tener muchos nodos ancestros , como el padre del padre. Los nodos hijos 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 interior , inodo o nodo de rama ) es cualquier nodo de un árbol que tiene nodos hijos. De manera similar, un nodo externo (también conocido como nodo exterior , nodo hoja o nodo terminal ) es cualquier nodo que no tiene nodos hijos.

La altura de un nodo es la longitud del camino descendente más largo desde ese nodo hasta una hoja. 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 ruta 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 que no es raíz puede ser tratado como el nodo raíz de su propio subárbol , que incluye ese nodo y todos sus descendientes. ^{[ a ] ​​[ 3 ]}

Otros términos utilizados en relación con los árboles:

Vecino

Padre o hijo.

Antepasado

Un nodo al que se puede llegar procediendo repetidamente desde el hijo al padre.

Descendiente

Un nodo al que se puede llegar procediendo repetidamente de padre a hijo. También conocido como subhijo .

Grado

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

Grado de árbol

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 del camino más corto entre dos nodos.

Nivel

El nivel de un nodo es el número de aristas a lo largo del camino único entre él y el nodo raíz. ^{[ 4 ]} Esto es lo mismo que la profundidad.

Ancho

El número de nodos en un nivel.

Amplitud

El número de hojas.

Árbol completo

Un árbol con todos los niveles completados, excepto el último.

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.

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

Existen diversas formas 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 el tamaño es fijo, los nodos pueden almacenarse en una lista. Los nodos y las relaciones entre ellos pueden almacenarse en un tipo especial de lista de adyacencia . En las bases de datos relacionales , los nodos se representan normalmente como filas de tabla, con identificadores de fila indexados que facilitan la vinculación entre padres e hijos.

Los nodos también se pueden almacenar como elementos en una matriz , y las relaciones entre ellos están 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 de términos siguientes) es el hijo derecho (subárbol). Esto se puede modificar para permitir también valores, como en las expresiones S de Lisp , donde la cabeza (el valor del primer término) es el valor del nodo, la cabeza de la cola (el valor del segundo término) es el hijo izquierdo y la cola de la cola (la lista de términos siguientes) es el hijo derecho.

Los árboles ordenados pueden codificarse de forma natural mediante secuencias finitas, por ejemplo, con números naturales. ^{[ 5 ]}

Como tipo de dato 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: T → F

nil: () → 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).

Vista en su conjunto, una estructura de datos de árbol es un árbol ordenado , generalmente con valores asociados a cada nodo. Concretamente, es (si se requiere que no esté vacía):

• Un árbol enraizado con la dirección "alejándose de la raíz" (un término más específico es " arborescencia "), lo que significa:
  • Un grafo dirigido ,
  • cuyo grafo subyacente no dirigido es un árbol (cualesquiera dos vértices están conectados por exactamente un camino simple), ^{[ 6 ]}
  • con una raíz distinguida (un vértice se designa como la raíz),
  • que determina la dirección de las aristas (las flechas apuntan alejándose de la raíz; dada una arista, el nodo desde el que apunta la arista se llama padre y el nodo hacia el que apunta la arista se llama hijo ), junto con:
• un ordenamiento en los nodos hijos de un nodo dado, y
• un valor (de algún tipo de dato) en cada nodo.

A menudo, los árboles tienen un factor de ramificación fijo (más propiamente, limitado) ( grado de salida ), en particular, siempre tienen dos nodos hijos (posiblemente vacíos, por lo tanto, como máximo dos nodos hijos no vacíos ), de ahí que se les llame "árbol binario".

Permitir árboles vacíos simplifica algunas definiciones y complica otras: un árbol con raíz debe ser no 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: 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).

Los árboles se utilizan comúnmente para representar o manipular datos jerárquicos en aplicaciones como:

• Sistemas de archivos para:
  • Estructura de directorios utilizada para organizar subdirectorios y archivos ( los enlaces simbólicos crean gráficos que no son de árbol, al igual que los múltiples enlaces duros al mismo archivo o directorio).
  • El mecanismo utilizado para asignar y enlazar bloques de datos en el dispositivo de almacenamiento.
• Jerarquía de clases o "árbol de herencia" que muestra las relaciones entre las clases en la programación orientada a objetos ; la herencia múltiple produce grafos que no son árboles.
• Árboles de sintaxis abstracta para lenguajes de programación
• Procesamiento del lenguaje natural :
  • Árboles de análisis sintáctico
  • 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 forma que permiten un algoritmo de búsqueda eficiente mediante el recorrido del árbol.
  • Un árbol de búsqueda binaria es un tipo de árbol binario.
• Representación de listas de datos ordenadas
• Imágenes generadas por computadora :
  • Particionamiento del espacio , incluido el particionamiento binario del espacio.
  • Composición digital
• Almacenamiento de árboles Barnes-Hut utilizados para simular galaxias
• Implementación de 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, tales como:

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

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

• Componentes y subcomponentes que pueden visualizarse en un dibujo de vista explosionada.
• Las llamadas a subrutinas se utilizan 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 cronología de la 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 y diccionarios anidados .

• Búsqueda en árbol distribuido
• 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 . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7Sección 10.4: Representación de árboles con raíz, págs.  214–217. Capítulos 12–14 (Árboles de búsqueda binaria, árboles rojo-negro, ampliación de estructuras de datos), págs.  253–320.

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