En informática , un árbol es un tipo de datos abstracto ampliamente utilizado que simula una estructura de árbol jerárquica , con un valor raíz y subárboles de hijos con un nodo padre , representado como un conjunto de nodos vinculados .
Una estructura de datos de árbol se puede definir de forma recursiva como una colección de nodos, donde cada nodo es una estructura de datos que consta de un valor y una lista de referencias a nodos. El inicio del árbol es el "nodo raíz" y los nodos de referencia son los "hijos". No se duplica ninguna referencia y ninguna apunta a la raíz.
Alternativamente, un árbol se puede definir de forma abstracta como un todo (globalmente) como un árbol ordenado , con un valor asignado a cada nodo. Ambas perspectivas son útiles: si bien un árbol se puede analizar matemáticamente como un todo, cuando en realidad se representa como una estructura de datos, generalmente se representa y se trabaja con él por separado por nodo (en lugar de como un conjunto de nodos y una lista de adyacencia de bordes entre nodos). , como se puede representar un dígrafo , por ejemplo). Por ejemplo, mirando un árbol como un todo, se puede hablar del "nodo padre" de un nodo dado, pero en general, como estructura de datos, un nodo dado solo contiene la lista de sus hijos pero no contiene una referencia. a su padre (si lo hay).
Un nodo es una estructura que puede contener un valor o condición, o representar una estructura de datos separada (que podría ser un árbol propio). 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 creciendo hacia abajo). Un nodo que tiene un hijo se llama nodo padre del hijo (o superior ). Un nodo tiene como máximo un padre, pero posiblemente muchos nodos ancestros , como el padre del padre. Los nodos secundarios con el mismo padre son nodos hermanos .
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.
El nodo superior de un árbol se llama nodo raíz . Dependiendo de la definición, se puede requerir que un árbol tenga un nodo raíz (en cuyo caso todos los árboles no están vacíos), o se puede permitir que esté vacío, en cuyo caso no necesariamente tiene un nodo raíz. Al ser el nodo superior, el nodo raíz no tendrá un padre. Es el nodo en el que comienzan los algoritmos en el árbol, ya que como estructura de datos, uno solo puede pasar de padres a hijos. Tenga en cuenta que algunos algoritmos (como la búsqueda en profundidad posterior al pedido) comienzan en la raíz, pero primero visitan los nodos hoja (acceden al valor de los nodos hoja), solo para visitar la raíz en último lugar (es decir, primero acceden a los hijos del root, pero solo acceda al valor de la raíz en último lugar). Se puede llegar a todos los demás nodos desde él siguiendo bordes o enlaces. (En la definición formal, cada una de estas rutas también es única). En los diagramas, el nodo raíz se dibuja convencionalmente en la parte superior. En algunos árboles, como los montones , el nodo raíz tiene propiedades especiales. Cada nodo de un árbol puede verse como el nodo raíz del subárbol enraizado en ese nodo.
La altura de un nodo es la longitud del camino descendente más largo 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 ruta hasta su raíz (es decir, su ruta raíz ). Esto es comúnmente necesario en la manipulación de varios árboles autoequilibrados, en particular los árboles AVL . El nodo raíz tiene profundidad cero, los nodos hoja tienen altura cero y un árbol con un solo nodo (por lo tanto, raíz y hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (árbol sin nodos, si están permitidos) tiene una altura -1.
Un subárbol de un árbol T es un árbol que consiste en un nodo en T y todos sus descendientes en T . [a] [1] Los nodos corresponden a subárboles (cada nodo corresponde al subárbol de sí mismo y todos sus descendientes) - el subárbol correspondiente al nodo raíz es el árbol completo, y cada nodo es el nodo raíz del subárbol que determina ; el subárbol correspondiente a cualquier otro nodo se denomina subárbol adecuado (por analogía con un subconjunto adecuado ).
Otros términos usados con árboles:
Un árbol es una estructura de datos no lineal, en comparación con matrices, listas enlazadas, pilas y colas que son estructuras de datos lineales. Un árbol puede estar vacío sin nodos o un árbol es una estructura que consta de un nodo llamado raíz y cero o uno o más subárboles.
Los árboles se dibujan a menudo en el plano. Los árboles ordenados se pueden representar esencialmente de forma única en el plano y, por lo tanto, se denominan árboles planos, de la siguiente manera: si uno fija un orden convencional (digamos, en sentido antihorario) y organiza los nodos secundarios en ese orden (primer borde padre entrante, luego primer hijo borde, etc.), esto produce una incrustación del árbol en el plano, única hasta la isotopía ambiental . A la inversa, tal incrustación determina un orden de los nodos secundarios.
Si uno coloca la raíz en la parte superior (los padres sobre los hijos, como en un árbol genealógico ) y coloca todos los nodos que están a una distancia determinada de la raíz (en términos de número de aristas: el "nivel" de un árbol) en un determinado línea horizontal, se obtiene un dibujo estándar del árbol. Dado un árbol binario, el primer hijo está a la izquierda (el "nodo izquierdo") y el segundo hijo está a la derecha (el "nodo derecho").
Algoritmos de búsqueda de gráficos y árboles |
---|
|
Listados |
|
Temas relacionados |
|
Pasar a través de los elementos de un árbol, por medio de las conexiones entre padres e hijos, se llama caminar por el árbol , y la acción es caminar por el árbol. A menudo, se puede realizar una operación cuando un puntero llega a un nodo en particular. Una caminata en la que se atraviesa cada nodo principal antes que sus hijos se denomina caminata de preorden ; una caminata en la que se atraviesa a los niños antes de atravesar a sus respectivos padres se denomina caminata posterior a la orden ; un recorrido en el que se atraviesa el subárbol izquierdo de un nodo, luego el propio nodo 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, asume específicamente unárbol binario .) Una caminata por orden de nivel realiza efectivamente una búsqueda en amplitud en la totalidad de un árbol; los nodos se atraviesan nivel por nivel, donde primero se visita el nodo raíz, seguido de sus nodos secundarios directos y sus hermanos, seguidos de sus nodos nietos y sus hermanos, etc., hasta que se hayan atravesado todos los nodos del árbol.
Hay muchas formas diferentes de representar árboles; Las representaciones comunes representan los nodos como registros asignados dinámicamente con punteros a sus hijos, sus padres o ambos, o como elementos en una matriz , con relaciones entre ellos determinadas por sus posiciones en la matriz (por ejemplo, montón binario ).
De hecho, un árbol binario se puede implementar como una lista de listas (una lista donde los valores son 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 y subsiguientes términos) es el hijo correcto (subárbol). Esto se puede modificar para permitir valores también, como en las expresiones S 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 de tercer y subsiguientes términos) es el hijo correcto.
En general, un nodo en un árbol no tendrá punteros a sus padres, pero esta información se puede incluir (expandiendo la estructura de datos para incluir también un puntero al padre) o almacenarse por separado. Alternativamente, los enlaces ascendentes se pueden incluir en los datos del nodo hijo, como en un árbol binario enhebrado .
Si los bordes (a los nodos secundarios) se consideran referencias, entonces un árbol es un caso especial de un dígrafo, y la estructura de datos del árbol se puede generalizar para representar gráficos dirigidos eliminando las restricciones que un nodo puede tener como máximo un padre, y que no se permiten ciclos. Los bordes todavía se consideran abstractamente como pares de nodos, sin embargo, los términos padre e hijo generalmente se reemplazan por una terminología diferente (por ejemplo, origen y destino ). Diferentes estrategias de implementaciónexiste: un dígrafo puede ser representado por la misma estructura de datos local que un árbol (nodo con valor y lista de hijos), asumiendo que "lista de hijos" es una lista de referencias, o globalmente por estructuras tales como listas de adyacencia .
En teoría de grafos , un árbol es un grafo acíclico conectado ; a menos que se indique lo contrario, en la teoría de grafos se supone que los árboles y gráficos no están dirigidos. No existe una correspondencia biunívoca entre árboles y árboles como estructura de datos. Podemos tomar un árbol arbitrario no dirigido, elegir arbitrariamente uno de sus vértices como raíz , hacer que todos sus bordes estén dirigidos haciéndolos apuntar lejos del nodo raíz - produciendo una arborescencia - y asignar un orden a todos los nodos. El resultado corresponde a una estructura de datos de árbol. Elegir una raíz diferente o un orden diferente produce una diferente.
Dado un nodo en un árbol, sus hijos definen un bosque ordenado (la unión de subárboles dada por todos los hijos, o equivalentemente tomando el subárbol dado por el propio nodo y borrando la raíz). Así como los subárboles son naturales para la recursividad (como en una búsqueda en profundidad), los bosques son naturales para la correcursión (como en una búsqueda en amplitud).
A través de la recursividad mutua , un bosque se puede definir como una lista de árboles (representados por nodos raíz), donde un nodo (de un árbol) consta de un valor y un bosque (sus hijos):
f: [n [1], ..., n [k]] n: vf
Existe una distinción entre un árbol como un tipo de datos abstracto y como una estructura de datos concreta, análoga a la distinción entre una lista y una lista enlazada .
Como tipo de datos, un árbol tiene un valor y sus hijos, y los hijos son ellos mismos árboles; el valor y los hijos del árbol se interpretan como el valor del nodo raíz y los subárboles de los hijos del nodo raíz. Para permitir árboles finitos, uno debe permitir que la lista de niños esté vacía (en cuyo caso se puede requerir que los árboles no estén vacíos, un "árbol vacío" en lugar de estar representado por un bosque de árboles cero), o permitir que los árboles estar vacío, en cuyo caso la lista de hijos puede ser de tamaño fijo ( factor de ramificación , especialmente 2 o "binario"), si se desea.
Como 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). También existe el requisito de que no haya dos referencias "descendentes" que apunten al mismo nodo. En la práctica, los nodos de un árbol también suelen incluir otros datos, como referencias siguientes / anteriores, referencias a sus nodos principales o casi cualquier cosa.
Debido al uso de referencias a árboles en la estructura de datos del árbol vinculado, los árboles a menudo se discuten implícitamente asumiendo que están siendo representados por referencias al nodo raíz, ya que a menudo es así como se implementan realmente. Por ejemplo, en lugar de un árbol vacío, uno puede tener una referencia nula: un árbol siempre no está vacío, pero una referencia a un árbol puede ser nula.
Recursivamente, como tipo de datos, un árbol se define como un valor (de algún tipo de datos, posiblemente vacío), junto con una lista de árboles (posiblemente una lista vacía), los subárboles de sus hijos; simbólicamente:
(Un árbol t consta de un valor v y una lista de otros árboles).
De manera más elegante, a través de la recursividad mutua , de la cual un árbol es uno de los ejemplos más básicos, un árbol se puede definir en términos de bosque (una lista de árboles), donde un árbol consiste en un valor y un bosque (los subárboles de su niños):
Tenga en cuenta que esta definición es en términos de valores y es apropiada en lenguajes funcionales (asume transparencia referencial ); diferentes árboles no tienen conexiones, ya que son simplemente listas de valores.
Como estructura de datos, un árbol se define como un nodo (la raíz), que a su vez consiste en un valor (de algún tipo de datos, posiblemente vacío), junto con una lista de referencias a otros nodos (lista posiblemente vacía, referencias posiblemente nulas ); simbólicamente:
(Un nodo n consta de un valor vy una lista de referencias a otros nodos).
Esta estructura de datos define un grafo dirigido, [b] y para que sea un árbol se debe agregar una condición en su estructura global (su topología), es decir, que como máximo una referencia puede apuntar a cualquier nodo dado (un nodo tiene como máximo un solo padre), y ningún nodo en el árbol apunta a la raíz. De hecho, cada nodo (que no sea la raíz) debe tener exactamente un padre y la raíz no debe tener padres.
De hecho, dada una lista de nodos, y para cada nodo una lista de referencias a sus hijos, no se puede saber si esta estructura es un árbol o no sin analizar su estructura global y que de hecho es topológicamente un árbol, como se define a continuación.
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:
con los axiomas:
En términos de teoría de tipos , un árbol es un tipo inductivo definido por los constructores nil (bosque vacío) y nodo (árbol con nodo raíz con valor e hijos dados).
Visto como un todo, una estructura de datos de árbol es un árbol ordenado , generalmente con valores adjuntos a cada nodo. Concretamente, es (si se requiere que no esté vacío):
Juntos con:
A menudo, los árboles tienen un factor de ramificación fijo (más correctamente, acotado) ( outdegree ), particularmente siempre con dos nodos secundarios (posiblemente vacíos, por lo tanto, como máximo, dos nodos secundarios no vacíos ), por lo tanto, un "árbol binario".
Permitir árboles vacíos hace que algunas definiciones sean más simples, otras más complicadas: un árbol enraizado 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 enraizado 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). Los conjuntos completos de operaciones en el árbol deben incluir la operación de bifurcación.
Matemáticamente, un árbol desordenado [3] (o "árbol algebraico") [4] se puede definir como una estructura algebraica ( X , padre) donde X es el conjunto de nodos portadores no vacíos y el padre es una función en X que asigna cada nodo x su nodo "padre", padre ( x ) . La estructura está sujeta a la condición de que toda subálgebra no vacía debe tener el mismo punto fijo . Es decir, debe haber un nodo "raíz" único r , tal que el padre ( r) = r y para cada nodo x , algún padre de aplicación iterativo (padre (⋯ padre ( x ) ⋯)) es igual a r .
Hay varias definiciones equivalentes.
Como alternativa más cercana, se pueden definir árboles desordenados como álgebras parciales ( X , padre) que se obtienen de las álgebras totales descritas anteriormente dejando que el padre ( r ) no esté definido. Es decir, la raíz r es el único nodo en el que la función padre no está definida y para cada nodo x , la raíz es accesible desde x en el gráfico dirigido ( X , padre) . De hecho, esta definición coincide con la de anti-arborescencia . El libro TAoCP usa el términoárbol orientado . [5]
Un árbol desordenado es una estructura ( X , ≺) donde X es un conjunto de nodos y ≺ es una relación de hijo a padre entre nodos de manera que: | |
(1) | X no está vacío. |
---|---|
(2) | X está débilmente conectado en ≺ . |
(3) | ≺ es funcional . |
(4) | ≺ satisface ACC : no hay secuencia infinita x 1 ≺ x 2 ≺ x 3 ≺ ⋯ . |
El cuadro de la derecha describe el álgebra parcial ( X , padre) como una estructura relacional ( X , ≺) . Si (1) se reemplaza por
entonces la condición (2) se vuelve redundante.
Con esta definición, se puede proporcionar terminología dedicada para generalizaciones de árboles desordenados que corresponden a subconjuntos distinguidos de las condiciones enumeradas:
Otra definición equivalente de un árbol desordenado es la de un árbol de teoría de conjuntos que tiene una sola raíz y cuya altura es como máximo ω (un árbol "finito"). [6] Es decir, las estructuras algebraicas ( X , padre) son equivalentes a órdenes parciales ( X , ≤) que tienen un elemento superior r y cuya alteración principal (también conocida como filtro principal ) es una cadena finita . Para ser precisos, deberíamos hablar de un árbol de teoría de conjuntos inverso ya que la definición de la teoría de conjuntos usualmente emplea un orden opuesto.
La correspondencia entre ( X , padre) y ( X , ≤) se establece mediante cierre / reducción transitiva reflexiva , con la reducción que da como resultado la versión "parcial" sin el ciclo raíz.
La definición de árboles en la teoría descriptiva de conjuntos (DST) utiliza la representación de órdenes parciales ( X , ≥) como órdenes de prefijo entre secuencias finitas. Resulta que hasta el isomorfismo , existe una correspondencia uno a uno entre los árboles DST (inverso de) y las estructuras de árbol definidas hasta ahora.
Podemos referirnos a las cuatro caracterizaciones equivalentes como árbol como álgebra , árbol como álgebra parcial , árbol como orden parcial y árbol como orden de prefijo . También hay una quinta definición equivalente: la de un árbol con raíces teóricas de grafos que es solo un grafo con raíces acíclicas conectadas .
La expresión de árboles como álgebras (parciales) (también llamadas gráficas funcionales ) ( X , padre) sigue directamente la implementación de estructuras de árbol usando punteros padre . Normalmente, se utiliza la versión parcial en la que el nodo raíz no tiene un padre definido. Sin embargo, en algunas implementaciones o modelos incluso se establece la circularidad padre ( r ) = r . Ejemplos notables:
de la programación orientada a objetos . En este caso, el nodo raíz es la metaclase superior , la única clase que es una instancia directa de sí misma.
Tenga en cuenta que la definición anterior admite árboles infinitos . Esto permite la descripción de estructuras infinitas soportadas por algunas implementaciones a través de la evaluación diferida . Un ejemplo notable es la regresión infinita de clases propias del modelo de objetos de Ruby . [11] En este modelo, el árbol establecido a través de superclass
enlaces entre objetos no terminales es infinito y tiene una rama infinita (una única rama infinita de objetos en "hélice" - ver el diagrama ).
En cada árbol desordenado ( X , padre) hay una partición distinguida del conjunto X de nodos en conjuntos hermanos . Dos nodos no raíz x , y pertenecen al mismo conjunto de hermanos si parent ( x ) = parent ( y ) . El nodo raíz r forma el conjunto hermano singleton { r }. [c] Se dice que un árbol es localmente finito o de ramificación finita si cada uno de sus conjuntos hermanos es finito.
Cada par de hermanos distintos es incomparable en ≤ . Por eso se utiliza la palabra desordenada en la definición. Tal terminología puede resultar engañosa cuando todos los conjuntos hermanos son singletons, es decir, cuando el conjunto X de todos los nodos está totalmente ordenado (y por lo tanto bien ordenado ) por ≤. En tal caso, podríamos hablar de un árbol de ramificación simple .
Al igual que con todo conjunto parcialmente ordenado, las estructuras de árbol ( X , ≤) se pueden representar por orden de inclusión , por sistemas de conjuntos en los que ≤ coincide con ⊆ , el orden de inclusión inducido . Considere una estructura ( U , ℱ) tal que U es un conjunto no vacío y ℱ es un conjunto de subconjuntos de U de manera que se satisfaga lo siguiente (según la definición de Colección de conjuntos anidados ):
A continuación, la estructura (ℱ, ⊆) es un árbol cuya raíz no ordenada es igual a T . Por el contrario, si ( U , ≤) es un árbol desordenado y ℱ es el conjunto {↓ x | x ∈ U } de todos los ideales principales de ( U , ≤) entonces el sistema de conjuntos ( U , ℱ) satisface las propiedades anteriores.
La vista de sistema de conjuntos de estructuras de árbol proporciona el modelo semántico predeterminado; en la mayoría de los casos más populares, las estructuras de datos de árbol representan la jerarquía de contención . Esto también ofrece una justificación para la dirección del pedido con la raíz en la parte superior: el nodo raíz es un contenedor más grande que cualquier otro nodo. Ejemplos notables:
Un árbol desordenado ( X , ≤) está bien fundado si el orden parcial estricto < es una relación bien fundada . En particular, todo árbol finito está bien fundado. Suponiendo el axioma de elección dependiente, un árbol está bien fundado si y solo si no tiene una rama infinita.
Los árboles bien fundados se pueden definir de forma recursiva , formando árboles a partir de una unión desarticulada de árboles más pequeños. Para una definición precisa, suponga que X es un conjunto de nodos. Uso de la reflexividad de órdenes parciales, podemos identificar cualquier árbol ( Y , ≤) en un subconjunto de X con su orden parcial (≤) - un subconjunto de X × X . El conjunto ℛ de todas las relaciones R que forman un árbol bien fundado ( Y , R ) en un subconjunto Y de X se define en etapas ℛyo , de modo que ℛ = ⋃ {ℛ i | i es ordinal }. Para cada número ordinal i , sea R pertenecer a la i -ésima etapa ℛ i si y solo si R es igual a
donde ℱ es un subconjunto de ⋃ {ℛ k | k < i } tal que los elementos de ℱ son disjuntos por pares, y x es un nodo que no pertenece a dom (⋃ℱ) . (Usamos dom ( S ) para denotar el dominio de una relación S. ) Observe que la etapa más baja ℛ 0 consiste en árboles de un solo nodo {( x , x )} ya que solo es posible ℱ vacío . En cada etapa, (posiblemente) nuevos árboles R se construyen tomando un bosque ⋃ℱcon componentes ℱ de etapas inferiores y uniendo una nueva raíz x encima de ⋃ℱ .
En contraste con la altura del árbol que es como máximo ω, el rango de árboles bien fundamentados es ilimitado, [13] vea las propiedades de " desplegarse ".
En informática, una forma común de definir árboles bien fundamentados es mediante pares ordenados recursivos ( F , x ) : un árbol es un bosque F junto con un nodo x "nuevo" . [14] Un bosque F, a su vez, es un conjunto de árboles posiblemente vacío con conjuntos de nodos separados por pares. Para la definición precisa, proceda de manera similar a como en la construcción de nombres usados en la técnica de forzamiento de la teoría de conjuntos. Sea X un conjunto de nodos. En la superestructura sobre X , defina los conjuntos T , ℱ de árboles y bosques, respectivamente, y un mapanodos: T → ℘ ( X ) asignando a cada árbol t su conjunto subyacente de nodos para que:
(árboles sobre X ) | t ∈ T | ↔ | t es un par ( F , x ) de ℱ × X de tal manera que para todos los s ∈ F , x ∉ nodos ( s ) , | |
(bosques sobre X ) | F ∈ ℱ | ↔ | F es un subconjunto de T tal que para cada s , t ∈ F , s ≠ t , nodos ( s ) ∩ nodos ( t ) = ∅ , | |
(nodos de árboles) | y ∈ nodos ( t ) | ↔ | t = ( F , x ) ∈ T y o bien y = x o Y ∈ nodos ( s ) para algunos s ∈ F . |
Las circularidades en las condiciones anteriores se pueden eliminar estratificando cada uno de T , ℱ y nodos en etapas como en la subsección anterior. Posteriormente, defina una relación de "subárbol" ≤ en T como el cierre transitivo reflexivo de la relación de "subárbol inmediato" ≺ definida entre árboles por
s ≺ t | ↔ | s ∈ π 1 ( t ) |
donde π 1 ( t ) es la proyección de t sobre la primera coordenada; es decir, es el bosque F tal que t = ( F , x ) para algunos x ∈ X . Se puede observar que ( T , ≤) es un árbol múltiple : para cada t ∈ T , el ideal principal ↓ t ordenado por ≤ es un árbol bien fundado como un orden parcial. Además, para cada árbol t ∈ T , su estructura de orden de "nodos" (nodos ( t ), ≤ t ) está dada por x ≤ t y si y solo si hay bosques F , G ∈ ℱ tales que tanto ( F , x ) como ( G , y ) son subárboles de t y ( F , x ) ≤ ( G , y ) .
Se puede obtener otra formalización, así como una generalización de árboles desordenados, reificando pares de nodos padre-hijo. Cada uno de estos pares ordenados puede considerarse como una entidad abstracta, una "flecha". Esto resulta en una multidigraph ( X , A , s , t ) donde X es el conjunto de nodos, A es el conjunto de flechas , y s y t son funciones de A a X asignación de cada flecha su fuente y de destino, respectivamente. La estructura está sujeta a las siguientes condiciones:
En (1), el símbolo de composición ○ debe interpretarse de izquierda a derecha. La condición dice que la consecutividad inversa de las flechas [d] es un mapa total de hijo a padre. Sea p este mapa padre entre flechas , es decir, p = s ○ t −1 . Entonces también tenemos s = p ○ t , por lo que un multidígrafo que satisfaga (1,2) también se puede axiomatizar como ( X , A , p , t ) , con el mapa padre p en lugar de scomo constituyente definitorio. Observe que la flecha de la raíz es necesariamente un bucle, es decir, su origen y destino coinciden.
Se establece una generalización importante de la estructura anterior al permitir que el mapa objetivo t sea de muchos a uno. Esto significa que (2) se debilita para
Tenga en cuenta que la condición (1) afirma que solo las flechas de hoja pueden tener el mismo objetivo. Es decir, la restricción de t al rango de p sigue siendo inyectiva .
Los multidígrafos que satisfacen (1,2 ') pueden denominarse "árboles de flechas": sus características de árbol se imponen sobre flechas en lugar de nodos. Estas estructuras pueden considerarse como la abstracción más esencial del VFS de Linux porque reflejan la estructura de enlace duro de los sistemas de archivos. Los nodos se llaman inodos , las flechas son dentries (o enlaces duros ). Los mapas padre y objetivo p y t están representados respectivamente por los campos d_parent
y d_inode
en la estructura de datos dentry. [15] A cada inodo se le asigna un tipo de archivo fijo, del cual el tipo de directorio juega un papel especial de "padres diseñados":
El uso de estilo discontinuo para la primera mitad del bucle raíz indica que, de manera similar al mapa principal, hay una versión parcial para el mapa fuente s en la que la fuente de la flecha raíz no está definida. Esta variante se emplea para una mayor generalización, consulte #Uso de rutas en un multidigrafo .
Despliegue de la pertenencia al conjunto ∈ . Para cada conjunto x , las estructuras relacionales ( x ∪ { x }, ∈) y ( TC ({ x }), ∈) son ambas apgs. [apg 1]
5 = 4 ∪ {4} = TC ({4}) = {0,1,2,3,4 } es un número ordinal de von Neumann .
Los árboles desordenados surgen naturalmente al "desplegar" gráficos puntiagudos accesibles . [dieciséis]
Sea ℛ = ( X , R , r ) una estructura relacional puntiaguda , es decir, tal que X es el conjunto de nodos, R es una relación entre nodos (un subconjunto de X × X ) y r es un nodo "raíz" distinguido . Suponga además que ℛ es accesible , lo que significa que X es igual a la preimagen de { r } bajo el cierre transitivo reflexivo de R , y llame a dicha estructura un grafo puntiagudo accesible o apgpara abreviar. [apg 2] Entonces se puede derivar otro apg ℛ '= ( X ' , R ' , r ' ) - el desarrollo de ℛ - como sigue:
Aparentemente, la estructura ( X ' , R ' ) es un árbol desordenado en la versión de "álgebra parcial": R ' es un mapa parcial que relaciona cada elemento que no es raíz de X ' con su padre mediante una ruta emergente. El elemento raíz es obviamente r ' . Además, se satisfacen las siguientes propiedades:
Notas:
Como se muestra en el ejemplo de estructura de enlace duro de sistemas de archivos, muchas estructuras de datos en informática permiten múltiples enlaces entre nodos. Por lo tanto, para exhibir correctamente la apariencia de árboles desordenados entre las estructuras de datos, es necesario generalizar los gráficos puntiagudos accesibles a la configuración multidigráfica . Para simplificar la terminología, utilizamos el término carcaj, que es un sinónimo establecido de "multidigraph".
Deje que un carcaj puntiagudo accesible o apq para abreviar se defina como una estructura
donde X es un conjunto de nodos , A es un conjunto de flechas , s es una función parcial de A a X (el mapa de origen ) y t es una función total de A a X (el mapa de destino ). Por tanto, ℳ es un "multidigráfico parcial".
La estructura está sujeta a las siguientes condiciones:
Se dice que ℳ es un árbol si el mapa objetivo t es una biyección entre flechas y nodos. El desarrollo de ℳ está formado por las secuencias mencionadas en (2), que son los caminos de accesibilidad (cf. Álgebra de caminos ). Como apq, el despliegue se puede escribir como ℳ '= ( X ' , A ' , s ' , t ' ) donde X' es el conjunto de rutas de accesibilidad, A ' coincide con X' , s ' coincide con la ruta emergente, y t 'es la identidad en X ' . Al igual que con apgs, el desdoblamiento es idempotente y siempre resulta en un árbol.
El apg subyacente se obtiene como la estructura ( X , R , t ( a r )) donde R = {( t ( a ), s ( a )) | a ∈ A \ { a r }} .
El diagrama de arriba muestra un ejemplo de un apq con 1 + 14 flechas. En JavaScript , Python o Ruby , la estructura se puede crear mediante el siguiente código (exactamente el mismo):
r = {}; r [ 1 ] = {}; r [ 2 ] = r [ 1 ]; r [ 3 ] = {}; r [ 4 ] = {}; r [ 1 ] [ 5 ] = {}; r [ 1 ] [ 14 ] = r [ 1 ] [ 5 ]; r [ 3 ] [ 7 ] = {}; r[ 3 ] [ 8 ] = r [ 3 ] [ 7 ]; r [ 3 ] [ 13 ] = {}; r [ 4 ] [ 9 ] = r [ 4 ]; r [ 4 ] [ 10 ] = r [ 4 ]; r [ 4 ] [ 11 ] = {}; r [ 3 ] [ 7 ] [ 6 ] = r[ 3 ]; r [ 3 ] [ 7 ] [ 12 ] = r [ 1 ] [ 5 ];
Los árboles desordenados y sus generalizaciones forman la esencia de los sistemas de nombres . Hay dos ejemplos destacados de sistemas de nombres: sistemas de archivos y matrices asociativas (anidadas) . Las estructuras basadas en múltiples gráficos de subsecciones anteriores proporcionaron abstracciones anónimas para ambos casos. Para obtener capacidades de nomenclatura, las flechas deben estar equipadas con nombres como identificadores . Un nombre debe ser localmente único - dentro de cada conjunto de flechas de hermanos [e] puede haber como máximo una flecha etiquetada con un nombre dado.
source | name | target |
---|---|---|
s ( a ) | σ ( a ) | t ( a ) |
Esto se puede formalizar como una estructura
donde X es un conjunto de nodos , Σ es un conjunto de nombres , A es un conjunto de flechas , s es una función parcial de A a X , σ es una función parcial de A a Σ y t es una función total de A a X . Para una flecha a , constituyentes de la triple ( s ( a ), σ ( a ), t ( a ))son, respectivamente, una 's fuente , nombre y objetivo .
La estructura está sujeta a las siguientes condiciones:
Esta estructura se puede llamar diccionario anidado o apq . En informática, estas estructuras son omnipresentes. La tabla anterior muestra que las flechas pueden considerarse "no reificadas" como el conjunto A ' = {( s ( a ), σ ( a ), t ( a )) | a ∈ A \ { a r }} de fuente-nombre-objetivo se triplica. Esto conduce a una estructura relacional ( X , Σ , A ' ) que puede verse como una base de datos relacionalmesa. Subraya source
e name
indica la clave principal .
La estructura puede reformularse como un sistema de transición etiquetado determinista : X es un conjunto de "estados", Σ es un conjunto de "etiquetas", A ' es un conjunto de "transiciones etiquetadas". (Además, el nodo raíz r = t ( a r ) es un "estado inicial", y la condición de accesibilidad significa que todos los estados son accesibles desde el estado inicial).
El diagrama de la derecha muestra un diccionario anidado ℰ que tiene el mismo multidígrafo subyacente que el ejemplo de la subsección anterior. La estructura se puede crear con el siguiente código. Como antes, se aplica exactamente el mismo código para JavaScript, Python y Ruby.
Primero, una subestructura , ℰ 0 , se crea mediante una única asignación de un literal {...}
a r
. Esta estructura, representada por líneas completas, es un " árbol de flechas " (por lo tanto, es un árbol de expansión ). El literal, a su vez, parece ser una serialización JSON de ℰ 0 .
Posteriormente, las flechas restantes se crean mediante asignaciones de nodos ya existentes. Las flechas que provocan ciclos se muestran en azul.
r = { "a" : { "a" : 5 , "b" : 5 }, "c" : { "a" : { "w" : 5 }, "c" : {}}, "d" : { "w" : 1.3 }}r [ "b" ] = r [ "a" ]; r [ "c" ] [ "b" ] = r [ "c" ] [ "a" ] r [ "c" ] [ "a" ] [ "p" ] = r [ "c" ]; r [ "d" ] [ "e" ] = r [ "d" ] [ "yo" ] = r [ "d"]
En Linux VFS, la función de nombre σ está representada por el d_name
campo en la estructura de datos dentry. [15] La estructura ℰ 0 anterior demuestra una correspondencia entre las estructuras representables en JSON y las estructuras de enlace duro de los sistemas de archivos. En ambos casos, hay un conjunto fijo de tipos integrados de "nodos" de los cuales un tipo es un tipo de contenedor, excepto que en JSON, de hecho, hay dos tipos de este tipo : Objeto y Matriz. Si se ignora el último (así como la distinción entre tipos de datos primitivos individuales), entonces las abstracciones proporcionadas de sistemas de archivos y datos JSON son las mismas: ambos son árboles de flechas equipados con nombres σ y una distinción de nodos contenedores.
Consulte # Datos anidados para obtener una descripción formal de las estructuras de árbol ("árboles JSON") con distinción y bipartición de nodos contenedores.
La función de nomenclatura σ de un diccionario anidado ℰ se extiende naturalmente desde las flechas hasta las rutas de las flechas. A cada secuencia p = [ a 1 , ..., a n ] de flechas consecutivas se le asigna implícitamente un nombre de ruta (cf. Pathname ) - la secuencia σ ( p ) = [ σ ( a 1 ), ..., σ ( a n )] de nombres de flechas. [F]La singularidad local se traslada a las rutas de las flechas: diferentes rutas de hermanos tienen diferentes nombres de ruta. En particular, las rutas de las flechas que se originan en la raíz están en correspondencia uno a uno con sus nombres de ruta. Esta correspondencia proporciona una representación "simbólica" del despliegue de ℰ a través de nombres de ruta; los nodos en ℰ se identifican globalmente a través de un árbol de nombres de ruta.
Las estructuras introducidas en la subsección anterior forman solo la parte central "jerárquica" de las estructuras de datos de árbol que aparecen en la informática. En la mayoría de los casos, también hay un orden "horizontal" adicional entre hermanos. En los árboles de búsqueda, el orden se establece comúnmente por la "clave" o el valor asociado con cada hermano, pero en muchos árboles ese no es el caso. Por ejemplo, los documentos XML, las listas dentro de los archivos JSON y muchas otras estructuras tienen un orden que no depende de los valores en los nodos, sino que son datos en sí mismos: ordenar los párrafos de una novela alfabéticamente cambiaría su significado.
La expansión correspondiente de las estructuras de árbol descritas anteriormente ( X , ≤) se puede definir dotando a cada conjunto hermano con un orden lineal de la siguiente manera. [17] [18]
En la siguiente subsección se presenta una definición alternativa según Kuboyama [3] .
Un árbol ordenado es una estructura ( X , ≤ V , ≤ S ) donde X es un conjunto no vacío de nodos y ≤ V y ≤ S son relaciones en X llamados v ertical (o también jerárquica [3] ) orden y s ibling orden, respectivamente. La estructura está sujeta a las siguientes condiciones:
Las condiciones (2) y (3) dicen que ( X , ≤ S ) es un orden lineal de componentes, cada componente es un conjunto hermano. La condición (4) afirma que si un conjunto hermano S es infinito, entonces ( S , ≤ S ) es isomorfo a ( , ≤) , el orden habitual de los números naturales.
Dado esto, hay tres (otros) órdenes parciales distinguidos que se dan únicamente por las siguientes prescripciones:
(< H ) | = | (≤ V ) ○ (< S ) ○ (≥ V ) | (la h orden orizontal ), |
(< L - ) | = | (> V ) ∪ (< H ) | (la "discordante" l inear orden ), |
(< L + ) | = | (< V ) ∪ (< H ) | (la "concordante" l inear orden ). |
Esto equivale a un sistema "VSHL ± " de cinco órdenes parciales ≤ V , ≤ S , ≤ H , ≤ L + , ≤ L - en el mismo conjunto X de nodos, en el cual, excepto para el par {≤ S , ≤ H }, dos relaciones cualesquiera determinan de forma única las otras tres, consulte la tabla de determinaciones .
Notas sobre convenciones de notación:
Esto produce seis versiones ≺, <, ≤, ≻,>, ≥ para una sola relación de orden parcial. A excepción de ≺ y ≻ , cada versión determina de forma única a las demás. Pasar de ≺ a < requiere que < sea transitivamente reducible. Esto siempre se cumple para todos los < V , < S y < H, pero puede que no sea válido para < L + o < L - si X es infinito.
Los órdenes parciales ≤ V y ≤ H son complementarios:
Como consecuencia, el orden lineal "concordante" < L + es una extensión lineal de < V . Del mismo modo, < L - es una extensión lineal de > V .
Las relaciones de cobertura ≺ L - y ≺ L + corresponden al recorrido previo al pedido y al recorrido posterior al pedido , respectivamente. Si x ≺ L - y entonces, según si y tiene un hermano anterior o no, el nodo x es el descendiente no estricto "más a la derecha" del hermano anterior de y o, en el último caso, x es el primer hijo de y . Los pares del último caso forman la relación (≺ L - ) ∖ (< H )que es un mapa parcial que asigna a cada nodo no hoja su primer nodo hijo . De manera similar, (≻ L + ) ∖ (> H ) asigna a cada nodo no hoja con un número finito de hijos su último nodo hijo.
La definición de Kuboyama de "árboles ordenados enraizados" [3] hace uso del orden horizontal ≤ H como relación definitoria. [g] (Ver también Suppes. [19] )
Utilizando la notación y la terminología introducidas hasta ahora, la definición se puede expresar de la siguiente manera.
Un árbol ordenado es una estructura ( X , ≤ V , ≤ H ) tal que se satisfacen las condiciones (1-5):
El orden de hermanos (≤ S ) se obtiene por (< S ) = (< H ) ∩ ((≺ V ) ○ (≻ V )) , es decir, dos nodos distintos están en orden de hermanos si y solo si están en orden horizontal y son hermanos.
La siguiente tabla muestra la determinación del sistema "VSHL ± ". Las expresiones relacionales en el cuerpo de la tabla son iguales a una de < V , < S , < H , < L - o < L + según la columna. De ello se deduce que, a excepción del par {≤ S , ≤ H }, un árbol ordenado ( X , ...) está determinado de forma única por dos cualesquiera de las cinco relaciones.
< V | < S | < H | < L - | < L + | |
---|---|---|---|---|---|
V, S | (≤ V ) ○ (< S ) ○ (≥ V ) | ||||
V, H | (< H ) ∩ ((≺ V ) ○ (≻ V )) | (> V ) ∪ (< H ) | (< V ) ∪ (< H ) | ||
V, L - | (< L - ) ∩ ((≺ V ) ○ (≻ V )) | (< L - ) ∖ (> V ) | |||
V, L + | (< L + ) ∩ ((≺ V ) ○ (≻ V )) | (< L + ) ∖ (< V ) | |||
H, L - | (> L - ) ∖ (< H ) | ||||
H, L + | (< L + ) ∖ (< H ) | ||||
L - , L + | (> L - ) ∩ (< L + ) | (< L - ) ∩ (< L + ) | |||
S, L - | x ≺ V y ↔ y = inf L - ( Y ) donde Y es la imagen de { x } debajo de (≥ S ) ○ (≻ L - ) | ||||
S, L + | x ≺ V y ↔ y = sup L + ( Y ) donde Y es la imagen de { x } bajo (≤ S ) ○ (≺ L + ) |
En las dos últimas filas, inf L - ( Y ) denota el mínimo de Y en ( X , ≤ L - ) , y sup L + ( Y ) denota el superior de Y en ( X , ≤ L + ) . En ambas filas, (≤ S ) resp. (≥ S ) puede ser reemplazado de manera equivalente por la equivalencia entre hermanos (≤ S ) ○ (≥S ) . En particular, la partición en conjuntos hermanos junto con ≤ L - o ≤ L + también es suficiente para determinar el árbol ordenado. La primera prescripción para ≺ V se puede leer como: el padre de un nodo no raíz x es igual al mínimo del conjunto de todos los predecesores inmediatos de los hermanos de x , donde las palabras "infimum" y "predecesores" se refieren a ≤ L - . De manera similar, con la segunda prescripción, simplemente use "supremum", "sucesores" y ≤ L + .
Las relaciones ≤ S y ≤ H obviamente no pueden formar un par definitorio. Para el ejemplo más simple, considere un árbol ordenado con exactamente dos nodos; entonces no se puede decir cuál de ellos es la raíz.
Eje XPath | Relación |
---|---|
ancestor | < V |
ancestor-or-self | ≤ V |
child | ≻ V |
descendant | > V |
descendant-or-self | ≥ V |
following | < H |
following-sibling | < S |
parent | ≺ V |
preceding | > H |
preceding-sibling | > S |
self | id X |
La tabla de la derecha muestra una correspondencia de las relaciones introducidas con los ejes XPath , que se utilizan en los sistemas de documentos estructurados para acceder a los nodos que tienen relaciones de ordenación particulares con un nodo de "contexto" inicial. Para un nodo de contexto [20] x , su eje nombrado por el especificador en la columna de la izquierda es el conjunto de nodos que es igual a la imagen de { x } bajo la relación correspondiente. A partir de XPath 2.0 , los nodos se "devuelven" en el orden del documento , que es el orden lineal "discordante" ≤ L - . Se lograría una "concordancia",si el orden vertical ≤V se definió de manera opuesta, con la dirección de abajo hacia arriba hacia afuera de la raíz como en la teoría de conjuntos de acuerdo con los árboles naturales. [h]
A continuación se muestra la lista de mapas parciales que se utilizan normalmente para el recorrido ordenado de árboles. [21] Cada mapa es una subrelación funcional distinguida de ≤ L - o de su opuesto.
Los mapas transversales constituyen un álgebra unaria parcial [22] ( X , parent, previousSibling, ..., nextNode) que forma una base para representar árboles como estructuras de datos vinculadas . Al menos conceptualmente, hay enlaces principales, enlaces de adyacencia hermanos y enlaces de primer / último hijo. Esto también se aplica a los árboles desordenados en general, que se pueden observar en la estructura de datos dentry en Linux VFS. [23]
De manera similar al sistema "VSHL ± " de órdenes parciales, existen pares de mapas transversales que determinan de manera única la estructura completa del árbol ordenado. Naturalmente, una de esas estructuras generadoras es ( X , ≺ V , ≺ S ) que se puede transcribir como ( X , parent, nextSibling) : la estructura de los enlaces de padres y hermanos siguientes. Otra estructura generadora importante es ( X , firstChild, nextSibling) conocida como árbol binario del hijo izquierdo del hermano derecho . Esta álgebra parcial establece una correspondencia uno a uno entre árboles binarios y árboles ordenados.
La correspondencia con árboles binarios proporciona una definición concisa de árboles ordenados como álgebras parciales.
Un árbol ordenado es una estructura donde X es un conjunto no vacío de nodos, y lc , rs son mapas parciales en X llamados l eft- c hild y r ight- s ibling , respectivamente. La estructura está sujeta a las siguientes condiciones:
La estructura de orden parcial ( X , ≤ V , ≤ S ) se obtiene de la siguiente manera:
(≺ S ) | = | ( rs ) , |
(≻ V ) | = | ( lc ) ○ (≤ S ) . |
Como una posible expansión del sistema "VSHL ± ", se pueden definir otras relaciones diferenciadas entre nodos, basadas en la estructura de niveles del árbol . En primer lugar, denotamos por ~ E la relación de equivalencia definida por x ~ E y si y sólo si x e y tienen el mismo número de antepasados. Esto produce una partición del conjunto de nodos en niveles L 0 , L 1 , ... (, L n ) - un grosor de la partición en conjuntos hermanos . Luego defina relaciones <E , < B - y < B + por
Se puede observar que < E es un orden parcial estricto y < B - y < B + son órdenes totales estrictos. Además, existe una similitud entre los sistemas "VSL ± " y "VEB ± ": < E es lineal por componentes y ortogonal a < V , < B - es la extensión lineal de < E y de > V , y < B + es una extensión lineal de < E y de < V .
Los árboles ordenados pueden codificarse naturalmente mediante secuencias finitas de números naturales. [24] [i] Denotar ⁎ el conjunto de todas las secuencias finitas de números naturales. Un subconjunto no vacío W de ⁎ se denomina dominio de árbol [25] [26] si para todo u , v de ⁎ y todo i , j de los siguientes valores ( ⁎ es el operador de concatenación ):
La estructura inducida en W da lugar a un árbol ordenado: tome el orden de prefijo para ≥ V y el orden lexicográfico para ≤ L - . [j]
Por el contrario, para un árbol ordenado T = ( X , ≤ V , ≤ L - ) asigne a cada nodo x la secuencia w ( x ) de índices hermanos, es decir, a la raíz se le asigna la secuencia vacía y para cada nodo no raíz x , sea w ( x ) = w (padre ( x )) ⁎ [ i ] donde i es el número de hermanos anteriores de x . Ponga W = { w ( x ) | x ∈ X} . Entonces W es un dominio de árbol con su estructura inducida isomorfo a T .
r = [[ 5 , 5 ], [[ 5 ], []], [[ 1.3 ]]] r [ 3 ] = r [ 0 ] r [ 1 ] [ 2 ] = r [ 1 ] [ 0 ] r [ 1 ] [ 0 ] [ 1 ] = r [ 1 ] r [ 2 ] [ 2 ] = r [ 2 ] [ 1 ] = r [ 2 ]
El orden de los hermanos se puede aplicar naturalmente a las generalizaciones de varios gráficos que se han introducido para árboles desordenados. Además, los índices de hermanos pueden verse como nombres especiales. Un dominio de árbol es solo un árbol de nombres de ruta . Como resultado, se obtiene una lista anidada como contraparte de un diccionario anidado .
El ejemplo que se muestra a la derecha proporciona una versión de lista anidada del diccionario anidado presentado anteriormente. Como antes, hay una estructura inicial (un árbol de flechas , representado por líneas completas) que se crea mediante una única asignación de un literal [...]
a r
. Posteriormente, la estructura se modifica mediante asignaciones que introducen enlaces adicionales.
El código es aplicable a JavaScript y Ruby. En Python, las asignaciones de modificación no están permitidas debido al uso de índices de hermanos que no están presentes en la estructura inicial. [k]
Las nociones de diccionario anidado y lista anidada (que son generalizaciones de árboles ordenados / desordenados, respectivamente) se pueden combinar en el concepto unificador de datos anidados . Estas estructuras son más populares en relación con el formato de datos JSON . Estas estructuras son multidigráficos con un conjunto distinguido de nodos contenedores, cada contenedor es un diccionario o una lista. En el texto a continuación, los conjuntos de diccionarios y listas se denotan respectivamente X O y X A . Esto es de acuerdo con la terminología JSON en la que los dos tipos de contenedores correspondientes se denominan Objeto y Matriz. El conjunto complementario de nodos no contenedores representa "valores primitivos". Formalizaciones específicas de JSON[27] [28] proporcionan un mayor refinamiento de acuerdo con los tipos de datos admitidos.
Los datos anidados se pueden formalizar como una estructura ℳ = ( X , Σ , A , X O , X A , s , t , σ , ι ) donde X es un conjunto de nodos , Σ es un conjunto de nombres , A es un conjunto de flechas , X O y X A son subconjuntos distinguidos de X , s es una función parcial de A a X(el mapa de origen ), t es una función total de A a X (el mapa de destino ), σ es una función parcial de A a Σ asignando su nombre a una flecha , y ι es una función parcial de A al conjunto de números naturales asignando a una flecha su índice de hermanos .
Sea ℳ un árbol de datos anidado si se cumplen las siguientes condiciones:
Tenga en cuenta en particular que (1) y (2) definen carcaj puntiagudos accesibles ( X , A , s , t ) . Condiciones (1-4) proporcionan axiomatization de árboles de flecha con la distinción de contenedores X O ∪ X A . Por (3) hay enlaces únicos a contenedores y por (4) los no contenedores deben ser nodos hoja (cf. condiciones (b) y (a) para enlaces físicos en sistemas de archivos). Una consecuencia importante de (1-4) es la condición de aciclicidad :
Esta condición proporciona una alternativa débil a (3).
Aunque los diccionarios tienen la semántica de colecciones desordenadas , en entornos de programación a menudo están equipados con algún orden intrínseco. Este orden es compatible con todos los de Python, Ruby y JavaScript. [l]
Por lo tanto, vale la pena considerar también los árboles de datos anidados ordenados , un refinamiento de los árboles de datos anidados en los que se ordenan todos los conjuntos hermanos. (La condición (7a) se modifica para permitir que ι ( a ) se defina para cada flecha que no sea raíz a .)
Al considerar solo subconjuntos particulares de las condiciones anteriores y / o constituyentes particulares de ℳ obtenemos una nomenclatura de estructuras de datos de árbol. Las aljabas puntiagudas accesibles ( X , A , s , t ) forman el "mínimo común denominador"; siempre se requieren las condiciones (1) y (2). Las condiciones (4–7) se imponen de manera apropiada a si se definen X O , X A , σ o ι .
La atribución de "árbol" se establece mediante la condición (3).
Exigir | Definir | Distinguir | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Singularidad (3) | Aciclicidad (3 ′) | Nombrar σ | Pedido ι | X O | X A | |||||||||||
Semántico | Total | |||||||||||||||
Carcaj puntiagudo accesible | ||||||||||||||||
Árbol desordenado | ||||||||||||||||
Árbol ordenado | ||||||||||||||||
Árbol de flechas con distinción de contenedores |
| |||||||||||||||
Diccionario anidado
| General | |||||||||||||||
Acíclico | ||||||||||||||||
Árbol | ||||||||||||||||
Ordenado | ||||||||||||||||
Lista anidada
| General | |||||||||||||||
Acíclico | ||||||||||||||||
Árbol | ||||||||||||||||
Datos anidados | General | |||||||||||||||
Acíclico | ||||||||||||||||
Árbol | ||||||||||||||||
Ordenado |
r = [[5,5],[[5,0],[],0],[[1.3],0,0],0]
|journal=
( ayuda )|journal=
( ayuda )|journal=
( ayuda )Wikimedia Commons tiene medios relacionados con estructuras de árboles . |