Algorithmes sur les arbres binaires et sur les arbres binaires de recherche

Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

L'essentiel

Un arbre binaire de recherche (ABR) est un arbre binaire muni d'une propriété d'ordre : pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à sa valeur, et toutes celles du sous-arbre droit lui sont supérieures. Cette propriété permet une recherche dichotomique.

Les parcours en profondeur se déclinent en trois ordres selon la place de la racine : - préfixe : racine, gauche, droit ; - infixe : gauche, racine, droit ; - suffixe (postfixe) : gauche, droit, racine.

Sur un ABR, le parcours infixe restitue les valeurs en ordre croissant, ce qui caractérise un ABR correct.

La recherche et l'insertion descendent dans l'arbre en comparant à chaque nœud, d'où une complexité en O(h) (hauteur) : O(\log n) si l'arbre est équilibré, mais O(n) s'il est filiforme.

Formules et schémas clés

Recherche récursive :

def recherche(a, x): if a is None: return False if a.valeur == x: return True if x < a.valeur: return recherche(a.gauche, x) return recherche(a.droit, x)

Insertion récursive :

def inserer(a, x): if a is None: return Noeud(x) if x < a.valeur: a.gauche = inserer(a.gauche, x) else: a.droit = inserer(a.droit, x) return a

Complexité : O(h), avec \log_2 n \le h \le n-1.

Méthode type bac

1. Vérifier/exploiter la propriété d'ordre pour orienter la descente (gauche si plus petit). 2. Toujours structurer les fonctions en cas de base None + récursion. 3. Pour un parcours infixe, écrire : parcourir gauche, traiter racine, parcourir droit. 4. Distinguer le meilleur cas (équilibré) du pire (filiforme) pour la complexité.

Pièges

  • Oublier le cas None : AttributeError sur a.valeur.
  • Confondre les trois parcours : seule la place de la racine change.
  • Croire que la recherche dans un ABR est toujours en O(\log n) : c'est O(n) si l'arbre est dégénéré.
  • Dans l'insertion, ne pas renvoyer a (la racine) après modification : l'arbre se perd.

Pour l'épreuve

L'ABR est un classique de l'écrit et de l'épreuve pratique : insertion, recherche, parcours infixe trié, calcul de hauteur, valeur minimale (à gauche) ou maximale (à droite). Sachez tracer l'arbre obtenu après une suite d'insertions et donner son parcours infixe pour vérifier qu'il est bien trié. Justifiez toujours la complexité par la hauteur de l'arbre, en distinguant le cas équilibré du cas filiforme. La rédaction récursive structurée (cas de base None + appels récursifs orientés par la comparaison à la valeur du nœud) est attendue et notée ; n'oubliez pas de renvoyer la racine après une insertion modifiante, faute de quoi l'arbre est perdu.