Arborescence - Tree structure

Une arborescence montrant l'organisation hiérarchique possible d'une encyclopédie
L' Encyclopédie originale utilisait un diagramme en arbre pour montrer la façon dont ses sujets étaient ordonnés.

Une structure arborescente , un diagramme arborescent ou un modèle arborescent est un moyen de représenter la nature hiérarchique d'une structure sous une forme graphique. On l'appelle une "structure arborescente" car la représentation classique ressemble à un arbre , bien que le graphique soit généralement à l'envers par rapport à un arbre biologique, avec la "tige" en haut et les "feuilles" en bas.

Une arborescence est conceptuelle et se présente sous plusieurs formes. Pour une discussion sur les structures arborescentes dans des domaines spécifiques, voir Arbre (structure de données) pour l'informatique ; en ce qui concerne la théorie des graphes, voir arbre (théorie des graphes) ou arbre (théorie des ensembles) . D'autres articles connexes sont énumérés ci-dessous.

Terminologie et propriétés

Les éléments de l'arbre sont appelés « nœuds ». Les lignes reliant les éléments sont appelées "branches". Les nœuds sans enfants sont appelés nœuds feuilles , « nœuds terminaux » ou « feuilles ».

Chaque structure arborescente finie a un membre qui n'a pas de supérieur . Ce membre est appelé « racine » ou nœud racine . La racine est le nœud de départ. Mais l'inverse n'est pas vrai : les structures arborescentes infinies peuvent avoir ou non un nœud racine.

Les noms des relations entre les nœuds modélisent la terminologie de parenté des relations familiales. Les noms non sexistes « parent » et « enfant » ont largement remplacé la terminologie plus ancienne « père » et « fils ». Le terme « oncle » est encore largement utilisé pour d'autres nœuds au même niveau que le parent, bien qu'il soit parfois remplacé par des termes non sexistes comme « ommer ».

  • Le "parent" d'un nœud est un nœud un échelon plus haut dans la hiérarchie (c'est-à-dire plus proche du nœud racine) et se trouvant sur la même branche.
  • Les nœuds « frères » (« frère » ou « soeur ») partagent le même nœud parent.
  • Les "oncles" d'un nœud (parfois "ommers") sont les frères et sœurs du parent de ce nœud.
  • Un nœud qui est connecté à tous les nœuds de niveau inférieur est appelé un "ancêtre". Les nœuds de niveau inférieur connectés sont des "descendants" du nœud ancêtre.

Dans l'exemple, "encyclopédie" est le parent de "science" et "culture", ses enfants. "Art" et "artisanat" sont frères et sœurs, et enfants de "culture", qui est leur parent et donc l'un de leurs ancêtres. Aussi, "l'encyclopédie", en tant que racine de l'arbre, est l'ancêtre de "science", "culture", "art" et "artisanat". Enfin, "science", "art" et "artisanat", en tant que feuilles, ne sont les ancêtres d'aucun autre nœud.

Les structures arborescentes peuvent représenter toutes sortes de connaissances taxonomiques , telles que les arbres généalogiques , l' arbre évolutif biologique , l' arbre évolutif d'une famille linguistique , la structure grammaticale d'une langue (un exemple clé étant S → NP VP, ce qui signifie qu'une phrase est un nom phrase et une phrase verbale, chacune ayant à son tour d'autres composants qui ont d'autres composants), la façon dont les pages Web sont logiquement ordonnées dans un site Web, les arbres mathématiques d'ensembles d'entiers , et cetera.

Les Oxford English Dictionary records utilisation des deux termes « structure arborescente » et « arbre-diagramme » de 1965 à Noam Chomsky l » Aspects de la théorie de la syntaxe .

Dans une structure arborescente, il n'y a qu'un et un seul chemin de n'importe quel point à n'importe quel autre point.

L'informatique utilise abondamment les structures arborescentes ( voir Arbre (structure de données) et télécommunications .)

Pour une définition formelle, voir la théorie des ensembles et pour une généralisation dans laquelle les enfants ne sont pas nécessairement des successeurs, voir l' ordre des préfixes .

Exemples d'arborescences

Une arborescence utilisée pour représenter une structure de répertoires comme un ensemble imbriqué
schéma d'information en forme d'arbre illustrant "l'évolution" des tubes thermoioniques (sorte de tube à vide) entre 1883 et 1934

Représenter des arbres

Il existe de nombreuses façons de représenter visuellement des structures arborescentes. Presque toujours, cela se résume à des variations ou à des combinaisons de quelques styles de base :

Diagrammes nœuds-liens classiques

Diagrammes nœuds-liens classiques, qui relient les nœuds avec des segments de ligne :

encyclopédie
/
culturel
\
sciences
/
art
\
artisanat

Ensembles imbriqués

Ensembles imbriqués qui utilisent l'enceinte/confinement pour montrer la parentalité, les exemples incluent les TreeMaps et les cartes fractales :

Vide.png encyclopédie
Vide.png Vide.png
Vide.png culture
Vide.png Vide.png
artisanat d'art
science 

Diagrammes « glaçons » en couches

Diagrammes « glaçons » en couches qui utilisent l'alignement/la contiguïté.

encyclopédie
culture science
de l'art artisanat

Contours et arborescences

Listes ou diagrammes utilisant l'indentation, parfois appelés « contours » ou « vues arborescentes ».

Un contour:

encyclopédie
culture
de l'art
artisanat
science

Une vue arborescente :

  • encyclopédie
    • culture
      • de l'art
      • artisanat
    • science

Parenthèses imbriquées

Une correspondance avec des parenthèses imbriquées a d'abord été remarquée par Sir Arthur Cayley :

((art,artisanat)culture,science)encyclopédie
ou
encyclopédie(culture(art,artisanat),science)

Arbres radiaux

Les arbres peuvent aussi être représentés radialement :

art
      \
artisanat
/    
culturel
|
encyclopédie
|
science

Voir également

Types d'arbres
Articles Liés

Les références

  1. ^ " Glossaire Ethereum " . GitHub . Consulté le 17 avril 2019 .
  2. ^ "arbre" . Dictionnaire anglais d'Oxford (le rédacteur en ligne). Presses de l'Université d'Oxford.  (Abonnement ou adhésion à une institution participante requis.)
  3. ^ "Qu'est-ce que le modèle d'objet de document ?" . Domaine de l'architecture W3C . Récupéré le 2006-12-05 .

Lectures complémentaires

L'identification de certains des styles de base des structures arborescentes peut être trouvée dans :

Liens externes