Arbres binaires de recherche


Notion darbre binaire de recherche (ABR)

Hauteur et équilibre dun arbre binaire

Nous avons étudié dans le dernier paragraphe du chapitre précédent la relation entre la taille \(N\) de larbre cest-à-dire le nombre de noeuds et sa hauteur \(h\), qui est la longueur du plus long chemin allant de la racine de larbre à lune de ses feuilles. Cest aussi le nombre de niveaux de larbre lorsquil est représenté graphiquement.

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

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

    arbre parfait

  • Si à linverse larbre a une structure filaire (par exemple un peigne à gauche ou à droite), on aura

    \[ h = N\]

    arbre filaire

On a représenté ci-dessus deux arbres comportant 15 noeuds: lun est parfait, lautre filaire.

Dans la pratique, tout arbre binaire se situera quelque part entre ces deux extrémités. Plus larbre sera équilibré, plus il se rapprochera dun arbre parfait et plus sa hauteur se rapprochera de la valeur \(\log_2(N)\). À linverse, plus larbre 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 deffectuer un parcours de larbre, jusquà trouver lélément recherché ou bien se rendre compte quil ny est pas. Cela nécessite comme pour une recherche dans un tableau ou une liste de parcourir dans le pire des cas lintégralité de la structure de donnée. On a donc nécessairement un algorithme linéaire.

Dans le cas dun tableau ou dune 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 dun arbre binaire, on ne peut pas non plus faire mieux que cela, à moins de disposer dinformations supplémentaires.

Plus précisément, si larbre est relativement équilibré et quà chaque étape de la recherche on dispose dun 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 larbre.

Autrement dit, on pourra avoir un algorithme dont la complexité est proportionnelle à \(\log_2(N)\) plutôt quun algorithme linéaire. Cest 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, cest-à-dire comment contraindre un arbre binaire afin quil offre des performances proches de celles dune recherche dichotomique, et ce sans avoir besoin deffectuer un tri préalable (qui est lui-même bien plus coûteux quune recherche dichotomique).

Définition dun ABR

Définition: Un arbre binaire de recherche (ABR):

  • est un arbre binaire;
  • contient des valeurs qui sont comparables, cest-à-dire des valeurs qui peuvent être comparées à laide de lopérateur \(<\) et ses variantes;
  • satisfait à la contrainte supplémentaire que, pour chaque noeud de valeur \(x\), tous les noeuds de valeurs strictement inférieure à \(x\) se touvent dans le sous-arbre à gauche et tous les noeuds de valeurs strictement supérieures à \(x\) se trouvent dans le sous-arbre à droite.

Remarquons que la contrainte supplémentaire imposée à lABR ne permet pas de stocker des doublons en son sein. Si avoir des doublons est important, on peut sen 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 lon effectue une recherche, ce qui nuira à la complexité des algorithmes (dans le pire des cas, on pourrait avoir les mêmes performances quavec un arbre binaire quelconque, cest-à-dire un algorithme linéaire).

Pour toute la suite du chapitre, nous choisirons arbitrairement la première possibilité: un ABR sera un arbre binaire pour lequel toutes les valeurs strictement inférieures à \(x\) seront dans le sous-arbre à gauche et toutes les valeurs supérieures ou égales à \(x\) seront dans le sous-arbre à droite.

Notre définition autorise donc le stockage de doublons dans larbres.

Voici un exemple dABR:

exemple 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 dailleurs deux fois dans larbre).

Non seulement cette propriété est vérifiée pour la racine, mais on peut constater quelle est vraie pour tout noeud de larbre: cest une condition nécessaire pour avoir un ABR.

Rechercher un élément dans un ABR

Un premier exemple

Prenons lABR ci-dessous:

Il sagit structurellement dun arbre parfait, mais cest aussi un ABR: les 15 valeurs stockées satisfont bien aux contraintes dordre.

Recherche de la valeur 11

Sur le schéma ci-dessous, on a mis en évidence les noeuds quil est nécessaire dexaminer pour rechercher la valeur 11, qui est bien contenue dans larbre.

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 larbre.

Recherche de la valeur 42

Sur le schéma ci-dessous, on a mis en évidence les noeuds quil est nécessaire dexaminer pour rechercher la valeur 42, qui nest pas dans larbre.

  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 sarrête donc, et est infructueuse !

Lorsque la valeur recherchée nest pas dans larbre, la recherche sarrêtera négativement dès lors que lon arrivera sur un noeud vide. Comme larbre est ici parfait, on a besoin dexaminer 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:

Algorithme de recherche dans un ABR:

En partant de la racine, on procède pour chaque noeud comme suit:

  • Si on est sur un noeud vide, cest que la valeur recherchée nest pas dans larbre (voir lexemple suivant pour rencontrer concrètement ce cas);
  • Sinon, deux cas exactement peuvent se présenter:
    • Si la valeur du noeud est égale à la valeur recherchée, on a terminé la recherche avec succès !
    • Sinon, si la valeur à rechercher \(y\) est strictement inférieure à la valeur du noeud courant \(x\), alors on part dans le sous-arbre à gauche;
    • Sinon, la valeur à rechercher \(y\) est nécessairement supérieure ou égale à la valeur du noeud courant \(x\), et on part dans ce cas dans le sous-arbre à droite.

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

Implémentation de cet algorithme

Lalgorithme décrit précédemment se traduit presque mot pour mot en python, à laide dune 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 laspect mutuellement exclusif des conditions, garantissant quun chemin unique sera choisi à chaque étape.

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

Construire un ABR

Lexemple de la partie précédente était quasiment idéal, dans le sens où lABR était structurellement parfait.

Si à linverse on avait choisi un ABR entièrement filaire (cest toujours possible, comme nous le verrons en TP), on aurait eu une recherche banalement linéaire, exactement comme si lon 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 lon dispose déjà dun ABR. Comment faire pour insérer une nouvelle valeur (homogène à celles qui sont déjà stockées dans larbre) ?

Lalgorithme suivant réalise cela, en recherchant récursivement la position dans laquelle on pourra insérer la nouvelle valeur (exactement comme pour lalgorithme 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 lABR:

  • 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 lancien 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 lancien sous-arbre à gauche et à droite vers le nouveau sous-arbre à droite.

Cet algorithme renvoie donc une copie de larbre initial, augmenté dun nouveau noeud de valeur \(v\) placé au bon endroit , de façon à ce quil 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 limpact de cet algorithme sur un ABR.

  • On part de lABR 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):

Important: Cet algorithme dinsertion place une valeur donnée à lemplacement du premier noeud vide que lon aurait rencontré avec lalgorithme de recherche (légèrement modifié pour quil ne sinterrompe pas lorsque lon rencontre la valeur que lon cherche à insérer ce qui revient à retirer le cas dégalité).

Linsertion donne-t-elle un arbre équilibré ?

Il sagit dune question légitime. Dans lexemple précédent, larbre obtenu après quatre insertions restait relativement équilibré (mais notons néanmoins que lon a un arbre de profondeur 5 pour 11 valeurs, alors quun 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 lordre dinsertion:

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

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

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

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

Nous ferons en TP une étude statistique sur linsertion aléatoire, avec laquelle on peut conjecturer que la profondeur moyenne est de lordre de \(2\times \log_2(N)\), ce qui reste proportionnel à \(\log_2(N)\), mais demanderait une étude mathématique poussée que nous ne ferons évidemment pas en Terminale. Ce genre détude est toujours du domaine de la recherche, des articles ont été publiés il y a moins de 20 ans sur le sujet.

Complexité et équilibre

On peut montrer que, sous réserve davoir un arbre proche dun arbre équilibré, lordre de grandeur de lalgorithme de recherche (ainsi que dautres algorithmes sur les ABR) reste proportionnel à \(\log_2(N)\), ce qui est aussi performant quune 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 dobtenir un ABR équilibré, mais il existe des moyens plus systématiques:

  • les AVL garantissent que larbre sera quasiment équilibré (la différence de hauteur entre les sous-arbres à gauche et à droite est dau 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.

Dautres algorithmes sur les ABR

Recherche du minimum et du maximum

Déterminer si un arbre binaire est un ABR