Estructura de árbol - Tree structure

Una estructura de árbol que muestra la posible organización jerárquica de una enciclopedia.
La Encyclopédie original usó un diagrama de árbol para mostrar la forma en que se ordenaron sus temas.

Una estructura de árbol , diagrama de árbol o modelo de árbol es una forma de representar la naturaleza jerárquica de una estructura en forma gráfica. Se le llama "estructura de árbol" porque la representación clásica se asemeja a un árbol , aunque el gráfico generalmente está al revés en comparación con un árbol biológico, con el "tallo" en la parte superior y las "hojas" en la parte inferior.

Una estructura de árbol es conceptual y aparece en varias formas. Para obtener más información sobre las estructuras de árbol en campos específicos, consulte Árbol (estructura de datos) para informática; en la medida en que se relacione con la teoría de grafos, consulte árbol (teoría de grafos) o árbol (teoría de conjuntos) . Otros artículos relacionados se enumeran a continuación.

Terminología y propiedades

Los elementos del árbol se denominan " nodos ". Las líneas que conectan elementos se denominan "ramas". Los nodos sin hijos se denominan nodos hoja , "nodos finales" u "hojas".

Cada estructura de árbol finita tiene un miembro que no tiene superior . Este miembro se llama "raíz" o nodo raíz . La raíz es el nodo inicial. Pero lo contrario no es cierto: las estructuras de árbol infinitas pueden tener o no un nodo raíz.

Los nombres de las relaciones entre los nodos modelan la terminología de parentesco de las relaciones familiares. Los nombres de género neutro "padre" e "hijo" han desplazado en gran medida la terminología más antigua de "padre" e "hijo". El término "tío" todavía se usa ampliamente para otros nodos al mismo nivel que el padre, aunque a veces se reemplaza con términos neutrales al género como "ommer".

  • El "padre" de un nodo es un nodo un paso más arriba en la jerarquía (es decir, más cerca del nodo raíz) y que se encuentra en la misma rama.
  • Los nodos "hermanos" ("hermano" o "hermana") comparten el mismo nodo principal.
  • Los "tíos" de un nodo (a veces "ommers") son hermanos del padre de ese nodo.
  • Un nodo que está conectado a todos los nodos de nivel inferior se denomina "antepasado". Los nodos de nivel inferior conectados son "descendientes" del nodo antepasado.

En el ejemplo, "enciclopedia" es el padre de "ciencia" y "cultura", sus hijos. "Arte" y "artesanía" son hermanos e hijos de la "cultura", que es su progenitor y, por tanto, uno de sus antepasados. Además, la "enciclopedia", como raíz del árbol, es el antepasado de la "ciencia", la "cultura", el "arte" y la "artesanía". Finalmente, "ciencia", "arte" y "artesanía", como hojas, no son antepasados ​​de ningún otro nodo.

Las estructuras de árbol pueden representar todo tipo de conocimiento taxonómico , como los árboles genealógicos , el árbol evolutivo biológico , el árbol evolutivo de una familia de lenguas , la estructura gramatical de una lengua (un ejemplo clave es S → NP VP, es decir, una oración es un sustantivo frase y una frase verbal, cada una a su vez con otros componentes que tienen otros componentes), la forma en que las páginas web están ordenadas lógicamente en un sitio web, árboles matemáticos de conjuntos de números enteros , etcétera.

Los Diccionario Oxford de Inglés registros de uso tanto de los términos "estructura de árbol" y "diagrama de árbol" de 1965 en Noam Chomsky 's Aspectos de la teoría de la sintaxis .

En una estructura de árbol hay una y solo una ruta desde cualquier punto a cualquier otro punto.

Las ciencias de la computación utilizan ampliamente las estructuras de árbol ( consulte Árbol (estructura de datos) y telecomunicaciones ).

Para una definición formal, consulte la teoría de conjuntos , y para una generalización en la que los niños no son necesariamente sucesores, consulte el orden de prefijos .

Ejemplos de estructuras de árboles

Un mapa de árbol utilizado para representar una estructura de directorio como un conjunto anidado
diagrama de información en forma de árbol que ilustra la "evolución" de los tubos termoiónicos (un tipo de tubo de vacío) entre 1883 y 1934

Representando árboles

Hay muchas formas de representar visualmente las estructuras de los árboles. Casi siempre, estos se reducen a variaciones o combinaciones de algunos estilos básicos:

Diagramas de enlace de nodo clásicos

Diagramas de enlace de nodo clásicos, que conectan nodos con segmentos de línea:

enciclopedia
/
cultura
\
ciencia
/
arte
\
artesanía

Conjuntos anidados

Conjuntos anidados que utilizan encierro / contención para mostrar la paternidad, los ejemplos incluyen TreeMaps y mapas fractales :

Blank.png enciclopedia
Blank.png Blank.png
Blank.png cultura
Blank.png Blank.png
oficio del arte
Ciencias 

Diagramas de "carámbanos" en capas

Diagramas de "carámbano" en capas que utilizan alineación / adyacencia.

enciclopedia
cultura Ciencias
Arte artesanía

Contornos y vistas de árbol

Listas o diagramas que usan sangría, a veces llamados " esquemas " o " vistas de árbol ".

Un esquema:

enciclopedia
cultura
Arte
artesanía
Ciencias

Una vista de árbol:

  • enciclopedia
    • cultura
      • Arte
      • artesanía
    • Ciencias

Paréntesis anidados

Sir Arthur Cayley notó por primera vez una correspondencia entre paréntesis anidados :

((arte, artesanía) cultura, ciencia) enciclopedia
o
enciclopedia (cultura (arte, artesanía), ciencia)

Árboles radiales

Los árboles también se pueden representar radialmente :

arte
      \
artesanía
/    
cultura
|
enciclopedia
|
Ciencias

Ver también

Tipos de arboles
Artículos relacionados

Referencias

  1. ^ "Glosario de Ethereum" . GitHub . Consultado el 17 de abril de 2019 .
  2. ^ "árbol" . Diccionario de inglés de Oxford (edición en línea). Prensa de la Universidad de Oxford.  (Se requiere suscripción o membresía en una institución participante ).
  3. ^ "¿Qué es el modelo de objetos de documento?" . Dominio de Arquitectura W3C . Consultado el 5 de diciembre de 2006 .

Otras lecturas

La identificación de algunos de los estilos básicos de estructuras de árboles se puede encontrar en:

enlaces externos