Arbre (type de données abstrait)

En informatique , un arbre est un type de données abstrait largement utilisé qui représente une structure arborescente hiérarchique avec un ensemble de nœuds connectés . Chaque nœud de l'arbre peut être connecté à de nombreux enfants (selon le type d'arbre), mais doit être connecté à exactement un parent, à l'exception du nœud racine , qui n'a pas de parent (c'est-à-dire le nœud racine comme nœud le plus haut dans la hiérarchie de l'arbre). Ces contraintes signifient qu'il n'y a pas de cycles ou de « boucles » (aucun nœud ne peut être son propre ancêtre), et aussi que chaque enfant peut être traité comme le nœud racine de son propre sous-arbre, ce qui fait de la récursivité une technique 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 des 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 couramment utilisé, qui limite le nombre d'enfants pour chaque parent à deux au maximum. 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 uniquement aux nœuds feuilles , qui n'ont pas de nœuds enfants.

Le type de données abstrait (ADT) peut être représenté de plusieurs manières, notamment par une liste de parents avec des pointeurs vers des enfants, une liste d'enfants avec des pointeurs vers des parents ou une liste de nœuds et une liste distincte de relations parent-enfant (un type spécifique 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 les performances.

Les arbres utilisés en informatique sont similaires aux constructions mathématiques des arbres de la théorie des graphes , des arbres de la théorie des ensembles et des arbres de la théorie descriptive des ensembles , mais peuvent en être différents .

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 :
  • Structure de répertoire utilisée pour organiser les sous-répertoires et les fichiers ( les liens symboliques créent des graphiques non arborescents, tout comme plusieurs liens physiques 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 de classes ou « arbre d'héritage » montrant les relations entre les classes dans la programmation orientée objet ; l'héritage multiple produit des graphes non arborescents
• Arbres de syntaxe abstraits pour les langages informatiques
• Traitement du langage naturel :
  • Analyser les arbres
  • 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 documents (« arbre DOM ») de documents XML et HTML
• Les arbres de recherche stockent les données d'une manière qui permet un algorithme de recherche efficace via le parcours des arbres.
  • Un arbre de recherche binaire est un type d' arbre binaire
• Représenter des listes triées de données
• Imagerie de synthèse :
  • Partitionnement de l'espace , y compris le partitionnement de l'espace binaire
  • Composition numérique
• Stockage des arbres de Barnes-Hut utilisés pour simuler les galaxies
• Implémentation de tas
• Collections d'ensembles imbriqués
• 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
• Regroupement 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 de graphe utilisé dans plusieurs chemins
• Toute hiérarchie mathématique

Les structures arborescentes sont souvent utilisées pour cartographier les relations entre les éléments, tels que :

• Composants et sous-composants pouvant être visualisés dans un dessin en vue éclatée
• Appels de sous-routines utilisés pour identifier les sous-routines d'un programme qui appellent d'autres sous-routines de manière non récursive
• Héritage de l'ADN entre les espèces par l'évolution , du code source des projets logiciels (par exemple, la chronologie de la distribution Linux ), des conceptions de divers 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 .

Un nœud est une structure qui peut contenir des données et des connexions à d'autres nœuds, parfois appelés arêtes ou liens . Chaque nœud d'un arbre a zéro ou plusieurs nœuds enfants , qui sont en dessous de lui dans l'arbre (par convention, les arbres sont dessinés avec les descendants descendants ). Un nœud qui a un enfant est appelé le nœud parent de l'enfant (ou supérieur ). Tous les nœuds ont exactement un parent, à l'exception du nœud racine le plus haut , qui n'en a aucun. Un nœud peut avoir de nombreux nœuds ancêtres , comme le parent du parent. Les nœuds enfants avec le même parent sont des nœuds frères . En général, les frères ont un ordre, le premier étant traditionnellement dessiné à gauche. Certaines définitions permettent à un arbre de n'avoir aucun nœud du tout, auquel cas il est dit vide .

Un nœud interne (également appelé nœud interne , inode en abrégé ou nœud de branche ) est tout nœud d'un arbre qui possède des nœuds enfants. De même, un nœud externe (également appelé nœud externe , nœud feuille ou nœud terminal ) est tout nœud qui n'a pas de nœuds enfants.

La hauteur d'un nœud est la longueur du chemin descendant le plus long vers une feuille à partir de ce nœud. La hauteur de la racine est la hauteur de l'arbre. La profondeur d'un nœud est la longueur du chemin vers sa racine (c'est-à-dire son chemin racine ). Ainsi, le nœud racine a une profondeur de zéro, les nœuds feuilles ont une hauteur de zéro et un arbre avec un seul nœud (donc à la fois une racine et une feuille) a une profondeur et une hauteur de zéro. Par convention, un arbre vide (arbre sans nœud, si ceux-ci sont autorisés) a une hauteur de −1.

Chaque nœud non racine peut être traité comme le nœud racine de son propre sous-arbre , qui comprend ce nœud et tous ses descendants.

Autres termes utilisés avec les arbres :

Voisin

Parent ou enfant.

Ancêtre

Un nœud accessible par une procédure répétée de l'enfant au parent.

Descendant

Un nœud accessible par une procédure répétée du parent vers l'enfant. Également appelé sous-enfant .

Degré

Pour un nœud donné, son nombre d'enfants. Une feuille, par définition, a un degré zéro.

Degré d'arbre

Le degré d'un arbre est le degré maximal d'un nœud de l'arbre.

Distance

Le nombre d'arêtes le long du chemin le plus court entre deux nœuds.

Niveau

Le niveau d'un nœud est le nombre d'arêtes le long du chemin unique entre lui et le nœud racine. C'est la même chose que la profondeur.

Largeur

Le nombre de nœuds dans un niveau.

Largeur

Le nombre de feuilles.

Forêt

Un ensemble d’un ou plusieurs arbres disjoints.

Arbre ordonné

Un arbre enraciné dans lequel un ordre est spécifié pour les enfants de chaque sommet.

Taille d'un arbre

Nombre de nœuds dans l'arbre.

• Énumération de tous les éléments
• Énumération d'une section d'un arbre
• Recherche d'un article
• Ajout d'un nouvel élément à une certaine position sur l'arbre
• Supprimer un élément
• Élagage : suppression d'une section entière d'un arbre
• Greffe : Ajout d'une section entière à un arbre
• Trouver la racine de n'importe quel nœud
• Trouver le plus petit ancêtre commun de deux nœuds

Le fait de parcourir les éléments d'un arbre, au moyen des connexions entre les parents et les enfants, est appelé parcourir l'arbre , et l'action est une promenade de l'arbre. Souvent, une opération peut être effectuée lorsqu'un pointeur arrive à un nœud particulier. Une promenade dans laquelle chaque nœud parent est parcouru avant ses enfants est appelée une promenade pré-ordre ; une promenade dans laquelle les enfants sont parcourus avant que leurs parents respectifs ne soient parcourus est appelée une promenade post-ordre ; une promenade dans laquelle le sous-arbre gauche d'un nœud, puis le nœud lui-même, et enfin son sous-arbre droit sont parcourus est appelée une traversée dans l'ordre . (Ce dernier scénario, se référant exactement à deux sous-arbres, un sous-arbre gauche et un sous-arbre droit, suppose spécifiquement un arbre binaire .) Une promenade d'ordre de niveau effectue effectivement une recherche en largeur sur l'intégralité d'un arbre ; les nœuds sont parcourus niveau par niveau, où le nœud racine est visité en premier, suivi de ses nœuds enfants directs et de leurs frères et sœurs, suivis de ses nœuds petits-enfants et de leurs frères et sœurs, etc., jusqu'à ce que tous les nœuds de l'arbre aient été parcourus.

Il existe de nombreuses façons différentes de représenter les arbres. Dans la mémoire de travail, les nœuds sont généralement des enregistrements alloués de manière dynamique avec des pointeurs vers leurs enfants, leurs parents ou les deux, ainsi que toutes les données associées. S'ils ont une taille fixe, les nœuds peuvent être stockés dans une liste. Les nœuds et les relations entre les nœuds peuvent être stockés dans un type spécial distinct de liste de contiguïté . Dans les bases de données relationnelles , les nœuds sont généralement représentés sous forme de lignes de table, avec des identifiants de ligne indexés facilitant les pointeurs entre les parents et les enfants.

Les nœuds peuvent également être stockés sous forme d'éléments dans 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é sous la forme d'une liste de listes : la tête d'une liste (la valeur du premier terme) est l'enfant gauche (sous-arbre), tandis que la queue (la liste du deuxième terme et des suivants) est l'enfant droit (sous-arbre). Cela peut être modifié pour autoriser également les valeurs, comme dans les expressions S de Lisp, où la tête (valeur du premier terme) est la valeur du nœud, la tête de la queue (valeur du deuxième terme) est l'enfant gauche et la queue de la queue (liste du troisième terme et des suivants) est l'enfant droit.

Les arbres ordonnés peuvent être naturellement codés par des séquences finies, par exemple avec des nombres naturels.

En tant que type de données abstrait , le type d'arbre abstrait T avec des valeurs d'un certain type E est défini, en utilisant le type de forêt abstraite F (liste d'arbres), par les fonctions :

valeur : T → E

enfants : T → F

nul : () → F

nœud : E × F → T

avec les axiomes :

valeur(nœud( e , f )) = e

enfants(nœud( e , f )) = f

En termes de théorie des types , un arbre est un type inductif défini par les constructeurs nil (forêt vide) et node (arbre avec nœud racine avec valeur donnée et enfants).

Considérée dans son ensemble, une structure de données arborescente est un arbre ordonné , généralement avec des valeurs attachées à chaque nœud. Concrètement, elle est (si elle doit être non vide) :

• Un arbre enraciné avec la direction « éloignée de la racine » (un terme plus restreint est une « arborescence »), ce qui signifie :
  • 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 la racine),
  • qui détermine la direction des arêtes (les flèches pointent dans la direction opposée à la racine ; étant donné une arête, le nœud à partir duquel l'arête pointe est appelé le parent et le nœud vers lequel l'arête pointe 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.

Souvent, les arbres ont un facteur de ramification fixe (plus précisément, limité) ( outdegree ), en particulier ils ont 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, et d'autres les complique : un arbre enraciné doit être non vide, donc si les arbres vides sont autorisés, la définition ci-dessus devient plutôt "un arbre vide ou un arbre enraciné tel que ...". D'un autre côté, les arbres vides simplifient la définition d'un facteur de ramification fixe : avec les arbres vides autorisés, un arbre binaire est un arbre tel que chaque nœud a exactement deux enfants, chacun étant un arbre (éventuellement vide).