3.8 KiB
Structures Arborescentes
Structure présente partout dans le monde numérique, des répertoires de fichiers sur un ordinateur aux bases de données et algorithmes de recherche, les abres sont un pan essentiel de l'informatique. Ils permettent de structurer efficacement des données hiérarchiques et d’optimiser certaines opérations comme la recherche ou le tri. En NSI, nous allons explorer une version particulière de ces structures : les arbres binaires.
Le programme
Définition
Attention, il y a quelques mots clés qui vont survenir dans les prochaines lignes !
-
Un arbre est une structure de données hiérarchique et récursive, composée d’éléments appelés des noeuds.
-
Chacun de ces noeuds peut être étiqueté pour représenter une information.
-
Les nœuds d’un arbre sont reliés entre eux par des liens que l’on appelle souvent arêtes lorsque l'on parle de graphes (que nous verrons prochainement), mais en contexte arborescent, on parle couramment de fils pour désigner les connexions hiérarchiques.
-
Un nœud parent est relié à ses nœuds enfants par ces fils.
- Ces relations définissent la hiérarchie dans l’arbre.
-
Un lien “fils” est orienté : il part d’un parent vers un enfant.
- Ce lien structure la hiérarchie descendante, qui est essentielle pour le parcours de l’arbre (comme un arbre généalogique).
Question : Pourquoi pensez-vous que cette structure est utilisée dans les systèmes informatiques ?
Caractéristiques d'un arbre
Un arbre possède donc un nombre de noeuds, qu'on appelle taille d'un arbre.
Question : Quelle est la taille de l'arbre représenté ci dessus ?
On parle également de hauteur d'un arbre :
- Elle correspond à la profondeur maximale d’un nœud dans l’arbre, c’est-à-dire le plus grand nombre d’arêtes depuis la racine jusqu’à une feuille.
- La hauteur est le nombre maximum de niveaux dans l’arbre, en partant de la racine jusqu’à la feuille la plus profonde.
- Selon les points de vue, la hauteur est parfois définie différemment :
- On peut considérer la hauteur d'un arbre vide à 0, soit à 1.
Question : Quelle est la hauteur de l'arbre du dessus ?
Arbres Binaires et Arbres binaires de recherche
On appelle Arbre Binaire (AB) une structure de données hiérarchique dans laquelle chaque nœud peut avoir au maximum deux enfants, appelés fils gauche et fils droit. Les valeurs des nœuds n’ont pas de contrainte particulière.
Un Arbre Binaire de Recherche (ABR) est un arbre binaire dans lequel, pour chaque nœud :
1. Les valeurs des nœuds du sous-arbre gauche sont strictement inférieures à la valeur du nœud.
2. Les valeurs des nœuds du sous-arbre droit sont strictement supérieures à la valeur du nœud.
À quoi cette structure sert-elle d'après vous ?
Conclusion
Comprendre ces caractéristiques nous aidera à explorer comment manipuler efficacement ces structures pour chercher, insérer ou supprimer des données, et ce, très prochainement.
Auteurs : Florian Mathieu, Timothée Decoster, Enzo Frémaux
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.