Arbre enraciné

Pour les articles homonymes, voir Arbre (homonymie).

Cet article ne cite pas suffisamment ses sources (décembre 2020).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

En théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent.

En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes.

Vocabulaire

Dans un arbre, on distingue deux catégories d'éléments :

les feuilles (ou nœuds externes), éléments ne possédant pas de fils dans l'arbre ;
les nœuds internes, éléments possédant des fils (sous-branches).

La racine de l'arbre est l'unique nœud ne possédant pas de parent. Les nœuds (les pères avec leurs fils) sont reliés entre eux par une arête. Selon le contexte, un nœud peut désigner un nœud interne ou externe (feuille) de l'arbre.

La profondeur d'un nœud est la distance, i.e. le nombre d'arêtes, de la racine au nœud^{[note 1]}. La hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre. La taille d'un arbre est son nombre de nœuds (en comptant les feuilles ou non), la longueur de cheminement est la somme des profondeurs de chacune des feuilles.

Les arbres peuvent être étiquetés. Dans ce cas, chaque nœud possède une étiquette, qui est en quelque sorte le « contenu » du nœud. L'étiquette peut être très simple : un nombre entier, par exemple. Elle peut également être aussi complexe que l'on veut : un objet, une instance d'une structure de données, un pointeur, etc. Il est presque toujours obligatoire de pouvoir comparer les étiquettes selon une relation d'ordre total, afin d'implanter les algorithmes sur les arbres.

Les fichiers et dossiers dans un système de fichiers sont généralement organisés sous forme arborescente. Voir par exemple la FHS.

Les arbres sont en fait rarement utilisés en tant que tels, mais de nombreux types d'arbres avec une structure plus restrictive existent et sont couramment utilisés en algorithmique, notamment pour gérer des bases de données, ou pour l'indexation de fichiers. Ils permettent alors des recherches rapides et efficaces. Nous vous en donnons ici les principaux exemples :

Les arbres binaires dont chaque nœud a au plus deux fils : ils sont en fait utilisés sous forme d'arbres binaires de recherche, de tas, d'AVL, ou encore d'arbres rouge-noir. Les deux derniers exemples sont des cas particuliers d'arbres équilibrés, c'est-à-dire d'arbres dont les sous-branches ont presque la même hauteur.
Les arbres n-aires qui sont une généralisation des arbres binaires : chaque nœud a au plus n fils. Les arbres 2-3-4 et les arbres B en sont des exemples d'utilisation et sont eux aussi des arbres équilibrés.

Construction

Pour construire un arbre à partir de cases ne contenant que des informations, on peut procéder de l'une des trois façons suivantes :

Créer une structure de données composée de :
1. l'étiquette (la valeur contenue dans le nœud),
2. un lien vers chaque nœud fils,
3. un arbre particulier, l'arbre vide, qui permet de caractériser les feuilles. Une feuille a pour fils des arbres vides uniquement.
Créer une structure de données composée de :
1. l'étiquette (la valeur contenue dans le nœud),
2. un lien vers le « premier » nœud fils (nœud fils gauche le cas échéant),
3. un autre lien vers le nœud frère (le « premier » nœud frère sur la droite le cas échéant).
Créer une structure de données composée de :
1. l'étiquette (la valeur contenue dans le nœud),
2. un lien vers le nœud père.

On note qu'il existe d'autres types de représentation propres à des cas particuliers d'arbres. Par exemple, le tas est représenté par un tableau d'étiquettes.

Parcours

Les parcours d'arbre sont des processus de visites des sommets d'un arbre, par exemple pour trouver une valeur.

Parcours en largeur

Cet algorithme est un cas particulier du parcours en largeur sur les graphes, détaillé dans l'article Algorithme de parcours en largeur.

Le parcours en largeur correspond à un parcours par niveau de nœuds de l'arbre. Un niveau est un ensemble de nœuds internes ou^{[note 2]} de feuilles situés à la même profondeur — on parle aussi de nœud ou de feuille de même hauteur dans l'arbre considéré. L'ordre de parcours d'un niveau donné est habituellement conféré, de manière récursive, par l'ordre de parcours des nœuds parents — nœuds du niveau immédiatement supérieur.

Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, C, D, E, F puis G.

Parcours en profondeur

Cet algorithme est un cas particulier du parcours en profondeur sur les graphes, détaillé dans l'article Algorithme de parcours en profondeur.

Le parcours en profondeur est un parcours récursif sur un arbre. Dans le cas général, deux ordres sont possibles :

Parcours en profondeur préfixe : dans ce mode de parcours, le nœud courant est traité avant ses descendants. Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, D, E, C, F puis G.
Parcours en profondeur suffixe : dans ce mode de parcours, le nœud courant est traité après ses descendants. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C puis A. Ce mode de parcours correspond à une notation polonaise inversée.

Pour les arbres binaires, on peut également faire un parcours infixe, c'est-à-dire traiter le nœud courant entre les nœuds gauche et droit. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, B, E, A, F, C puis G.

Voir aussi

Notes et références

Notes

↑ Les arêtes d'un arbre peuvent être pondérés. Cette pondération peut servir à l'évaluation d'une mesure entre deux nœuds quelconques de l'arbre. On parle de longueur du (plus court) chemin entre deux nœuds d'un arbre, la longueur étant distincte de la différence des hauteurs respectives.
↑ Le « ou » est large : un niveau peut recouvrir à la fois des nœuds et des feuilles ; en effet, toutes les feuilles d'un arbre ne sont pas nécessairement situées à la même « distance » du nœud racine.

Références

v · m Arbre enraciné
Arbre binaire	Arbre binaire de recherche Arbre de fouille Arbre cartésien MVP Tree (en) Top tree (en) T-tree (en)
Arbre équilibré	AA tree (en) Arbre AVL LLRB tree (en) Arbre bicolore Arbre bouc-émissaire Arbre splay Treap
Arbre B	B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a,b)-tree (en) Dancing tree Htree (en)
Trie	Arbre des suffixes Arbre radix Arbre ternaire de recherche X-fast trie (en) Y-fast trie (en)
Partition binaire de l'espace trees	Quadtree Octree Arbre kd (relaxé) Implicit k-d tree (en) Vp-tree
Arbres non binaires	Arbre exponentiel Fusion tree (en) arbre d'intervalles arbre PQ arbre de portée (range tree) arbre SPQR arbre de Van Emde Boas
Arbre de base de données spatiales	R-arbre R+ tree (en) R* tree (en) X-tree (en) M-tree (en) arbre de segments Hilbert R-tree (en) Priority R-tree (en)
Autres arbres	Arbre de Merkle Arbre couvrant de poids minimal Arbre syntaxique Arbre de la syntaxe abstraite Finger tree (en) Order statistic tree (en) Arbre métrique Cover tree (en) BK-tree (en) Doubly chained tree iDistance (en) Link-cut tree (en) Fenwick tree (en) Tas Tas binomial Tas de Fibonacci Arbre cousu

v · m

Éléments de programmation informatique

Bibliothèque logicielle

Vocabulaire

Algorithme Expression Indentation Instruction Ligne de code Opérateur Pseudo-code Ramasse-miettes
Fonctions	Convention de nommage Dispatch multiple Factorisation Fonction imbriquée Fonction de rappel Fonction d'ordre supérieur Fonction récursive Généricité Opérande Paramètre Polymorphisme Procédure Signature de type Surcharge
Objet	Classe Constructeur Destructeur Encapsulation Héritage Héritage multiple Instance Méthode
Événementiel	Inversion de contrôle

Code source

Structures de données	Arbre Attribut Caractère Enregistrement Ensemble File Liste Liste chaînée Pile Propriété Sémaphore Tableau Tas Type abstrait Vecteur
Déclarations	Affectation Pointeur Portée Référence Tableau associatif Type énuméré Type récursif Typage statique Variable Variable globale Variable locale
Structures de contrôle	Case Do Else Eval If For Goto Loop Switch While
Fonctions usuelles	Concaténation Incrémentation malloc printf

Outil de développement

Folklore

Catégories :

Programmation informatique
Développement logiciel

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique