Les arbres binaires de recherche (ABR)

La conclusion des exercices précédents est que la liste semble ne pas tenir la comparaison avec les tableaux. Elle a néanmoins plusieurs avantages : coût d'insertion et de suppression d'un élément en tête ou en queue de liste en temps constant notamment. En revanche le temps de recherche/accès à un élément se fait en temps linéaire, tandis que le tableau peut bénéficier d'une recherche dichotomique en log(n) pour la recherche et d'un temps d'accès constant.

Nous allons donc étudier une structure de données qui permet à une liste de bénéficier d'un coût de recherche, d'insertion et de suppression en log(n) .

Approche naïve

L'approche naïve consiste à considérer un arbre binaire de recherche (ABR) qui est une structure récursive, comme la liste vue précédemment. Contrairement à la liste dont la structure est linéaire, celle de l'arbre est plus complexe. Chaque nœud de l'arbre a deux successeurs : un gauche et un droit.

IllustrationABR

Un nœud de l'arbre binaire de recherche comporte donc une valeur et deux sous-arbres. Le gauche contiendra toutes les valeurs inférieures à celle stockée dans le nœud, le droit toutes les valeurs supérieures.

class ABR:

    def __init__(self, value=None):
        self._value = value
        # self._l et self._ sont de type `Arbre`
        self._l = None
        self._r = None

    @property
    def balance(self) -> int:
       # sera utile plus tard ... ne sert à rien pour l'instant
       return 0

    def __repr__(self) -> str:
        return f'({self._l if self._l is not None else ""}) {self._value}/{self.balance} ({self._r if self._r is not None else ""})'

Si l'affichage linéaire des ABR via __repr__ vous semble trop laborieux, vous pouvez également utiliser la fonction plot() ci-dessous.

def plot(self):
    s = str(self)
    none_string = 'None'
    line = 0
    column = 0
    current = ''
    previous = False
    nodes = {}
    max_width = len(none_string)

    for c in s:
        if c == '(':
            if current:
                current = current.split('/')[0]
                nodes[(line, column)] = current
                previous = False
                if len(current) > max_width:
                    max_width = len(current)
                current = ''
            line += 1
        elif c == ')':
            if not previous:
                column += 1
                nodes[(line, column)] = none_string
                previous = True
            column += 1
            line -= 1
        elif c != ' ':
            previous = True
            current += c

    line = 0
    column = 0
    for pos in sorted(nodes.keys()):
        if pos[0] > line:
            print()
            line = pos[0]
            column = 0

        s = nodes[pos].center(max_width)
        ws = (pos[1]-column)*max_width
        print(' '*ws,s,sep='',end='')
        column = pos[1]+1

1. Exercices préalables

  1. Réalisez la méthode ABR.insert(valeur) -> list qui insère la valeur passée en argument dans l'arbre. Cette fonction renverra une list Python (pas une Liste comme vu précédemment) contenant, dans l'ordre de la feuille à la racine l'ensemble des nœuds parcourus pour faire l'insertion. Ces nœuds correspondent aux parents de celui inséré.

  2. Réalisez la fonction ABR.hauteur() -> int qui calcule la hauteur de l'arbre. On peut définir la hauteur d'un arbre de deux façons :

    • C'est la longueur de la suite de nœuds la plus longue de la racine à un nœud qui n'a pas de successeur.
    • C'est 1 plus la hauteur la plus grande entre les sous-arbres gauche ou droite, sachant qu'un nœud sans successeur a une hauteur de 0.

  3. Réalisez la fonction ABR.nbNoeuds() -> int qui renvoie le nombre de nœuds dans l'arbre.

  4. Réalisez la fonction ABR.contains(valeur) -> bool qui renvoie un booléen selon la présence ou l'absence de valeur dans l'arbre.
  5. Réalisez la fonction ABR.delete(valeur) qui supprime la valeur de l'arbre, ou qui lève une exception de type RuntimeError si la valeur n'est pas dans l'arbre.

Des tests unitaires sont disponibles ici

2. Construction de ArbreTrie

Nous allons refaire le même exercice que celui fait précédemment avec les tableaux et les listes, mais cette fois-ci la collection triée sera gérée par un ABR tel que défini ci-dessus.

  1. Créez maintenant la classe ArbreTrie qui dérive d'CollectionTriee et qui implémente les méthodes insert(), contains() et delete().
  2. Testez votre code.

Analyse de la complexité

Pire cas

Quelle est la forme de l'arbre lorsqu'on crée la liste [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] en insérant les éléments dans l'ordre.

Combien de tests faut-il pour vérifier si 10 est dans l'arbre ?

Est-ce plus efficace ou moins efficace qu'un tableau trié ou une liste triée ?

Meilleur cas

Quelle est la forme de l'arbre lorsqu'on crée la liste [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] en insérant les éléments dans l'ordre suivant : [6, 3, 8, 1, 4, 7, 10, 9]

Combien de tests faut-il pour vérifier si 10 est dans l'arbre ?

Est-ce plus efficace ou moins efficace qu'un tableau trié ou une liste triée ?

Rééquilibrage de l'arbre

On observe, dans les évaluations précédentes qu'un Arbre Binaire de Recherche n'est efficace que lorsqu'il est équilibré. Un arbre est dit équilibré si à tout niveau, le nombre de branches à gauche est équivalent au nombre de branches à droite. En d'autres termes, pour que l'arbre soit équilibré, la hauteur du sous-arbre gauche doit être égale à celle du sous-arbre droit à une unité près.

Arbre AVL

Un arbre AVL est un arbre qui est toujours équilibré avant et après insertion et suppression d'un élément. Pour cela, il sera nécessaire d'implanter des fonctions insert() et delete() adaptées.

  1. Avant de réaliser ces fonctions, complétez la fonction balance() qui était fournie au-dessus, mais qui renvoyait systématiquement zéro. La valeur de retour de balance est égale à la différence entre la hauteur du sous-arbre gauche et celle du sous-arbre droit.

  2. Codez la fonction rotationGauche() La fonction rotationGauche() suppose que self._r existe ainsi que self._r._r. La fonction suppose également que tous les sous-arbres à gauche sont vides, comme indiqué dans l'image ci-dessous. Dans l'illustration ci-dessous, on associe Z à self, Y à self._r et X à self._r._r.

RotationGauche1

près exécution de la fonction la configuration devra ressembler à l'image suivante :

RotationGauche2

Il faut donc :

  a. mémoriser `Z`;

  b. copier `Y` dans `self`

  c. accrocher une copie de `Z` comme sous-arbre gauche à `Y`
  1. Codez la fonction rotationDroite() qui est la symétrique de rotationGauche().

RotationDroite

  1. Généralisez les fonctions rotationGauche() et rotationDroite() afin qu'elles gèrent des sous-arbres non vides, comme illustré ci-dessous pour le cas de la rotationDroite().

RotationDroiteGen

Il est important de noter qu'après une rotation l'arbre résultat reste un Arbre Binaire de Recherche (les valeurs stockées à gauche sont plus petites que les valeurs de la racine, et les valeurs stockées à droite plus grandes)

  1. Quel arbre obtient-on lorsqu'on exécute le code suivant sur l'arbre représenté en dessous ? Dessinez-le.

python Y.rotationDroite() Z.rotationGauche()

DroiteGauche

  1. Quel arbre obtient-on lorsqu'on exécute le code suivant sur l'arbre représenté en dessous ? Dessinez-le.

python Y.rotationGauche() Z.rotationDroite()

GaucheDroite

Insertion dans un arbre AVL

L'insertion dans un arbre AVL et qui garantira l'équilibre de l'arbre est décrit par l'algorithme suivant :

class AVL:
   """
   Faire une insertion classique dans un arbre binaire de recherche. 
   Pour tous les parents de noeud inséré
    - Calculez son hauteur
    - Calculez le niveau d équilibre du parent avec la méthode `balance()`
    - Si le niveau d équilibre est supérieur à 1 alors le noeud est déséquilibré à gauche
    - Si le niveau d équilibre est inférieur à -1 alors le noeud est déséquilibré à droite
      # Il existe au total 4 sortes d'arbre déséquilibré :
      # Gauche-Gauche, Gauche-Droite, Droite-Gauche, Droite-Droite
      # Ils correspondent respectivement aux illustrations des cas 3, 6, 5 et 2 ci-dessus.
    - Rééquilibrer l'arbre avec la combinaison de rotation adaptée.
   """

   def insert(self, value) -> list:
      """
      Insère la valeur `value` dans l'arbre en garantissant qu'il reste équilibré
      :param value: valeur à insérer
      :return: liste des nœuds parcourus pour l'insertion
      """
      lst = super().insert(value)
      rebalance_after_insert(lst)
      return lst

Suppression dans un arbre AVL

... à venir

Temps d'exécution

... à venir

Temps d'exécution AVL