Estrutura da árvore - Tree structure
Uma estrutura de árvore , diagrama de árvore ou modelo de árvore é uma maneira de representar a natureza hierárquica de uma estrutura de forma gráfica. É chamada de "estrutura de árvore" porque a representação clássica lembra uma árvore , embora o gráfico geralmente esteja de cabeça para baixo em comparação com uma árvore biológica, com o "caule" na parte superior e as "folhas" na parte inferior.
Uma estrutura em árvore é conceitual e aparece em várias formas. Para obter uma discussão sobre estruturas de árvore em campos específicos, consulte Árvore (estrutura de dados) para ciência da computação; no que se refere à teoria dos grafos, consulte árvore (teoria dos grafos) ou árvore (teoria dos conjuntos) . Outros artigos relacionados estão listados abaixo.
Terminologia e propriedades
Os elementos da árvore são chamados de " nós ". As linhas que conectam os elementos são chamadas de "ramos". Os nós sem filhos são chamados de nós folha , "nós finais" ou "folhas".
Cada estrutura de árvore finita tem um membro que não tem superior . Esse membro é chamado de "raiz" ou nó raiz . A raiz é o nó inicial. Mas o inverso não é verdadeiro: estruturas de árvore infinitas podem ou não ter um nó raiz.
Os nomes das relações entre os nós modelam a terminologia de parentesco das relações familiares. Os nomes neutros de gênero "pai" e "filho" substituíram amplamente a terminologia mais antiga de "pai" e "filho". O termo "tio" ainda é amplamente usado para outros nós no mesmo nível do pai, embora às vezes seja substituído por termos de gênero neutro como "ommer".
- O "pai" de um nó é um nó um degrau acima na hierarquia (ou seja, mais perto do nó raiz) e situado no mesmo galho.
- Os nós "irmãos" ("irmão" ou "irmã") compartilham o mesmo nó pai.
- Os "tios" de um nó (às vezes "ommers") são irmãos do pai desse nó.
- Um nó que está conectado a todos os nós de nível inferior é chamado de "ancestral". Os nós de nível inferior conectados são "descendentes" do nó ancestral.
No exemplo, "enciclopédia" é o pai de "ciência" e "cultura", seus filhos. "Arte" e "artesanato" são irmãos e filhos da "cultura", que é seu pai e, portanto, um de seus ancestrais. Além disso, "enciclopédia", como a raiz da árvore, é o ancestral da "ciência", "cultura", "arte" e "artesanato". Finalmente, "ciência", "arte" e "artesanato", como folhas, não são ancestrais de nenhum outro nó.
Estruturas de árvores podem representar todos os tipos de conhecimento taxonômico , como árvores genealógicas , a árvore evolutiva biológica , a árvore evolutiva de uma família de línguas , a estrutura gramatical de uma língua (um exemplo-chave é S → NP VP, o que significa que uma frase é um substantivo frase e uma frase verbal, cada um tendo, por sua vez, outros componentes que têm outros componentes), a maneira como as páginas da web são ordenadas logicamente em um site da web, árvores matemáticas de conjuntos de inteiros etc.
Os Dicionário de Inglês Oxford registros de uso de ambos os termos "estrutura de árvore" e "árvore-diagrama" de 1965 em Noam Chomsky 's Aspectos da Teoria da Sintaxe .
Em uma estrutura em árvore, há um e apenas um caminho de qualquer ponto a qualquer outro ponto.
A ciência da computação usa estruturas de árvore extensivamente ( ver Árvore (estrutura de dados) e telecomunicações .)
Para obter uma definição formal, consulte a teoria dos conjuntos e, para uma generalização na qual os filhos não são necessariamente sucessores, consulte a ordem dos prefixos .
Exemplos de estruturas de árvore
- Internet:
- Tubos a vácuo
- Estrutura lógica do Document Object Model , Yahoo! índice de assuntos, Curlie
- Sistema operacional : estrutura de diretório
- Gerenciamento de informações: sistema decimal de Dewey , PSH , esta lista hierárquica com marcadores
- Gestão: estruturas organizacionais hierárquicas
- Ciência da Computação:
- Biologia: árvore evolutiva
- Negócio: esquema de venda em pirâmide
- Gestão de projetos: estrutura analítica do trabalho
- Linguística:
- (Sintaxe) Árvores de estrutura de frase
- (Lingüística histórica) Modelo em árvore da mudança de linguagem
- Esportes: xadrez de negócios , chaves dos playoffs
- Matemática: universo de Von Neumann
- Teoria do grupo: árvores descendentes
Representando árvores
Existem muitas maneiras de representar visualmente estruturas em árvore. Quase sempre, eles se resumem a variações ou combinações de alguns estilos básicos:
Diagramas de ligação de nó clássicos
Diagramas de ligação de nó clássicos, que conectam nós com segmentos de linha:
enciclopédia | ||
---|---|---|
/ cultura |
\ ciência |
|
/ art |
\ craft |
Conjuntos aninhados
Conjuntos aninhados que usam invólucro / contenção para mostrar a paternidade, os exemplos incluem TreeMaps e mapas fractais :
Diagramas de "gelo" em camadas
Diagramas de "gelo" em camadas que usam alinhamento / adjacência.
enciclopédia | ||
---|---|---|
cultura | Ciência | |
arte | artesanato |
Contornos e visualizações em árvore
Listas ou diagramas que usam indentação, às vezes chamados de " contornos " ou " visualizações em árvore ".
Um esboço:
-
enciclopédia
-
cultura
- arte
- artesanato
- Ciência
-
cultura
Uma visualização em árvore:
-
enciclopédia
-
cultura
- arte
- artesanato
- Ciência
-
cultura
Parênteses aninhados
Uma correspondência entre parênteses aninhados foi notada pela primeira vez por Sir Arthur Cayley :
((arte, artesanato) cultura, ciência) enciclopédia
ou
enciclopédia (cultura (arte, artesanato), ciência)
Arvores radiais
As árvores também podem ser representadas radialmente :
arte \ |
ofício / |
---|---|
cultura | |
|
enciclopédia | |
| Ciência |
Veja também
- Tipos de árvores
- Árvore B
- Árvore dançante
- Árvore de decisão
- Árvore binária filho esquerdo irmão direito
- Árvore (estrutura de dados)
- Árvore (teoria dos grafos)
- Árvore (teoria dos conjuntos)
- Artigos relacionados
Referências
- ^ "Glossário Ethereum" . GitHub . Página visitada em 17 de abril de 2019 .
- ^ "árvore" . Oxford English Dictionary (ed. Online). Imprensa da Universidade de Oxford. (É necessária uma assinatura ou associação a uma instituição participante .)
- ^ "O que é o modelo de objeto de documento?" . Domínio da arquitetura W3C . Página visitada em 2006-12-05 .
Leitura adicional
A identificação de alguns dos estilos básicos de estruturas em árvore pode ser encontrada em:
- Jacques Bertin , Semiology of Graphics , 1983, University of Wisconsin Press (2ª edição 1973, ISBN 978-0299090609 ;
- Donald E. Knuth , The Art of Computer Programming , Volume I: Fundamental Algorithms, 1968, Addison-Wesley, pp. 309-310;
- Brian Johnson e Ben Shneiderman , Tree-maps: A space -illing approach to the visualization of hierarchical information structure , in Proceedings of IEEE Visualization (VIS), 1991, pp. 284-291, ISBN 0-8186-2245-8 ;
- Peter Eades , Tao Lin e Xuemin Lin, Two Tree Drawing Conventions , International Journal of Computational Geometry and Applications, 1993, volume 3, número 2, pp. 133-153.
- Manuel Lima , The Book of Trees: Visualizing Branches of Knowledge (2014), Princeton Architectural Press , ISBN 978-1-616-89218-0