Estructura de árbol
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 denomina "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 el fondo.
Una estructura de árbol es conceptual y aparece en varias formas. Para obtener una discusión sobre las estructuras de árbol en campos específicos, consulte Árbol (estructura de datos) para informática; en lo que se refiere a la teoría de grafos, véase á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 llaman "nodos". Las líneas que conectan los elementos se denominan "ramas". Los nodos sin hijos se denominan nodos hoja, "nodos finales" u "hojas".
Cada estructura de árbol finito tiene un miembro que no tiene superior. Este miembro se denomina "raíz" o nodo raíz. La raíz es el nodo inicial. Pero lo contrario no es cierto: infinitas estructuras de árboles pueden o no tener un nodo raíz.
Los nombres de las relaciones entre nodos modelan la terminología de parentesco de las relaciones familiares. Los nombres neutros en cuanto al género "parent" y "niño" han desplazado en gran medida al viejo "padre" y "hijo" terminología. 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 de género neutral como "ommer".
- El "padre" de un nodo es un paso más alto en la jerarquía (es decir, más cerca del nodo raíz) y acostado en la misma rama.
- Los nodos "hermano" ("hermano") comparten el mismo nodo padre.
- Los "uncles" 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 llama "ancestor". Los ganglios de nivel inferior conectados son "descendientes" del nodo del ancestro.
En el ejemplo, "enciclopedia" es el padre de la "ciencia" y "cultura", sus hijos. "Arte" y "artesanía" son hermanos e hijos de la "cultura", que es su padre y, por lo tanto, uno de sus antepasados. Además, la "enciclopedia", como la raíz del árbol, es el antepasado de la "ciencia", la "cultura", el "arte" y "artesanía". Finalmente, "ciencia", "arte" y "artesanía", como las hojas, no son ancestros de ningún otro nodo.
Las estructuras de árbol pueden representar todo tipo de conocimiento taxonómico, como árboles genealógicos, el árbol evolutivo biológico, el árbol evolutivo de una familia lingüística, la estructura gramatical de un idioma (un ejemplo clave es S → NP VP, que significa una oración es un sintagma nominal y un sintagma verbal, cada uno de los cuales tiene a su vez 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.
El Oxford English Dictionary registra el uso de los términos "estructura de árbol" y "diagrama de árbol" de 1965 en Aspects of the Theory of Syntax de Noam Chomsky.
En una estructura de árbol hay una y sólo una ruta de cualquier punto a cualquier otro punto.
Las ciencias de la computación usan estructuras de árbol ampliamente (ver Á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 los prefijos.
Ejemplos de estructuras de árbol
- Internet:
- jerarquía de usonet
- Tubos de vacío
- Document Object Estructura lógica del modelo, índice de sujeto Yahoo!, Curlie
- Sistema operativo: estructura del directorio
- Gestión de la información: Dewey Decimal System, PSH, esta lista jerárquica de balas
- Gestión: estructuras organizativas jerárquicas
- Computer Science:
- árbol de búsqueda binaria
- Árbol rojo-negro
- Árbol AVL
- R-tree
- Biología: árbol evolutivo
- Negocios: esquema de venta de pirámide
- Gestión del proyecto: estructura de desglose del trabajo
- Lingüística:
- (Sintaxis)
- (Línguística histórica) Modelo de árbol del cambio de idioma
- Deportes: ajedrez de negocios, soportes de playoffs
- Matemáticas: universo Von Neumann
- Teoría del grupo: árboles descendientes
Representación de árboles
Hay muchas formas de representar visualmente las estructuras de árbol. 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 usan recinto/contención para mostrar la paternidad, los ejemplos incluyen TreeMaps, mapas fractales y diagramas de Euler:
"carámbano" en capas diagramas
"carámbano" en capas diagramas que usan alineación/adyacencia.
enciclopedia | ||
---|---|---|
cultura | ciencia | |
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
- ciencia
- cultura
Una vista de árbol:
- enciclopedia
- cultura
- arte
- artesanía
- ciencia
- cultura
Paréntesis anidados
Sir Arthur Cayley notó por primera vez una correspondencia entre paréntesis anidados:
(arte, artesanía)cultura, ciencia)
o
enciclopedia(cultura(arte, artesanía), ciencia)
Árboles radiales
Los árboles también se pueden representar radialmente:
arte | artesanía / |
---|---|
cultura Silencio | |
enciclopedia | |
Silencio ciencia |
Contenido relacionado
Ultima Online
Programación lógica inductiva
SHA-1