Les arbres
Cours · NSI (terminale), chapitre 3 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
Les structures linéaires comme les listes, les piles ou les files organisent les données les unes à la suite des autres. Mais de nombreuses informations du monde réel possèdent une organisation hiérarchique : l'arborescence des fichiers d'un disque dur, l'arbre généalogique d'une famille, le sommaire d'un livre, ou encore les coups possibles dans une partie d'échecs. Pour modéliser ces situations, on utilise une structure de données fondamentale : l'arbre.
Dans ce chapitre, nous définissons précisément le vocabulaire des arbres, nous étudions le cas particulier très important des arbres binaires, leurs différents parcours, puis nous nous concentrons sur les arbres binaires de recherche (ABR), une structure qui permet de rechercher, d'insérer et de supprimer efficacement des valeurs. Toutes les implémentations seront réalisées en Python à l'aide d'une classe et de la récursivité, omniprésente dès que l'on manipule des arbres.
3.1 Vocabulaire des arbres
Un arbre est une structure composée de nœuds reliés par des liens. Chaque nœud peut posséder des « enfants », mais possède au plus un « parent ».
Un arbre est un ensemble de nœuds organisé hiérarchiquement de la façon suivante :
- soit l'arbre est vide ;
- soit il possède un nœud particulier appelé racine, auquel sont rattachés des sous-arbres, eux-mêmes des arbres.
Cette définition est récursive : un arbre est défini à partir d'arbres plus petits.
On adopte le vocabulaire suivant, partiellement emprunté à la généalogie et à la botanique (mais l'arbre informatique est traditionnellement dessiné la racine en haut !).
- La racine est l'unique nœud sans parent (le sommet de l'arbre).
- Un nœud interne possède au moins un enfant.
- Une feuille (ou nœud externe) est un nœud sans enfant.
- Le parent d'un nœud est le nœud situé juste au-dessus de lui ; ses enfants (ou fils) sont les nœuds situés juste en dessous.
- Deux nœuds ayant le même parent sont des nœuds frères.
- Un sous-arbre est l'arbre formé par un nœud et tous ses descendants.
Considérons l'arbre suivant, représenté textuellement par indentation (chaque niveau d'indentation correspond à une descente d'un niveau dans l'arbre) :
A <- racine
|-- B <- enfant de A
| |-- D <- feuille
| |-- E <- feuille
|-- C <- enfant de A
|-- F <- feuilleIci : A est la racine ; B et C sont ses enfants (et sont frères) ; D, E et F sont des feuilles ; A, B et C sont des nœuds internes. Le nœud B avec ses descendants D et E forme un sous-arbre.
On définit ensuite plusieurs grandeurs numériques qui mesurent la « taille » et la « forme » d'un arbre.
Soit un arbre non vide.
- La profondeur d'un nœud est le nombre de liens qui le séparent de la racine. La racine est à la profondeur ; ses enfants à la profondeur , etc.
- La hauteur de l'arbre est la profondeur maximale atteinte par une feuille, c'est-à-dire la longueur du plus long chemin de la racine vers une feuille. Un arbre réduit à sa racine a une hauteur de .
- La taille de l'arbre est son nombre total de nœuds.
La convention sur la hauteur (et la profondeur de la racine) varie selon les ouvrages : certains comptent la racine à la profondeur et donnent la hauteur en nombre de niveaux. Dans ce manuel, nous adoptons la convention « racine à la profondeur », qui est la plus répandue en NSI. Il faut toujours vérifier la convention utilisée dans un énoncé.
Reprenons l'arbre précédent.
Aest à la profondeur ,BetCà la profondeur ,D,EetFà la profondeur .- La hauteur de l'arbre vaut (la feuille la plus profonde est à la profondeur ).
- La taille vaut (les nœuds
A,B,C,D,E,F).
3.2 Les arbres binaires
Parmi tous les arbres, un cas particulier est essentiel : celui où chaque nœud possède au plus deux enfants.
Exercices du chapitre
- Valeur maximale d'un arbre binaire corrigé
- Vérifier qu'un arbre est un ABR corrigé
- Parcours infixe et tri corrigé
- Problème — Suppression d'une valeur dans un ABR corrigé
- Compter les feuilles corrigé
- Recherche du minimum dans un ABR corrigé