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

A node is a structure which may contain data and connections to other nodes, sometimes called edges or links. Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn with descendants going downwards). A node that has a child is called the child's parent node (or superior). All nodes have exactly one parent, except the topmost root node, which has none. A node might have many ancestor nodes, such as the parent's parent. Child nodes with the same parent are sibling nodes. Typically siblings have an order, with the first one conventionally drawn on the left. Some definitions allow a tree to have no nodes at all, in which case it is called empty.

An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). Thus the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

Each non-root node can be treated as the root node of its own subtree, which includes that node and all its descendants.^[a][3]

Other terms used with trees:

Neighbor

Parent or child.

Ancestor

A node reachable by repeated proceeding from child to parent.

Descendant

A node reachable by repeated proceeding from parent to child. Also known as subchild.

Degree

For a given node, its number of children. A leaf, by definition, has degree zero.

Degree of tree

The degree of a tree is the maximum degree of a node in the tree.

Distance

The number of edges along the shortest path between two nodes.

Level

The level of a node is the number of edges along the unique path between it and the root node.^[4] This is the same as depth.

Width

The number of nodes in a level.

Breadth

The number of leaves.

Complete tree

A tree with every level filled, except the last.

Forest

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.
• Cómo 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 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: 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