Worldlex Wiki En informatique , un arbre est un type de données abstrait largement utilisé qui représente une structure arborescente hiérarchique composée d'un ensemble de nœuds connectés . Chaque nœud de l'arbre peut être connecté à plusieurs enfants (selon le type d'arbre), mais doit être connecté à un seul parent à l'exception du nœud racine , qui n'a pas de parent (c'est-à-dire le nœud le plus haut dans la hiérarchie). Ces contraintes impliquent l'absence de cycles ou de boucles (aucun nœud ne peut être son propre ancêtre), et permettent également de traiter chaque enfant comme le nœud racine de son propre sous-arbre, ce qui rend la récursivité utile pour le parcours d'arbres . Contrairement aux structures de données linéaires , de nombreux arbres ne peuvent pas être représentés par des relations entre nœuds voisins (nœuds parents et enfants d'un nœud considéré, s'ils existent) sur une seule ligne droite (appelée arête ou lien entre deux nœuds adjacents).
Les arbres binaires sont un type de données couramment utilisé, qui limite à deux le nombre d'enfants de chaque parent. Lorsque l'ordre des enfants est spécifié, cette structure de données correspond à un arbre ordonné en théorie des graphes . Une valeur ou un pointeur vers d'autres données peut être associé à chaque nœud de l'arbre, ou parfois seulement aux feuilles , qui n'ont pas d'enfants.
Le type de données abstrait (TDA) peut être représenté de différentes manières : par exemple, une liste de parents avec des pointeurs vers leurs enfants, une liste d’enfants avec des pointeurs vers leurs parents, ou encore une liste de nœuds et une liste distincte de relations parent-enfant (un type particulier de liste d’adjacence ). Les représentations peuvent également être plus complexes, par exemple en utilisant des index ou des listes d’ancêtres pour optimiser les performances.
Les arbres utilisés en informatique sont similaires, mais peuvent différer, des constructions mathématiques que sont les arbres en théorie des graphes , les arbres en théorie des ensembles et les arbres en théorie descriptive des ensembles .
nœud est une structure pouvant contenir des données et des connexions à d'autres nœuds, parfois appelées arêtes ou liens . Chaque nœud d'un arbre possède zéro ou plusieurs nœuds enfants , situés en dessous de lui dans l'arbre (par convention, les arbres sont représentés avec les descendants orientés vers le bas). Un nœud ayant un enfant est appelé le nœud parent (ou supérieur ) de cet enfant. Tous les nœuds ont exactement un parent, à l'exception du nœud racine , le plus haut , qui n'en a pas. Un nœud peut avoir plusieurs ancêtres , comme le parent de son parent. Les nœuds enfants ayant le même parent sont des nœuds frères . Généralement, les frères sont ordonnés, le premier étant conventionnellement représenté à gauche. Certaines définitions autorisent un arbre à ne contenir aucun nœud ; on dit alors qu'il est vide .Élagage : Suppression d'une partie entière d'un arbreMéthodes de parcours et de recherche
Représentations
Il existe de nombreuses façons de représenter les arbres. En mémoire vive, les nœuds sont généralement des enregistrements alloués dynamiquement, contenant des pointeurs vers leurs enfants, leurs parents, ou les deux, ainsi que vers les données associées. Si leur taille est fixe, les nœuds peuvent être stockés dans une liste. Les nœuds et leurs relations peuvent être stockés dans un type spécifique de liste d'adjacence . Dans les bases de données relationnelles , les nœuds sont généralement représentés par des lignes de table, dont les identifiants indexés permettent d'établir des liens entre les parents et les enfants.
Les nœuds peuvent également être stockés comme éléments d'un tableau , les relations entre eux étant déterminées par leurs positions dans le tableau (comme dans un tas binaire ).
Un arbre binaire peut être implémenté comme une liste de listes : la tête de liste (la valeur du premier terme) est le sous-arbre gauche, tandis que la queue (la liste des termes suivants) est le sous-arbre droit. Cette représentation peut être modifiée pour inclure également des valeurs, comme dans les expressions S de Lisp , où la tête (la valeur du premier terme) est la valeur du nœud, la tête de la queue (la valeur du deuxième terme) est le sous-arbre gauche, et la queue de la queue (la liste des termes suivants) est le sous-arbre droit.
Les arbres ordonnés peuvent être naturellement encodés par des suites finies, par exemple avec des nombres naturels.
Exemples d'arbres et de non-arbres
- Un arbre enraciné dans la direction « à l'opposé de la racine » (un terme plus précis est « arborescence »), c'est-à-dire :
- Un graphe orienté ,
- dont le graphe non orienté sous-jacent est un arbre (deux sommets quelconques sont connectés par exactement un chemin simple),
- avec une racine distinguée (un sommet est désigné comme racine),
- qui détermine la direction des arêtes (les flèches pointent à l'opposé de la racine ; pour une arête donnée, le nœud d'où part l'arête est appelé le parent et le nœud vers lequel pointe l'arête est appelé l' enfant ), ainsi que :
- un ordre sur les nœuds enfants d'un nœud donné, et
- une valeur (d'un certain type de données) à chaque nœud.
Les arbres ont souvent un facteur de branchement fixe (plus précisément, borné) ( degré sortant ), et possèdent en particulier toujours deux nœuds enfants (éventuellement vides, donc au plus deux nœuds enfants non vides ), d'où un « arbre binaire ».
Autoriser les arbres vides simplifie certaines définitions, en complexifie d'autres : un arbre enraciné doit être non vide ; par conséquent, si les arbres vides sont autorisés, la définition ci-dessus devient « un arbre vide ou un arbre enraciné tel que… ». En revanche, les arbres vides simplifient la définition d'un facteur de branchement fixe : avec les arbres vides autorisés, un arbre binaire est un arbre tel que chaque nœud possède exactement deux enfants, chacun étant un arbre (éventuellement vide).
Applications
Les arbres sont couramment utilisés pour représenter ou manipuler des données hiérarchiques dans des applications telles que :
- Systèmes de fichiers pour :
- La structure de répertoires permet d'organiser les sous-répertoires et les fichiers ( les liens symboliques créent des graphes non arborescents, tout comme les liens physiques multiples pointant vers le même fichier ou répertoire).
- Le mécanisme utilisé pour allouer et lier des blocs de données sur le périphérique de stockage
- Hiérarchie des classes ou « arbre d'héritage » illustrant les relations entre les classes en programmation orientée objet ; l'héritage multiple produit des graphes non arborescents.
- Arbres de syntaxe abstraite pour les langages informatiques
- Traitement automatique du langage naturel :
- Arbres d'analyse
- Modélisation des énoncés dans une grammaire générative
- Arbre de dialogue pour générer des conversations
- Modèles d'objets de document (« arbre DOM ») des documents XML et HTML
- Les arbres de recherche stockent les données de manière à rendre possible un algorithme de recherche efficace grâce au parcours de l'arbre.
- Un arbre binaire de recherche est un type d' arbre binaire
- Représentation de listes de données triées
- Images générées par ordinateur :
- Stockage des arbres de Barnes-Hut utilisés pour simuler les galaxies
- Implémentation des tas
- Collections d'ensembles imbriqués
- Les taxonomies hiérarchiques telles que la classification décimale de Dewey, avec des sections de spécificité croissante.
- mémoire temporelle hiérarchique
- Programmation génétique
- Classification hiérarchique
Les arbres peuvent être utilisés pour représenter et manipuler diverses structures mathématiques, telles que :
- Chemins à travers un graphe arbitraire de nœuds et d'arêtes (y compris les multigraphes ), en créant plusieurs nœuds dans l'arbre pour chaque nœud du graphe utilisé dans plusieurs chemins.
- Toute hiérarchie mathématique
Les structures arborescentes sont souvent utilisées pour cartographier les relations entre des éléments, tels que :
- Composants et sous-composants pouvant être visualisés sur un dessin en vue éclatée
- Les appels de sous-programmes permettent d'identifier les sous-programmes d'un programme qui appellent d'autres sous-programmes de manière non récursive.
- L'hérédité de l'ADN entre les espèces par l'évolution , du code source par les projets logiciels (par exemple, la chronologie de la distribution Linux ), des conceptions dans différents types de voitures, etc.
- Le contenu des espaces de noms hiérarchiques
Les documents JSON et YAML peuvent être considérés comme des arbres, mais sont généralement représentés par des listes et des dictionnaires imbriqués .