Árbol (informática)

Un árbol simple sin ordenar. En este diagrama, el nodo con la etiqueta 7 tiene dos hijos, el 2 y el 6, y un padre, el 2. La raíz, al inicio, no tiene padre.

En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados.

Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos) , con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz.

Alternativamente, un árbol se puede definir de manera abstracta en su conjunto como un árbol ordenado, con un valor asignado a cada nodo. Ambas perspectivas son útiles: mientras que un árbol puede ser analizado matemáticamente, realmente es representado como una estructura de datos en la que se trabaja con cada nodo por separado (en lugar de como una lista de nodos y una lista de adyacencia entre nodos, como un grafo). Mirando a un árbol como conjunto, se puede hablar de el nodo padre de un nodo dado, pero en general se habla de una estructura de datos de un nodo dado que sólo contiene la lista de sus hijos sin referencia a su padre (si lo hay).

Definición

No es un árbol: Hay dos partes sin conectar (A→B y C→D→E), luego existe más de una raíz.
No es un árbol: En el ciclo 1-2-4-3, el 4 tiene más de un padre.
No es un árbol: En el ciclo B→C→E→D→B, B tiene más de un padre.
No es un árbol: En el ciclo A→A, A es la raíz, pero también tiene un padre.
Cada lista lineal es trivialmente un árbol

Un árbol es una estructura (posiblemente no lineal) de datos compuesta de nodos, vértices y aristas que es acíclica. Un árbol que no tiene ningún nodo se llama árbol vacío o nulo. Un árbol que no está vacío consta de un nodo raíz y potencialmente muchos niveles de nodos adicionales que forman una jerarquía.

Other Languages
français: Arbre enraciné
Bahasa Indonesia: Pohon (struktur data)
한국어: 트리 구조
norsk bokmål: Tre (datastruktur)