Arbres binaires


Les tableaux ou les listes (quelles soient chaînées ou des listes python) sont des structures séquentielles: elles ont vocation à être utilisées dès lors quil est possible dindexer les valeurs que lon souhaite représenter, à linstar 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: lorganigramme hiérarchique dune entreprise, la structure des répertoires sur un disque dur, la classification des espèces en biologie, etc sont des structures hiérarchiques que lon représentera plus aisément à laide dun arbre.

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

Quest-ce quun arbre binaire

Définition

Un arbre binaire est un cas particulier dune 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;
  • Sil nest pas vide, il possède un noeud particulier appelé noeud racine;
  • Tous les autres noeuds de labre 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;

arbre binaire

Dans la figure ci-dessus, on a représenté la structure dun arbre binaire comportant 12 noeuds. Lorsquil ny 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 lunique sous-arbre est à gauche ou à droite.

Quelques noeuds ont des noms particuliers:

Définitions:

  • Le premier noeud composant larbre est appelé racine, comme nous lavons vu plus haut;
  • Tout noeud situé à lopposé de la racine et nayant ni sous-arbre à gauche ni sous-arbre à droite sera appelé une feuille;
  • Les liens entre les noeuds sont appelés des branches.

arbre annotations

Taille et hauteur

À tout arbre (quils soient dailleurs binaires ou non) sont attachées deux notions importantes:

Définitions:

  • La taille dun arbre est le nombre de noeuds quil contient;
  • La hauteur dun arbre est le nombre maximal de noeuds rencontrés de la racine à une feuille quelconque de larbre.

Lillustration 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 linformation

Sil navait que sa structure, un arbre naurait quun intérêt limité. Heureusement, un arbre prend tout son potentiel lorsquil permet de stocker de linformation (tout comme une tableau, une liste, un dictionnaire).

Concrètement, à chaque noeud on associera une valeur. Ces valeurs peuvent être dun 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 lon a besoin de données hétérogènes).

arbre avec information

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

Quelques arbres particuliers

Arbres parfaits

Définition: Un arbre binaire est parfait lorsque, pour une hauteur \(h\) donnée, le nombre de noeuds est maximal.

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

arbre parfait

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

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

Dans lexemple 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

À lopposé des arbres parfaits, nous avons les arbres filaires pour lesquels on ne trouvera à chaque noeud quun unique fils (excepté pour les feuilles bien entendu).

Définitions:

  • Un peigne à gauche est un arbre filaire nayant que des embranchements à gauche;

  • Un peigne à droite est un arbre filaire nayant que des embranchements à droite;

Un peigne est à lopposé dun arbre parfait dans le sens où sa hauteur est égale à sa taille. Cest un arbre le plus déséquilibré possible, car il ny a jamais de noeuds ayant 2 fils.

Important: Nous verrons en TP et surtout dans le chapitre suivant (sur les arbres binaires de recherche) que la recherche de léquilibre est très importante, car elle réduit considérablement la complexité des algorithmes.

Implémentation dun arbre binaire

Tout comme la Cellule était indispensable à limplémentation des listes chaînées, ici cest le Noeud qui permettra de définir une structure darbre 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 dimplémenter un noeud en python (et de loin) est dutiliser 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 quun arbre vide sera représenté par la valeur None.

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

arbre détaillé

Lorsquil ny a pas de sous-arbre, les attributs correspondants valent None, mais cela na 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 lorsquils sont vides (None). Larbre précédent peut alors être créé grâce à linstruction:

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 nest pas très lisible (il est cependant possible dutiliser des indentations si nécessaire). Mais dans la pratique, cela nest guère important, il est très rare de créer à la main des arbres aussi grands. Les arbres dont nous aurons lusage seront presque toujours le résultat dun algorithme, selon le problème que lon cherche à résoudre.

Algorithmes fondamentaux

Il existe de nombreux algorithmes liés aux arbres binaires. Nous nen étudierons quune 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 dun arbre, parcours dun arbre).

Dautres 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 dun arbre binaire

Calculer la taille dun arbre binaire peut se faire récursivement:

  • Condition darrêt: Un arbre vide a une taille nulle;
  • Si larbre nest pas vide:
    • On calcule la taille des sous-arbres gauche et droite;
    • On ajoute ces deux entiers, que lon 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 dun arbre binaire

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

  • Condition darrêt: Un arbre vide a une hauteur nulle;
  • Si larbre nest pas vide:
    • On calcule la hauteur des sous-arbres gauche et droite;
    • On conserve la plus grande de ses deux hauteurs, et on lincré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 dun arbre binaire

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

  • Si on traite dabord 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 à laide dune fonction qui affiche (dans la console) les valeurs dun arbre binaire.

Important: Notez que, entre ces trois algorithmes, seule la position de la ligne print(a.valeur) change.

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 préfixe

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 infixe

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

parcours postfixe

Les algorithmes de calcul de la taille et de la hauteur sont, conceptuellement, des parcours postfixe de larbre puisque lon calcule dabord les tailles (ou les hauteurs) des deux sous-arbres, avant den déduire la taille (ou la hauteur) de larbre représenté par la racine.

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

Il est toujours important de se demander à quel moment on doit effectuer le traitement du noeud racine. Cela déterminera le type de parcours à effectuer.

Minimum et maximum dun arbre binaire

Afin que la recherche dun extremum ait un sens, on doit supposer que les valeurs (homogènes) stockées dans larbre sont comparables, cest-à-dire quil est possible de les comparer à laide des opérateurs \(<\), \(>\), \(\leqslant\) ou bien \(\geqslant\). Cela sappliquera 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.

Un arbre contenant des dictionnaires peut paraître absurde ? Il nen est rien: par exemple le format de représentation de données json très utilisé de nos jours est naturellement arborescent (cest-à-dire que lon peut le représenter sous la forme dun arbre, même non binaire), et contient souvent des dictionnaires (au sens python du terme).

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

  • Condition darrêt: Si on a une feuille, la valeur du noeud est le maximum (ou le minimum)
  • Si le noeud nest 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 (sils sont non vides).
    • Si lun ou lautre 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 larbre, 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 lalgorithme.

Notons que la condition darrêt nest pas pour une fois le fait davoir un noeud vide, car la notion de maximum ou de minimum ne sapplique pas à un arbre vide.

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 quil y avait une relation très forte entre la taille \(N\) dun arbre et sa hauteur \(h\), selon que lon est dans lun 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 saperçoit quil est et de très loin beaucoup plus intéressant davoir un arbre proche dun arbre parfait, car les algorithmes de parcours précédents (quils soient pré-, in- ou postfixes) auront une pile dappel ayant au plus \(\log_2(N+1)\) empilements.

Prenons un exemple numérique: si larbre contient \(N = 100\,000\) noeuds (ce qui nest 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 nexplorent quune unique branche à la fois. Notamment, rechercher un élément dans une telle situation ne nécessiterait que 17 appels au maximum, alors quil y a \(100\,000\) données stockées dans larbre.

On peut atteindre des performances similaires à celle dune recherche dichotomique.