Arbres binaires et arbres binaires de recherche : fiche de révision

1Vocabulaire et propriétés

Un arbre binaire est soit vide, soit constitué d'un nœud (la racine) portant une étiquette et de deux sous-arbres binaires, le sous-arbre gauche et le sous-arbre droit. Un nœud sans enfant est une feuille. La taille est le nombre de nœuds ; la hauteur est le nombre de nœuds sur le plus long chemin de la racine à une feuille (convention du programme : un arbre vide a une hauteur 0, un arbre réduit à sa racine une hauteur 1 — vérifie toujours la convention de l'énoncé).

Encadrement fondamental : pour un arbre de taille n et de hauteur h, on a h ≤ n ≤ 2^h − 1. Un arbre filiforme (chaque nœud a un seul enfant) a h = n ; un arbre complet (tous les niveaux remplis) a n = 2^h − 1, donc h ≈ log₂(n). C'est cette hauteur logarithmique qui rend les arbres efficaces.

Implémentation en Python par une classe Noeud avec les attributs valeur, gauche et droit (None pour un sous-arbre vide), ou par des tuples imbriqués. Les fonctions sur les arbres sont naturellement récursives, le cas de base étant l'arbre vide.

2Calculs récursifs : taille, hauteur, parcours

def taille(a): return 0 if a is None else 1 + taille(a.gauche) + taille(a.droit)

def hauteur(a): return 0 if a is None else 1 + max(hauteur(a.gauche), hauteur(a.droit))

Les trois parcours en profondeur diffèrent par la position du traitement de la racine par rapport aux sous-arbres : préfixe (racine, gauche, droite), infixe (gauche, racine, droite), suffixe (gauche, droite, racine). Exemple avec la racine 8, fils gauche 3 (lui-même avec fils 1 et 6) et fils droit 10 : préfixe 8 3 1 6 10 ; infixe 1 3 6 8 10 ; suffixe 1 6 3 10 8.

def infixe(a):

if a is not None: infixe(a.gauche) ; print(a.valeur) ; infixe(a.droit)

Le parcours en largeur visite les nœuds niveau par niveau (8, puis 3 et 10, puis 1 et 6) et utilise une file : on enfile la racine, puis tant que la file n'est pas vide on défile un nœud, on le traite et on enfile ses enfants non vides. Chaque parcours visite chaque nœud une fois : complexité O(n).

3Arbres binaires de recherche (ABR)

Un arbre binaire de recherche est un arbre binaire étiqueté par des valeurs comparables tel que, pour tout nœud, toutes les valeurs du sous-arbre gauche sont inférieures (ou égales, selon la convention) à la valeur du nœud, et toutes celles du sous-arbre droit lui sont supérieures. Propriété clé : le parcours infixe d'un ABR donne les valeurs dans l'ordre croissant.

Recherche : on compare à la racine ; si égal, trouvé ; si plus petit, on continue à gauche ; sinon à droite. Chaque étape descend d'un niveau : complexité O(h), soit O(log n) pour un arbre équilibré, mais O(n) pour un arbre filiforme (obtenu en insérant des valeurs déjà triées). Insertion : même descente, puis création d'une feuille à l'emplacement vide atteint.

def recherche(a, x):

if a is None: return False

if x == a.valeur: return True

if x < a.valeur: return recherche(a.gauche, x)

return recherche(a.droit, x)

Le programme se limite à la recherche et à l'insertion ; l'équilibrage (arbres AVL, rouge-noir) est hors programme mais l'idée qu'un arbre dégénéré perd son efficacité doit être comprise.

4Exercice type et pièges

Énoncé type : « Écrire une fonction qui renvoie le nombre de feuilles d'un arbre binaire. » Cas de base : arbre vide → 0 ; nœud sans enfant → 1 ; sinon somme sur les deux sous-arbres.

def nb_feuilles(a):

if a is None: return 0

if a.gauche is None and a.droit is None: return 1

return nb_feuilles(a.gauche) + nb_feuilles(a.droit)

Autres classiques : vérifier qu'un arbre est un ABR (le parcours infixe doit être strictement croissant), trouver le minimum d'un ABR (descendre tout à gauche), calculer la hauteur minimale pour n nœuds (⌈log₂(n+1)⌉).

Pièges : oublier le cas de base None ; confondre hauteur et profondeur, ou les deux conventions de hauteur ; croire qu'un ABR est toujours équilibré ; écrire un parcours infixe qui traite la racine avant le sous-arbre gauche ; insérer des valeurs triées et attendre une recherche en O(log n).