Parcourir les arbres et rechercher

Un arbre binaire est vide, ou constitué d’une racine et de deux sous-arbres binaires disjoints, gauche et droit. Les positions gauche et droite sont distinctes : un enfant droit seul n’est pas un enfant gauche. Une feuille est un nœud dont les deux sous-arbres sont vides. Un arbre n’est pas simplement un graphe où chaque sommet possède au plus deux voisins : les relations de parenté et l’absence de cycle comptent.

Nous représentons un arbre vide par None. Un objet Noeud porte trois attributs : cle, gauche et droit. Son constructeur reçoit une clé et, éventuellement, deux sous-arbres. Un nœud n’est pas sa seule valeur ; la clé est une donnée stockée dans cet objet. Les algorithmes doivent tester None avant de lire ses attributs.

Python
class Noeud:
  def __init__(
    self, cle,
    gauche=None, droit=None
  ):
    self.cle = cle
    self.gauche = gauche
    self.droit = droit

La taille est le nombre de nœuds : zéro pour l’arbre vide, sinon un plus les tailles des deux sous-arbres. La hauteur est ici mesurée en arêtes sur le plus long chemin de la racine à une feuille. Une feuille a donc hauteur zéro ; par convention, le vide a hauteur −1. Certains cours comptent les niveaux : annonce toujours ta convention avant de calculer ou de comparer des résultats.

Les définitions deviennent des programmes : taille du vide renvoie zéro ; sur un nœud, renvoie 1 + taille(gauche) + taille(droit). Pour la hauteur, la base renvoie −1, puis on utilise 1 + max(hauteur(gauche), hauteur(droit)). La récursion termine car chaque appel porte sur un sous-arbre strictement plus petit d’un arbre fini.

Les parcours en profondeur explorent entièrement un sous-arbre avant l’autre. La place du traitement de la racine donne leur nom : préfixe pour racine puis gauche puis droit ; infixe pour gauche puis racine puis droit ; suffixe, aussi appelé postfixe, pour gauche puis droit puis racine. À chaque étape, gauche et droit désignent des parcours complets des sous-arbres, pas seulement leurs racines.

Un parcours peut afficher une clé, l’ajouter à une liste ou effectuer un autre traitement. Pour séparer le calcul de l’affichage, construisons une liste resultat reçue comme accumulateur. Le cas vide ne modifie rien. Le programme préfixe ajoute la clé, traite le sous-arbre gauche, puis le droit. Une liste neuve doit être créée avant chaque parcours indépendant.

Python
def prefixe(arbre, resultat):
  if arbre is not None:
    resultat.append(arbre.cle)
    prefixe(arbre.gauche, resultat)
    prefixe(arbre.droit, resultat)

Pour l’infixe, déplace seulement la ligne append entre les deux appels ; pour le suffixe, place-la après les deux appels. Les appels restent gauche puis droit. Le résultat de prefixe n’est pas la liste : la fonction la modifie et renvoie implicitement None. On l’utilise donc avec resultat = [], puis prefixe(arbre, resultat), et on lit ensuite resultat.

Le parcours en largeur visite les niveaux dans leur ordre, de gauche à droite à chaque niveau. Il utilise une file : retirer le plus ancien nœud en attente, le traiter, puis ajouter ses enfants gauche et droit non vides à la fin. Dans la bibliothèque collections, deque propose popleft et append pour ces opérations. Une pile utilisée de la même façon ne conserve pas l’ordre en largeur.

Un arbre binaire de recherche, abrégé ABR, respecte une propriété globale : à chaque nœud, toutes les clés du sous-arbre gauche sont plus petites que sa clé et toutes celles du sous-arbre droit sont plus grandes. Chacun des sous-arbres doit respecter la même propriété. Ici les doublons ne sont pas ajoutés. Une autre politique est possible, mais doit être précisée avant l’algorithme.

Pour rechercher une clé, compare-la à la racine. L’égalité donne un succès. Si elle est plus petite, seule la gauche peut la contenir ; si elle est plus grande, seule la droite reste possible. Atteindre le vide donne un échec. Cette élimination d’un sous-arbre entier est justifiée par l’ordre des clés, pas par la forme visuelle du dessin.

Python
def contient(arbre, cle):
  if arbre is None:
    return False
  if cle == arbre.cle:
    return True
  if cle < arbre.cle:
    return contient(arbre.gauche, cle)
  return contient(arbre.droit, cle)

Insérer reprend le même chemin. À la première position vide, on crée une feuille portant la clé. Si la clé existe déjà, l’arbre reste identique selon notre convention. Une fonction qui renvoie la racine du sous-arbre obtenu permet aussi de traiter l’insertion dans le vide : le programme client doit affecter le résultat à sa variable racine.

Python
def inserer(arbre, cle):
  if arbre is None:
    return Noeud(cle)
  if cle < arbre.cle:
    arbre.gauche = inserer(
      arbre.gauche, cle)
  elif cle > arbre.cle:
    arbre.droit = inserer(
      arbre.droit, cle)
  return arbre

La propriété d’ABR doit être vérifiée pour tous les descendants. Une racine 8, un fils gauche 3 et un fils droit 9 de ce 3 violent la propriété : 9 reste dans le sous-arbre gauche de 8. Les comparaisons entre un parent et ses enfants immédiats ne suffisent donc pas à valider tout l’arbre.

Dans un parcours complet, chaque nœud est traité une fois. Avec un traitement constant par nœud et une représentation sans copie des sous-arbres, le temps est linéaire en la taille. Les parcours récursifs utilisent une pile dont la profondeur dépend de la hauteur. La file du parcours en largeur peut contenir beaucoup de nœuds d’un même niveau.

Recherche et insertion dans un ABR suivent un seul chemin. Pour une hauteur h, elles visitent au plus h + 1 nœuds non vides. Dans un arbre équilibré, la hauteur grandit comme le logarithme du nombre de nœuds et la recherche a un coût logarithmique. Dans une chaîne, elle peut visiter tous les nœuds : le pire coût est linéaire. Le seul nom ABR ne garantit donc pas une recherche logarithmique.

L’ordre d’insertion influence cette forme. Insérer 2 puis 1 puis 3 donne une hauteur 1 ; insérer 1 puis 2 puis 3 donne une chaîne de hauteur 2. Pour de grandes suites déjà triées, la même insertion élémentaire crée une structure très déséquilibrée. Les techniques automatiques d’équilibrage ne sont pas nécessaires ici.

Teste un arbre vide, une feuille, un seul enfant droit, une clé absente et une clé déjà présente. Après une insertion, contrôle le nouvel infixe et la taille. Une séquence croissante obtenue par infixe est un contrôle utile de l’ordre pour des clés distinctes, mais ne prouve pas à elle seule que toutes les opérations d’une bibliothèque sont correctes.