---

Notion d’arbre binaire de recherche (ABR)

Hauteur et équilibre d’un arbre binaire

Nous avons étudié dans le dernier paragraphe du chapitre précédent la relation entre la taille \(N\) de l’arbre — c’est-à-dire le nombre de noeuds — et sa hauteur \(h\), qui est la longueur du plus long chemin allant de la racine de l’arbre à l’une de ses feuilles. C’est aussi le nombre de niveaux de l’arbre lorsqu’il est représenté graphiquement.

• Si l’arbre est parfaitement équilibré (on dit dans ce cas que l’arbre est parfait), alors on a

  \[ h \approx \log_2(N)\]

  

• Si à l’inverse l’arbre a une structure filaire (par exemple un peigne à gauche ou à droite), on aura

  \[ h = N\]

  

On a représenté ci-dessus deux arbres comportant 15 noeuds: l’un est parfait, l’autre filaire.

Dans la pratique, tout arbre binaire se situera quelque part entre ces deux extrémités. Plus l’arbre sera équilibré, plus il se rapprochera d’un arbre parfait et plus sa hauteur se rapprochera de la valeur \(\log_2(N)\). À l’inverse, plus l’arbre sera filaire (et donc déséquilibré), plus sa hauteur tendra à se rapprocher de sa taille.

Rechercher dans un arbre binaire

Comment rechercher un élément dans un arbre binaire ? Il suffit a priori d’effectuer un parcours de l’arbre, jusqu’à trouver l’élément recherché ou bien se rendre compte qu’il n’y est pas. Cela nécessite — comme pour une recherche dans un tableau ou une liste — de parcourir dans le pire des cas l’intégralité de la structure de donnée. On a donc nécessairement un algorithme linéaire.

Dans le cas d’un tableau ou d’une liste — et en dehors de toute autre contrainte comme par exemple lorsque le tableau est déjà trié — on ne peut pas faire mieux que cette recherche linéaire.

Si on dispose d’un arbre binaire, on ne peut pas non plus faire mieux que cela, à moins de disposer d’informations supplémentaires.

Plus précisément, si l’arbre est relativement équilibré et qu’à chaque étape de la recherche on dispose d’un moyen de choisir à coup sûr le sous-arbre à gauche ou bien le sous-arbre à droite, alors on a la garantie de terminer notre recherche (positivement ou non) en un nombre d’étapes inférieur ou égal à la hauteur \(h\) de l’arbre.

Autrement dit, on pourra avoir un algorithme dont la complexité est proportionnelle à \(\log_2(N)\) plutôt qu’un algorithme linéaire. C’est exactement ce que nous avions réussi à obtenir avec la recherche dichotomique.

Nous allons précisément étudier dans ce chapitre comment obtenir de telles conditions, c’est-à-dire comment contraindre un arbre binaire afin qu’il offre des performances proches de celles d’une recherche dichotomique, et ce sans avoir besoin d’effectuer un tri préalable (qui est lui-même bien plus coûteux qu’une recherche dichotomique).

Définition d’un ABR

Remarquons que la contrainte supplémentaire imposée à l’ABR ne permet pas de stocker des doublons en son sein. Si avoir des doublons est important, on peut s’en sortir de trois manières:

• On autorise les valeurs supérieures ou égales à \(x\) dans le sous-arbre à droite:

  

• On autorise les valeurs inférieures ou égales à \(x\) dans le sous-arbre à gauche:

  

• On autorise les doublons indifféremment à gauche ou à droite, ce qui est bien plus symétrique:

  

Cette dernière possibilité est tout aussi symétrique que celle avec les inégalités strictes, mais elle a le désavantage de ne pas offrir une route unique lorsque l’on effectue une recherche, ce qui nuira à la complexité des algorithmes (dans le pire des cas, on pourrait avoir les mêmes performances qu’avec un arbre binaire quelconque, c’est-à-dire un algorithme linéaire).

Voici un exemple d’ABR:

On peut constater de visu que toutes les valeurs inférieures à 11 sont dans le sous-arbre à gauche de la racine, alors que le sous-arbre à droite contient des valeurs supérieures ou égales à 11 (la valeur 11 apparaît d’ailleurs deux fois dans l’arbre).

Non seulement cette propriété est vérifiée pour la racine, mais on peut constater qu’elle est vraie pour tout noeud de l’arbre: c’est une condition nécessaire pour avoir un ABR.

Rechercher un élément dans un ABR

Un premier exemple

Prenons l’ABR ci-dessous:

Il s’agit structurellement d’un arbre parfait, mais c’est aussi un ABR: les 15 valeurs stockées satisfont bien aux contraintes d’ordre.

Recherche de la valeur 11

Sur le schéma ci-dessous, on a mis en évidence les noeuds qu’il est nécessaire d’examiner pour rechercher la valeur 11, qui est bien contenue dans l’arbre.

En partant de la racine:

1. Puisque \(11 < 15\), on prend le chemin à gauche;
2. Le noeud suivant a pour valeur 10. Comme \(11 > 10\), on poursuit la recherche vers la droite;
3. On part ensuite à gauche puisque \(11 < 14\);
4. Et on tombe sur un noeud de valeur 11: la recherche est donc terminée avec succès !

Pour le cas de 11, on a pu conclure positivement à la recherche en examinant exactement 4 noeuds sur les 15 que comporte l’arbre.

Recherche de la valeur 42

Sur le schéma ci-dessous, on a mis en évidence les noeuds qu’il est nécessaire d’examiner pour rechercher la valeur 42, qui n’est pas dans l’arbre.

1. On a \(42 > 15\): on part à droite;
2. \(42 < 80\): on part à gauche;
3. \(42 < 75\): on part encore à gauche;
4. \(42 < 55\): on devrait partir à gauche, mais 55 est une feuille: la recherche s’arrête donc, et est infructueuse !

Lorsque la valeur recherchée n’est pas dans l’arbre, la recherche s’arrêtera négativement dès lors que l’on arrivera sur un noeud vide. Comme l’arbre est ici parfait, on a besoin d’examiner exactement 5 noeuds (dont un noeud vide) pour conclure.

Algorithme de recherche dans un ABR

Les deux exemples précédents se généralisent de la manière suivante:

Le point important est que cet algorithme nous fait passer au niveau suivant de l’arbre à chaque étape, ce qui nous garantit que le nombre d’étapes est au maximum égal à la hauteur de l’arbre.

Implémentation de cet algorithme

L’algorithme décrit précédemment se traduit presque mot pour mot en python, à l’aide d’une fonction récursive:

def recherche_ABR(x, a):
   """
   Répond True ou False selon que x est dans l'ABR a ou non.
   """

   if a is None:
      # Condition d'arrêt
      return False
   else:
      if x == a.valeur:
         return True
      elif x < a.valeur:
         return recherche_ABR(x, a.gauche)
      else:
         # x >= a.valeur, forcément
         return recherche_ABR(x, a.droite)

Il apparaît très clairement à la lecture de cette implémentation l’aspect mutuellement exclusif des conditions, garantissant qu’un chemin unique sera choisi à chaque étape.

De ce fait, la complexité dans le pire des cas est proportionnelle à la hauteur \(h\) de l’arbre.

Construire un ABR

L’exemple de la partie précédente était quasiment idéal, dans le sens où l’ABR était structurellement parfait.

Si à l’inverse on avait choisi un ABR entièrement filaire (c’est toujours possible, comme nous le verrons en TP), on aurait eu une recherche banalement linéaire, exactement comme si l’on cherchait une valeur dans un tableau ou bien une liste.

Indépendamment de ces deux cas extrêmes, la question primordiale de comment construire un ABR se pose.

Insérer un élément dans un ABR

Supposons que l’on dispose déjà d’un ABR. Comment faire pour insérer une nouvelle valeur (homogène à celles qui sont déjà stockées dans l’arbre) ?

L’algorithme suivant réalise cela, en recherchant récursivement la position dans laquelle on pourra insérer la nouvelle valeur (exactement comme pour l’algorithme décrit précédemment), puis en reconstruisant des noeuds en remontant jusqu’à la racine. Plus précisément, pour insérer une valeur \(v\), en partant de la racine de l’ABR:

• Si le noeud courant est vide, alors on crée un noeud contenant la valeur \(v\);
• Sinon, deux cas peuvent se produire:
  • Si la valeur \(x\) du noeud vérifie \(v < x\), alors on insère \(v\) dans le sous-arbre à gauche, et on crée un nouveau noeud de valeur \(x\) pointant à gauche vers ce nouvel arbre et à droite vers l’ancien sous-arbre à droite;
  • Sinon, on a nécessairement \(v \geqslant x\), et on insère \(v\) dans le sous-arbre à droite. On crée ensuite un nouveau noeud de valeur \(x\) pointant à gauche sur l’ancien sous-arbre à gauche et à droite vers le nouveau sous-arbre à droite.

Cet algorithme renvoie donc une copie de l’arbre initial, augmenté d’un nouveau noeud de valeur \(v\) placé au bon endroit , de façon à ce qu’il soit encore un ABR.

Voici son implémentation en python:

def insertion_ABR(x, a):
    """
    Insère la nouvelle valeur x dans l'ABR dont la racine est a.
    """

    if a is None:
        return Noeud(x)
    else:
        v = a.valeur

        if x < v:
            # On insère x dans le sous-arbre à gauche
            nouveau_gauche = insertion_ABR(x, a.gauche)
            return Noeud(v, 
                         gauche=nouveau_gauche, 
                         droite=a.droite)
        else:
            # On insère x dans le sous-arbre à droite
            nouveau_droite = insertion_ABR(x, a.droite)
            return Noeud(v, 
                         gauche=a.gauche,
                         droite=nouveau_droite)

Observons l’impact de cet algorithme sur un ABR.

• On part de l’ABR initial ci-dessous:

  

• On insère la valeur 5:

  

• On insère la valeur 1:

  

• On insère la valeur 7:

  

• On insère la valeur 7 (une deuxième fois):

  

L’insertion donne-t-elle un arbre équilibré ?

Il s’agit d’une question légitime. Dans l’exemple précédent, l’arbre obtenu après quatre insertions restait relativement équilibré (mais notons néanmoins que l’on a un arbre de profondeur 5 pour 11 valeurs, alors qu’un arbre parfait de profondeur 4 peut déjà à lui seul contenir 15 valeurs).

Est-ce toujours le cas ?

Prenons pour exemple la situation suivante: on cherche à insérer les chiffres de 0 à 9 dans un arbre vide (qui est un ABR). Quel arbre obtient-on à la fin ? On va voir que cela dépend de l’ordre d’insertion:

• Si on insère les valeurs dans l’ordre croissant, on obtient un peigne à droite:

  

• Si au contraire on insère les valeurs dans l’ordre décroissant, on obtient un peigne à gauche:

  

• Si on mélange aléatoirement les valeurs avant de les insérer dans l’arbre, on peut tomber sur un arbre relativement équilibré. Avec l’ordre d’insertion [2, 6, 0, 1, 5, 4, 3, 9, 8, 7], on obtient par exemple:

  

  Ce n’est pas optimal (profondeur de 5 plutôt que le minimum théorique de 4), mais c’est tout de même bien équilibré.

Complexité et équilibre

On peut montrer que, sous réserve d’avoir un arbre proche d’un arbre équilibré, l’ordre de grandeur de l’algorithme de recherche (ainsi que d’autres algorithmes sur les ABR) reste proportionnel à \(\log_2(N)\), ce qui est aussi performant qu’une recherche dichotomique sur un tableau trié.

Le remplissage aléatoire évoqué au paragraphe précédent donne un début de piste quand à la manière d’obtenir un ABR équilibré, mais il existe des moyens plus systématiques:

• les AVL garantissent que l’arbre sera quasiment équilibré (la différence de hauteur entre les sous-arbres à gauche et à droite est d’au maximum une unité). Les AVL ne sont pas au programme de NSI, mais nous les découvrirons néanmoins en fin de TP;
• Les arbres bicolores sont une autre solution de rééquilibrage automatique des arbres, elle aussi hors programme en NSI.

D’autres algorithmes sur les ABR

Recherche du minimum et du maximum

Déterminer si un arbre binaire est un ABR