---

Les tableaux ou les listes (qu’elles soient chaînées ou des listes python) sont des structures séquentielles: elles ont vocation à être utilisées dès lors qu’il est possible d’indexer les valeurs que l’on souhaite représenter, à l’instar des suites mathématiques \((u_n)_{n\in\mathbb N}\).

Cependant, de nombreuses structures du monde qui nous entourent ne se prêtent pas facilement à une énumération, mais plutôt à une hiérarchisation: l’organigramme hiérarchique d’une entreprise, la structure des répertoires sur un disque dur, la classification des espèces en biologie, etc… sont des structures hiérarchiques que l’on représentera plus aisément à l’aide d’un arbre.

Nous étudierons brièvement la structure générale d’arbre dans un chapitre futur. Les arbres binaires sont un type particulier d’arbres.

Qu’est-ce qu’un arbre binaire

Définition

Un arbre binaire est un cas particulier d’une structure arborescente pour laquelle chaque position (appelée noeud en langage informatique) ne peut aboutir qu’à un maximum de deux autres positions.

Plus précisément:

• Un arbre binaire peut être vide;
• S’il n’est pas vide, il possède un noeud particulier appelé noeud racine;
• Tous les autres noeuds de l’abre sont séparés en deux sous-ensembles, appelés le sous-arbre gauche et le sous-arbre droit;
• Chaque noeud est relié à un maximum de deux autres noeuds, qui sont respectivement les racines du sous-arbre gauche et du sous-arbre droit;

Dans la figure ci-dessus, on a représenté la structure d’un arbre binaire comportant 12 noeuds. Lorsqu’il n’y a pas de sous-arbre à gauche ou à droite, on représente une liaison plus claire ne pointant sur rien. Cela permet notamment de savoir si l’unique sous-arbre est à gauche ou à droite.

Quelques noeuds ont des noms particuliers:

Taille et hauteur

À tout arbre (qu’ils soient d’ailleurs binaires ou non) sont attachées deux notions importantes:

L’illustration précédente représente un arbre de taille 12 et de hauteur 6 (obtenue en suivant le chemin partant de la racine et empruntant toujours la branche droite jusqu’à la dernière feuille en bas à droite).

Un arbre contient de l’information

S’il n’avait que sa structure, un arbre n’aurait qu’un intérêt limité. Heureusement, un arbre prend tout son potentiel lorsqu’il permet de stocker de l’information (tout comme une tableau, une liste, un dictionnaire…).

Concrètement, à chaque noeud on associera une valeur. Ces valeurs peuvent être d’un type quelconque (entier, nombre à virgule flottante, chaîne de caractère, tableau, tuple, etc), mais on ne considérera que des arbres dont les types sont homogènes, exactement comme pour les tableaux ou les listes (mais pas les tuples qui sont spécifiquement là lorsque l’on a besoin de données hétérogènes).

Dans cet exemple, l’arbre précédent associe à chaque noeud un entier aléatoire compris entre 1 et 100.

Quelques arbres particuliers

Arbres parfaits

Un arbre parfait est parfaitment équilibré: chaque noeud (sauf les feuilles) ont toujours et systématiquement deux noeuds fils.

On peut montrer que le nombre \(N\) de noeuds d’un arbre parfait (c’est-à-dire sa taille) est toujours égal à:

\[ 1 + 2 + 4 + \cdots + 2^{h-1} = 2^h - 1\]

Dans l’exemple ci-dessus, on a un arbre parfait de hauteur 4. Le nombre de noeuds est bien:

\[ 1 + 2 + 4 + 8 = 15 = 2^4 - 1\]

Peignes

À l’opposé des arbres parfaits, nous avons les arbres filaires pour lesquels on ne trouvera à chaque noeud qu’un unique fils (excepté pour les feuilles bien entendu).

Un peigne est à l’opposé d’un arbre parfait dans le sens où sa hauteur est égale à sa taille. C’est un arbre le plus déséquilibré possible, car il n’y a jamais de noeuds ayant 2 fils.

Implémentation d’un arbre binaire

Tout comme la Cellule était indispensable à l’implémentation des listes chaînées, ici c’est le Noeud qui permettra de définir une structure d’arbre binaire.

Concrètement, un noeud doit contenir:

• Un sous-arbre gauche (éventuellement vide);
• Une valeur;
• Un sous-arbre droit (éventuellement vide);

On pourrait représenter un noeud par un tuple (gauche, valeur, droit) ou bien un tableau [gauche, valeur, droit] (encore que ce dernier ne serait probablement pas homogène, ce qui pose conceptuellement un problème), mais la manière la plus naturelle d’implémenter un noeud en python (et de loin) est d’utiliser la POO.

On définit donc une classe Noeud contenant 3 attributs:

• Noeud.gauche qui contient le sous-arbre à gauche;
• Noeud.valeur qui contient la valeur;
• Noeud.droite qui contient le sous-arbre à droite;

On convient qu’un arbre vide sera représenté par la valeur None.

Voici une représentation de l’arbre précédent où on a mis en évidence ces 3 attributs pour chaque noeud:

Lorsqu’il n’y a pas de sous-arbre, les attributs correspondants valent None, mais cela n’a pas été représenté pour ne pas alourdir la figure.

Une implémentation rudimentaire de la classe Noeud peut être celle-ci:

class Noeud:
   def __init__(self, valeur, gauche=None, droite=None):
      self.valeur = valeur
      self.gauche = gauche
      self.droite = droite

Notons que les paramètres par défaut pour les sous-arbres à gauche ou à droite permettent de ne rien mettre lorsqu’ils sont vides (None). L’arbre précédent peut alors être créé grâce à l’instruction:

a = Noeud(3, Noeud(83, droite=Noeud(56, gauche=Noeud(49, Noeud(41), Noeud(89, droite=Noeud(57, Noeud(28), Noeud(31, droite=Noeud(58, gauche=Noeud(45)))))))), Noeud(32))

Ce code n’est pas très lisible (il est cependant possible d’utiliser des indentations si nécessaire). Mais dans la pratique, cela n’est guère important, il est très rare de créer à la main des arbres aussi grands. Les arbres dont nous aurons l’usage seront presque toujours le résultat d’un algorithme, selon le problème que l’on cherche à résoudre.

Algorithmes fondamentaux

Il existe de nombreux algorithmes liés aux arbres binaires. Nous n’en étudierons qu’une petite partie, parmis les algorithmes les plus fondamentaux.

Certains de ces algorithmes fondamentaux sont liés à la structure de ces arbres, et ne tiennent pas du tout compte des valeurs (taille et hauteur d’un arbre, parcours d’un arbre).

D’autres au contraire portent à la fois sur les valeurs et la structure (recherche des extremums par exemple), et nécessitent souvent une condition supplémentaire (notamment le fait que les valeurs soient comparables).

Taille d’un arbre binaire

Calculer la taille d’un arbre binaire peut se faire récursivement:

• Condition d’arrêt: Un arbre vide a une taille nulle;
• Si l’arbre n’est pas vide:
  • On calcule la taille des sous-arbres gauche et droite;
  • On ajoute ces deux entiers, que l’on incrémente ensuite pour tenir compte de la racine.

def taille(a):
   if a is None:
      return 0
   else:
      taille_gauche = taille(a.gauche)
      taille_droite = taille(a.droite)

      return 1 + taille_gauche + taille_droite

Hauteur d’un arbre binaire

Calculer la hauteur fonctionne quasiment de la même manière:

• Condition d’arrêt: Un arbre vide a une hauteur nulle;
• Si l’arbre n’est pas vide:
  • On calcule la hauteur des sous-arbres gauche et droite;
  • On conserve la plus grande de ses deux hauteurs, et on l’incrémente de 1 pour tenir compte de la racine.

def hauteur(a):
   if a is None:
      return 0
   else:
      hauteur_gauche = hauteur(a.gauche)
      hauteur_droite = hauteur(a.droite)

      return 1 + max(hauteur_gauche, hauteur_droite)

Parcours d’un arbre binaire

La grande similitude entre les deux algorithmes précédents n’est pas due au hasard: dans les deux cas, on effectue un parcours de l’arbre. Il existe 3 types de parcours, selon le moment où l’on va traiter le noeud racine:

• Si on traite d’abord le noeud racine, puis le sous-arbre à gauche suivi du sous-arbre à droite, on a un parcours préfixe.
• Si on traite le noeud racine entre le parcours récursif du sous-arbre à gauche et du sous-arbre à droite, on a un parcours infixe.
• Enfin, si le traitement du noeud racine arrive après avoir parcouru les deux sous-arbres, on a un parcours postfixe.

Illustrons ces trois notions à l’aide d’une fonction qui affiche (dans la console) les valeurs d’un arbre binaire.

Parcours préfixe

def parcours_préfixe(a):
   if a is None:
      return
   else:
      print(a.valeur)
      parcours_préfixe(a.gauche)
      parcours_préfixe(a.droite)

a = Noeud(1, Noeud(2), Noeud(3))

parcours_préfixe(a)

Ce programme affichera alors:

A
B
C

On a illustré sur la figure ci-dessous le parcours: suivre la ligne bleue du début jusqu’à la fin. Les ronds rouges marquent le moment où un noeud est affiché.

Parcours infixe

def parcours_infixe(a):
   if a is None:
      return
   else:
      parcours_infixe(a.gauche)
      print(a.valeur)
      parcours_infixe(a.droite)

a = Noeud(1, Noeud(2), Noeud(3))

parcours_infixe(a)

Ce programme affichera alors:

B
A
C

Parcours postfixe

def parcours_postfixe(a):
   if a is None:
      return
   else:
      parcours_postfixe(a.gauche)
      parcours_postfixe(a.droite)
      print(a.valeur)

a = Noeud(1, Noeud(2), Noeud(3))

parcours_postfixe(a)

Ce programme affichera alors:

B
C
A

Les algorithmes de calcul de la taille et de la hauteur sont, conceptuellement, des parcours postfixe de l’arbre puisque l’on calcule d’abord les tailles (ou les hauteurs) des deux sous-arbres, avant d’en déduire la taille (ou la hauteur) de l’arbre représenté par la racine.

D’autres algorithmes utiliseront plutôt un parcours préfixe ou infixe, selon le cas.

Minimum et maximum d’un arbre binaire

Afin que la recherche d’un extremum ait un sens, on doit supposer que les valeurs (homogènes) stockées dans l’arbre sont comparables, c’est-à-dire qu’il est possible de les comparer à l’aide des opérateurs \(<\), \(>\), \(\leqslant\) ou bien \(\geqslant\). Cela s’appliquera donc naturellement aux entiers, aux flottants, aux chaînes de caractères, ou à des tuples (à condition que les composantes du tuples soient elles-mêmes comparables), mais pas à des dictionnaires par exemple.

Pour rechercher un maximum (ou un minimum), on procède comme pour la recherche du maximum dans un tableau:

• Condition d’arrêt: Si on a une feuille, la valeur du noeud est le maximum (ou le minimum)
• Si le noeud n’est pas vide:
  • On initialise la variable maxi avec la seule valeur dont on dispose: la valeur du noeud courant;
  • On cherche les maximum des sous-arbres à gauche et à droite (s’ils sont non vides).
  • Si l’un ou l’autre des maximum est plus grand que la variable maxi, on ajuste la valeur de cette dernière.

On aura donc ici plutôt un parcours préfixe de l’arbre, car la valeur du noeud courant est traitée en premier.

Évidemment, pour rechercher le minimum il suffit de remplacer plus grand par plus petit dans le dernier point de l’algorithme.

On obtient alors:

def maximum(a):
   if a.gauche is None and a.droite is None:
      # C'est une feuille !
      return a.valeur
   else:
      maxi = a.valeur
      if a.gauche not is None:
         maxi = max(maxi, maximum(a.gauche))
      if a.droite not is None:
         maxi = max(maxi, maximum(a.droite))

      return maxi

def minimum(a):
   if a.gauche is None and a.droite is None:
      # C'est une feuille !
      return a.valeur
   else:
      mini = a.valeur
      if a.gauche not is None:
         mini = min(mini, minimum(a.gauche))
      if a.droite not is None:
         mini = min(mini, minimum(a.droite))

      return mini

Relation entre la taille et la hauteur

On a déjà vu qu’il y avait une relation très forte entre la taille \(N\) d’un arbre et sa hauteur \(h\), selon que l’on est dans l’un des cas extrême:

• Avec un arbre parfait, on a \(N = 2^h - 1\), ce qui peut aussi s’écrire \(2^h = N + 1\), ou encore

  \[ h = \log_2(N + 1) \approx \log_2(N)\]

• Au contraire, avec un arbre filaire, on a simplement

  \[ h = N\]

Le logarithme de base 2 croissant très lentement avec la taille de \(N\), on s’aperçoit qu’il est — et de très loin — beaucoup plus intéressant d’avoir un arbre proche d’un arbre parfait, car les algorithmes de parcours précédents (qu’ils soient pré-, in- ou postfixes) auront une pile d’appel ayant au plus \(\log_2(N+1)\) empilements.

Prenons un exemple numérique: si l’arbre contient \(N = 100\,000\) noeuds (ce qui n’est pas déraisonnable à l’époque du big data), alors un arbre très équilibré aura une hauteur qui se rapprochera de \(h \approx \log_2(100\,000) \approx 17\) par arrondi à la valeur supérieure.

Cela prendra toute son importance au chapitre suivant, où on utilisera des parcours optimisés qui n’explorent qu’une unique branche à la fois. Notamment, rechercher un élément dans une telle situation ne nécessiterait que 17 appels au maximum, alors qu’il y a \(100\,000\) données stockées dans l’arbre.

On peut atteindre des performances similaires à celle d’une recherche dichotomique.