Bonjour,
Bienvenue dans ce nouveau module consacré aux arbres. Dans les modules précédents, nous avons étudié les algorithmes de tri et démontré que pour les tris par comparaison, une complexité en est une borne infranchissable. Cette analyse théorique conclut notre étude approfondie des structures de données linéaires et des algorithmes qui leur sont associés.
Nous abordons maintenant une nouvelle classe de structures de données non linéaires : les arbres. Ces structures hiérarchiques sont omniprésentes en informatique, de la représentation de systèmes de fichiers à l'organisation d'index dans les bases de données, en passant par la syntaxe du code que vous écrivez.
L'objectif de cette première leçon est de poser des fondations solides : définir formellement un arbre binaire et ses propriétés fondamentales que sont la taille, la hauteur et la profondeur. La maîtrise de ces définitions, notamment leur nature récursive, est un prérequis indispensable pour tous les algorithmes que nous étudierons par la suite.
1. Des structures linéaires aux structures hiérarchiques
Jusqu'à présent, nous avons principalement travaillé avec des structures de données linéaires comme les tableaux et les listes chaînées. Si elles sont efficaces pour de nombreuses tâches, elles montrent leurs limites lorsque les données sont organisées de façon hiérarchique ou lorsque l'efficacité des opérations de recherche, d'insertion et de suppression devient critique.
Les arbres proposent une organisation différente qui peut, pour certaines applications, offrir des complexités logarithmiques là où les listes imposent des parcours linéaires.
Pour commencer, je vous invite à regarder la vidéo suivante, qui introduit le concept général d'arbre et le vocabulaire de base.
Les arbres binaires - Épisode 1 - Application avec Python
Cette vidéo de Cédric Gerland pose le décor en différenciant les arbres des structures linéaires et en présentant les termes fondamentaux. C'est une excellente entrée en matière visuelle.
Regardez les sections de 01:18 à 05:28. Concentrez-vous sur la terminologie : nœud (node), racine (root), feuille (leaf), parent, fils (child) et sous-arbre (subtree). Ces termes sont le langage commun pour décrire toutes les structures arborescentes.
Pour résumer et formaliser le vocabulaire :
- Un arbre est une structure de données composée de nœuds.
- Il y a un nœud spécial, la racine, qui est le seul à ne pas avoir de parent.
- Chaque autre nœud a exactement un parent.
- Un nœud peut avoir zéro, un ou plusieurs fils.
- Un nœud sans fils est une feuille (ou nœud externe).
- Un nœud qui n'est pas une feuille est un nœud interne.
- Le lien entre un parent et son fils est une arête.
Parmi la grande famille des arbres, nous allons nous concentrer sur la forme la plus courante et la plus fondamentale : l'arbre binaire. Comme son nom l'indique, c'est un arbre où chaque nœud a au plus deux fils.
2. Définition formelle d'un arbre binaire
Pour pouvoir raisonner rigoureusement sur les arbres et écrire des algorithmes corrects, une définition visuelle ne suffit pas. L'approche la plus puissante, et celle attendue à l'Agrégation, est la définition inductive (ou récursive).
Le document suivant, destiné aux classes préparatoires, présente une définition inductive formelle des arbres binaires. Cette définition est au cœur de la pensée algorithmique sur les arbres.
Lisez attentivement la section C "Définition inductive des arbres binaires" (Définition 17). Portez une attention particulière à la structure de la définition : un cas de base (l'arbre vide) et un cas constructeur.
Retenons cette définition formelle. Soit un ensemble d'étiquettes (les valeurs contenues dans les nœuds), l'ensemble des arbres binaires sur est défini comme suit :
- Cas de base : L'arbre vide (noté
Vide,nilou ) est un arbre binaire. - Cas inductif : Si est une étiquette, et si et sont deux arbres binaires, alors le triplet NŒUD() est un arbre binaire.
Dans ce triplet, est l'étiquette de la racine, est le sous-arbre gauche et est le sous-arbre droit.
Cette définition est extrêmement puissante. Elle reflète directement la structure des algorithmes que nous écrirons : un algorithme sur un arbre traitera le cas de l'arbre vide, puis, pour un nœud, il se rappellera récursivement sur ses sous-arbres gauche et droit. Le type OCaml présenté dans le document (type 'a btree = Vide | Noeud of 'a * 'a btree * 'a btree) est la traduction directe de cette définition, ce qui illustre l'adéquation entre la programmation fonctionnelle et ce type de structure.
3. Propriétés fondamentales : Taille, Profondeur, Hauteur
La définition inductive nous permet de définir très proprement les propriétés fondamentales d'un arbre.
Taille (Size)
La taille d'un arbre est simplement le nombre de nœuds qu'il contient. Sa définition inductive découle naturellement de celle de l'arbre :
- Cas de base : La taille de l'arbre vide est 0.
- Cas inductif : La taille d'un arbre NŒUD() est 1 (pour la racine) plus la taille de ses deux sous-arbres.
Vous pouvez retrouver cette définition dans le document précédent (resource ID=[LINK](https://iocpge-0dbdfc.forge.apps.education.fr/pdf/OI_Cours_S2_5_Arbres_binaires_et_ABR_web.pdf)) à l'Exemple 2 de la section E.
Profondeur (Depth)
La profondeur d'un nœud est la distance qui le sépare de la racine. Par convention, on la définit comme le nombre d'arêtes sur le chemin de la racine au nœud.
- La profondeur de la racine est 0.
- La profondeur d'un nœud est la profondeur de son parent + 1.
Hauteur (Height)
La hauteur d'un arbre est la profondeur maximale de l'une de ses feuilles. C'est la longueur du plus long chemin de la racine à une feuille. Là encore, la définition inductive est la plus élégante.
- Cas de base : Par convention, la hauteur de l'arbre vide est -1.
- Cas inductif : La hauteur d'un arbre NŒUD() est 1 plus le maximum des hauteurs de ses deux sous-arbres.
La convention peut surprendre, mais elle est très pratique. Grâce à elle, un arbre composé d'une unique feuille (qui est de la forme NŒUD(Vide, e, Vide)) a une hauteur de , ce qui est intuitif.
Le document ci-dessous formalise cette définition (Exemple 1, section E) et la justifie.
Revenons au document sur les arbres binaires pour examiner les définitions inductives de la hauteur et de la taille.
Lisez les Exemples 1 et 2 de la section E ("Définitions inductives de fonction sur les arbres"). Comprenez bien comment ces deux définitions suivent le modèle du cas de base et du pas d'induction.
Pour visualiser ces concepts, l'image suivante est très éclairante. Elle calcule la taille et la hauteur pour deux arbres différents. Notez que la hauteur y est définie comme le nombre de niveaux (racine au niveau 0), ce qui correspond à notre définition.
Enfin, pour une dernière révision visuelle de ces trois concepts, regardez la courte section suivante. Attention, la convention utilisée pour la profondeur et la hauteur y est différente (la racine est à la profondeur 1). Cette diversité de conventions existe, mais nous retiendrons pour ce cours la définition inductive formelle (racine à profondeur 0, hauteur de l'arbre vide à -1) car elle est plus cohérente et plus utile pour les preuves.
Les arbres binaires - Épisode 1 - Application avec Python
Cette dernière vidéo de Cédric Gerland illustre le calcul de la profondeur, de la hauteur et de la taille sur un exemple concret.
Regardez le segment de 05:28 à 07:14. L'objectif est de voir l'application de ces définitions sur un schéma. Ignorez la convention (profondeur de la racine = 1) et essayez de recalculer mentalement la hauteur avec notre convention (h = 4 au lieu de 5).
Conclusion
Cette première leçon a posé les bases terminologiques et formelles indispensables à l'étude des arbres.
Points clés à retenir :
- Les arbres sont des structures de données hiérarchiques, par opposition aux structures linéaires.
- Un arbre binaire se définit de manière inductive : soit il est vide, soit il est formé d'une racine et de deux sous-arbres binaires (gauche et droit).
- La taille d'un arbre est son nombre de nœuds. La définition inductive est : .
- La profondeur d'un nœud est sa distance à la racine (la racine est à profondeur 0).
- La hauteur d'un arbre est la profondeur maximale de ses feuilles. La définition inductive est : , avec .
La nature récursive de ces définitions n'est pas un simple exercice de style ; elle est le miroir de la manière dont nous allons concevoir et implémenter les algorithmes sur les arbres.
Prochaine étape :
Dans la prochaine leçon, nous mettrons en pratique cette structure récursive en implémentant les algorithmes de parcours d'arbres (préfixe, infixe, postfixe et en largeur), qui sont les opérations les plus fondamentales pour visiter et traiter les nœuds d'un arbre.