Estructura de árbol - Tree structure
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
- Internet:
- Tubos de vacio
- La estructura lógica del Document Object Model , Yahoo! índice de materias, Curlie
- Sistema operativo : estructura de directorios
- Gestión de la información: Dewey Decimal System , PSH , esta lista jerárquica con viñetas
- Gestión: estructuras organizativas jerárquicas
- Ciencias de la Computación:
- Biología: árbol evolutivo
- Negocio: esquema de venta piramidal
- Gestión de proyectos: estructura de desglose del trabajo
- Lingüística:
- (Sintaxis) Árboles de estructura de frases
- (Lingüística histórica) Modelo de árbol del cambio de idioma
- Deportes: ajedrez de negocios , tramos de playoffs
- Matemáticas: universo de Von Neumann
- Teoría de grupos: árboles descendientes
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 :
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
-
cultura
Una vista de árbol:
-
enciclopedia
-
cultura
- Arte
- artesanía
- Ciencias
-
cultura
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
- Árbol B
- Árbol bailando
- Árbol de decisión
- Árbol binario del hermano derecho del hijo izquierdo
- Árbol (estructura de datos)
- Árbol (teoría de grafos)
- Árbol (teoría de conjuntos)
- Artículos relacionados
Referencias
- ^ "Glosario de Ethereum" . GitHub . Consultado el 17 de abril de 2019 .
- ^ "á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 ).
- ^ "¿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:
- Jacques Bertin , Semiology of Graphics , 1983, University of Wisconsin Press (2da edición 1973, ISBN 978-0299090609 ;
- Donald E. Knuth , El arte de la programación informática , Volumen I: Algoritmos fundamentales, 1968, Addison-Wesley, págs. 309-310;
- Brian Johnson y Ben Shneiderman , Mapas de árboles: Un enfoque que llena el espacio para la visualización de estructuras de información jerárquica , en Proceedings of IEEE Visualization (VIS), 1991, págs. 284-291, ISBN 0-8186-2245-8 ;
- Peter Eades , Tao Lin y Xuemin Lin, dos convenciones de dibujo de árboles , Revista Internacional de Geometría y Aplicaciones Computacionales, 1993, volumen 3, número 2, págs. 133-153.
- Manuel Lima , El libro de los árboles: Visualizando ramas del conocimiento (2014), Princeton Architectural Press , ISBN 978-1-616-89218-0