Partie 1 : Algorithmes sur les arbres binaires¶
Programme officiel (B.O.)¶
B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Algorithmes sur les arbres binaires et sur les arbres binaires de recherche. | Calculer la taille et la hauteur d'un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d'abord). Rechercher une clé dans un arbre de recherche, insérer une clé. | Une structure de données récursive adaptée est utilisée. L'exemple des arbres permet d'illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique. |
1. Rappels sur les arbres binaires¶
1.1 Définition récursive¶
Un arbre binaire est soit :
- l'arbre vide (noté
Noneen Python) ; - un nœud contenant une valeur (appelée étiquette ou clé), un sous-arbre gauche et un sous-arbre droit, qui sont eux-mêmes des arbres binaires.
1.2 Vocabulaire¶
| Terme | Définition |
|---|---|
| Racine | Nœud au sommet de l'arbre (ici : 8) |
| Feuille | Nœud sans enfants (ici : 1, 4, 7, 13) |
| Nœud interne | Nœud ayant au moins un enfant |
| Sous-arbre gauche/droit | Arbre formé par l'enfant gauche/droit et ses descendants |
| Taille | Nombre total de nœuds |
| Hauteur | Longueur du plus long chemin de la racine à une feuille |
| Profondeur d'un nœud | Nombre d'arêtes entre la racine et ce nœud |
1.3 Implémentation en Python (classe)¶
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
Construction de l'arbre de l'exemple :
arbre = Noeud(8,
Noeud(3,
Noeud(1),
Noeud(6, Noeud(4), Noeud(7))
),
Noeud(10,
None,
Noeud(14, Noeud(13), None)
)
)
2. Taille et hauteur¶
2.1 Taille (nombre de nœuds)¶
La taille est définie récursivement :
2.2 Hauteur¶
La hauteur est la profondeur maximale. Par convention, l'arbre vide a une hauteur de -1 (ou 0 selon les conventions).
def hauteur(arbre):
if arbre is None:
return -1
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
2.3 Encadrement de la hauteur¶
Pour un arbre binaire de taille n :
- Hauteur minimale (arbre complet/équilibré) : \(h = \lfloor \log_2(n) \rfloor\)
- Hauteur maximale (arbre filiforme, dégénéré en liste) : \(h = n - 1\)
2.4 Compter les feuilles¶
def nb_feuilles(arbre):
if arbre is None:
return 0
if arbre.gauche is None and arbre.droit is None:
return 1
return nb_feuilles(arbre.gauche) + nb_feuilles(arbre.droit)
3. Parcours en profondeur¶
Les parcours en profondeur (Depth-First Search, DFS) explorent l'arbre en descendant le plus profondément possible avant de remonter. Ils diffèrent par le moment où l'on traite la racine.
3.1 Parcours préfixe (racine - gauche - droite)¶
On traite la racine d'abord, puis le sous-arbre gauche, puis le sous-arbre droit.
def parcours_prefixe(arbre):
if arbre is None:
return []
return ([arbre.valeur]
+ parcours_prefixe(arbre.gauche)
+ parcours_prefixe(arbre.droit))
Sur notre exemple : 8, 3, 1, 6, 4, 7, 10, 14, 13
3.2 Parcours infixe (gauche - racine - droite)¶
On traite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit.
def parcours_infixe(arbre):
if arbre is None:
return []
return (parcours_infixe(arbre.gauche)
+ [arbre.valeur]
+ parcours_infixe(arbre.droit))
Sur notre exemple : 1, 3, 4, 6, 7, 8, 10, 13, 14
Propriété remarquable
Pour un arbre binaire de recherche, le parcours infixe donne les valeurs dans l'ordre croissant.
3.3 Parcours suffixe (gauche - droite - racine)¶
On traite les sous-arbres d'abord, puis la racine en dernier.
def parcours_suffixe(arbre):
if arbre is None:
return []
return (parcours_suffixe(arbre.gauche)
+ parcours_suffixe(arbre.droit)
+ [arbre.valeur])
Sur notre exemple : 1, 4, 7, 6, 3, 13, 14, 10, 8
3.4 Résumé des parcours en profondeur¶
| Parcours | Ordre | Résultat sur l'exemple |
|---|---|---|
| Préfixe | Racine → Gauche → Droit | 8, 3, 1, 6, 4, 7, 10, 14, 13 |
| Infixe | Gauche → Racine → Droit | 1, 3, 4, 6, 7, 8, 10, 13, 14 |
| Suffixe | Gauche → Droit → Racine | 1, 4, 7, 6, 3, 13, 14, 10, 8 |
4. Parcours en largeur¶
4.1 Principe¶
Le parcours en largeur (Breadth-First Search, BFS) explore l'arbre niveau par niveau, de gauche à droite. Il utilise une file (FIFO).
4.2 Algorithme¶
from collections import deque
def parcours_largeur(arbre):
if arbre is None:
return []
resultat = []
file = deque([arbre])
while file:
noeud = file.popleft()
resultat.append(noeud.valeur)
if noeud.gauche is not None:
file.append(noeud.gauche)
if noeud.droit is not None:
file.append(noeud.droit)
return resultat
Sur notre exemple : 8, 3, 10, 1, 6, 14, 4, 7, 13
5. Arbres binaires de recherche (ABR)¶
5.1 Définition¶
Un arbre binaire de recherche (ABR) est un arbre binaire vérifiant pour chaque nœud :
- toutes les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud ;
- toutes les valeurs du sous-arbre droit sont supérieures à la valeur du nœud.
5.2 Recherche dans un ABR¶
La recherche se fait par dichotomie : à chaque nœud, on choisit de descendre à gauche ou à droite.
def recherche_abr(arbre, cle):
if arbre is None:
return False
if cle == arbre.valeur:
return True
elif cle < arbre.valeur:
return recherche_abr(arbre.gauche, cle)
else:
return recherche_abr(arbre.droit, cle)
Complexité : dans un ABR équilibré, la recherche est en O(log₂ n) (on divise l'espace de recherche par 2 à chaque étape). Dans le pire cas (arbre dégénéré), elle est en O(n).
5.3 Insertion dans un ABR¶
Pour insérer une valeur, on descend dans l'arbre comme pour une recherche, puis on crée un nouveau nœud à l'emplacement vide trouvé.
def inserer_abr(arbre, cle):
if arbre is None:
return Noeud(cle)
if cle < arbre.valeur:
arbre.gauche = inserer_abr(arbre.gauche, cle)
elif cle > arbre.valeur:
arbre.droit = inserer_abr(arbre.droit, cle)
return arbre
# Construction d'un ABR par insertions successives
racine = None
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
racine = inserer_abr(racine, val)
À retenir¶
| Concept | Description |
|---|---|
| Arbre binaire | Structure récursive : vide ou nœud + sous-arbre gauche + sous-arbre droit |
| Taille | Nombre de nœuds (récursif : 1 + taille gauche + taille droit) |
| Hauteur | Profondeur maximale (récursif : 1 + max des hauteurs) |
| Parcours préfixe | Racine → Gauche → Droit |
| Parcours infixe | Gauche → Racine → Droit (donne l'ordre croissant dans un ABR) |
| Parcours suffixe | Gauche → Droit → Racine |
| Parcours en largeur | Niveau par niveau, avec une file |
| ABR | Arbre binaire de recherche : gauche < racine < droit |
| Recherche ABR | O(log₂ n) si l'arbre est équilibré |