derecha|192px|miniatura|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 miniatura|x100px|No es un árbol: Hay dos partes sin conectar (A→B y C→D→E), luego existe más de una raíz. miniatura|x100px|No es un árbol: En el ciclo 1-2-4-3, el 4 tiene más de un padre. miniatura|x100px|No es un árbol: En el ciclo B→C→E→D→B, B tiene más de un padre. miniatura|x50px|No es un árbol: En el ciclo A→A, A es la raíz, pero también tiene un padre. miniatura|x50px|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.

Terminología utilizada en árboles Raíz: El nodo superior de un árbol.

Hijo: Un nodo conectado directamente con otro cuando se aleja de la raíz.

Padre: La noción inversa de hijo.

Hermanos: Un conjunto de nodos con el mismo padre.

Descendiente: Un nodo accesible por descenso repetido de padre a hijo.

Ancestro: Un nodo accesible por ascenso repetido de hijo a padre.

Hoja: Un nodo sin hijos.

Nodo interno: Un nodo con al menos un hijo.

Grado: Número de subárboles de un nodo.

Brazo: La conexión entre un nodo y otro.

Camino: Una secuencia de nodos y brazos conectados con un nodo descendiente.

Nivel: El nivel de un nodo se define por 1 + (el número de brazos entre el nodo y la raíz).

Altura de un nodo: La altura de un nodo es el número de brazos en el camino más largo entre ese nodo y una hoja.

Altura de un árbol: La altura de un árbol es la altura de su nodo raíz.

Profundidad: La profundidad de un nodo es el número de brazos desde la raíz del árbol hasta un nodo.

Bosque: Un bosque es un conjunto de árboles n ≥ 0 disjuntos.

Rama: Una ruta del nodo raíz a cualquier otro nodo.

Tipo de datos frente a la estructura de datos Hay una distinción entre un árbol como un tipo de datos abstracto y como una estructura concreta de datos, de forma análoga a la distinción entre una lista y lista enlazada. Como tipo de dato, un árbol tiene un valor e hijos, y los hijos son a su vez subárboles; el valor y los hijos de un árbol se interpreta como el valor del nodo raíz y los subárboles de los hijos del nodo raíz. Para permitir que los árboles puedan ser finitos, hay que, o bien permitir que la lista de los hijos pueda estar vacía, o permitir que los árboles puedan estar vacíos, en cuyo caso la lista de los hijos pueden ser de tamaño fijo (factor de ramificación, especialmente 2 o binario), si se desea.

Como una estructura de datos, un árbol vinculado es un grupo de nodos, donde cada nodo tiene un valor y una lista de referencias a otros nodos (sus hijos). Esta estructura de datos realmente define a un grafo dirigido,Adecuadamente, un gráfico dirigido ordenado y arraigado. porque puede tener bucles o varias referencias al mismo nodo, del mismo modo que una lista enlazada. Luego también existe el requisito de que no hay dos referencias que apuntan al mismo nodo (que cada nodo tiene como máximo un solo padre, y de hecho todos lo tienen, a excepción de la raíz), y un árbol que viola esto es árbol corrupto.

Debido al uso de referencias a los árboles en la estructura de datos de un árbol enlazado, a menudo se habla de árboles en los que implícitamente están siendo representados por referencias al nodo raíz, ya que esto es, normalmente, la forma en la que se aplican realmente. Por ejemplo, en lugar de un árbol vacío, uno puede tener una referencia nula: un árbol nunca está vacío, sino que una referencia a un árbol puede ser nula.

Recursividad

De forma recursiva, un árbol como un tipo de datos se define como un valor (de un cierto tipo de datos, posiblemente vacía), junto con una lista de los árboles (posiblemente una lista vacía), los subárboles de sus hijos: t: v [t, ..., t[k]] (Un árbol t se compone de un valor v y una lista de otros árboles.)

Más elegantemente, a través de la recursión mutua, de los cuales un árbol es uno de los ejemplos más básicos, un árbol se puede definir en términos de un bosque (una lista de árboles), donde un árbol consta de un valor y un bosque (los subárboles de sus hijos): f: [t, ..., t[k]] t: v f

Tenga en cuenta que esta definición es en términos de valores, y es apropiada en lenguaje funcional (se asume la transparencia referencial); diferentes árboles no tienen conexión, ya que son simplemente listas de valores.

Como una estructura de datos, un árbol se define como un nodo (la raíz), que a su vez consta de un valor (de algún tipo de datos, posiblemente vacío), junto con una lista de referencias a otros nodos (lista posiblemente vacía y referencias posiblemente nulas): n: v [&n, ..., &n[k]] (Un nodo n se compone de un valor v y una lista de referencias a otros nodos.)

Esta estructura de datos define un grafo dirigido, y para que sea un árbol hay que añadir una condición en su estructura global (en su topología), y esto es que a lo sumo una referencia puede apuntar a cualquier nodo dado (un nodo tiene como máximo un solo padre), y ningún nodo del árbol puede apuntar a la raíz. De hecho, todos los nodos (que no sean la raíz) deben tener exactamente un padre, y la raíz no debe tener ningún padre.

De hecho, dada una lista de nodos, y para cada nodo de una lista de referencias a sus hijos, no se puede saber si esta estructura es un árbol o no sin analizar su estructura global, como se define a continuación.

Teoría de tipos Como un tipo abstracto de datos (TAD), el tipo de árbol abstracto T con los valores de algún tipo E se define utilizando el tipo abstracto de los bosques F (lista de árboles), por las funciones: valor: T → E hijo: T → F nulo: () → F nodo: E × F → T con los axiomas: valor(nodo(e, f)) = e hijo(nodo(e, f)) = f En términos de la teoría de tipos, un árbol es un tipo inductivo definido por los constructores nulo (bosque vacío) y nodo (árbol con raíz con valor dado e hijos).

Matemáticamente Visto en su conjunto, una estructura de datos en árbol es un árbol ordenado, generalmente con valores unidos a cada nodo. Concretamente, es (si se requiere que no sea vacío): Un árbol arraigado en dirección contraria a la raíz (un término más estrecho es una arborescencia), significa: Un grafo dirigido. Cuyo grafo no dirigido subyacente es un árbol (dos vértices están conectados por exactamente un camino simple). Con una raíz destacada (un vértice se designa como la raíz). Lo que determina la dirección en los brazos (flechas que apuntan fuera de la raíz; dado un brazo, el nodo desde donde la flecha apunta se llama el padre y el nodo al que apunta se llama el hijo). Junto con: Una ordenación en los nodos hijos de un nodo dado, y un valor (de algún tipo de datos) en cada nodo. A menudo, los árboles tienen un factor de ramificación de dos nodos hijo (posiblemente vacíos, por lo tanto, como máximo dos nodos secundarios no vacíos). En estos casos se habla de un árbol binario.

Permitir árboles vacíos hace algunas definiciones simples un poco más complicadas: un árbol con raíz no debe estar vacío, por lo tanto, si a los árboles vacíos se le asigna la definición anterior, en su lugar se convierte en un árbol vacío, o un árbol arraigado de tal manera que .... Por otro lado, los árboles vacíos se simplifican definiendo un factor de ramificación fijo: con árboles vacíos, un árbol binario es un árbol de tal manera que cada nodo tiene exactamente dos hijos, cada uno de los cuales es un árbol (posiblemente vacío). Los conjuntos de operaciones en un árbol deben incluir la operación de tenedor.

Terminología Un nodo es una estructura que puede contener un valor o condición, o representar una estructura de datos separada (que puede llegar a ser un árbol). Cada nodo en un árbol tiene cero o más nodos hijo, que se disponen debajo de este en el árbol (por convenio, los árboles se dibujan de arriba abajo). Un nodo que tiene un hijo se llama el nodo padre del hijo (o nodo superior). Todos los nodos tienen al menos un padre.

Un nodo interno (también conocido como un nodo inferior o nodo rama) es cualquier nodo de un árbol que tiene nodos secundarios. De manera similar, un nodo externo (también conocido como un nodo exterior, nodo hoja, o nodo terminal) es cualquier nodo que no tiene nodos hijos.

El nodo más alto en un árbol se llama el nodo raíz. Dependiendo de la definición, un árbol puede ser obligado a tener un nodo raíz (en cuyo caso ningún árbol estaría vacío), o que se les permita estar vacíos, en cuyo caso no necesariamente tienen un nodo raíz. Siendo el nodo superior, el nodo raíz no tendrá un padre. Es el nodo en el que los algoritmos comienzan, ya que, como estructura de datos que es, sólo se puede pasar de padres a hijos. Tenga en cuenta que algunos algoritmos comienzan en la raíz, pero primero visitan a los nodos hoja (acceden al valor de los nodos hoja), y acceden por último a la raíz (es decir, que acceden por primera vez a los hijos de la raíz, pero solo acceder al valor de la raíz como último paso). Todos los demás nodos pueden ser accedidos siguiendo los brazos o enlaces. (En la definición formal, cada uno de esos caminos es único.) En los diagramas, el nodo raíz se extrae convencionalmente en la parte superior. En algunos árboles, tales como los montículos, el nodo raíz tiene propiedades especiales. Cada nodo en un árbol puede ser visto como el nodo raíz del subárbol con raíz en ese nodo.

miniatura|300px|Las rotaciones en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto) del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico. La altura de un nodo es la longitud de la trayectoria descendente más larga a una hoja desde ese nodo. La altura de la raíz es la altura del árbol. La profundidad de un nodo es la longitud de la trayectoria a su raíz (es decir, su camino hacia la raíz). Esto es necesario comúnmente en la manipulación de diversos árboles autobalanceables (árboles AVL, en particular). El nodo raíz tiene una profundidad cero, los nodos hoja tienen altura cero, y un árbol con un solo nodo (por lo tanto, tanto una raíz y una hoja) tienen profundidad y altura cero. Convencionalmente, un árbol vacío (árbol con ningún nodo, si es que están permitidos) tienen profundidad y altura -1.