Arbre AVL : guide complet avec implémentation en Python

Déséquilibre dans les arbres binaires de recherche

Les arbres binaires de recherche (BST) sont un type d’arbre binaire structure de données qui organise les données selon un ordre précis. Chaque nœud contient une valeur et possède des liens vers jusqu’à deux autres nœuds : les enfants gauche et droit. Dans un BST, la valeur de l’enfant gauche doit être inférieure à celle de son parent, et la valeur de l’enfant droit doit être supérieure.

Les BST sont très efficaces pour retrouver des valeurs précises, car ils permettent d’éliminer de larges portions de l’arbre pendant la recherche. Par exemple, si nous cherchons la valeur un dans l’arbre ci-dessus, nous pouvons ignorer tous les nœuds à droite de six. En effet, la propriété d’ordre garantit que toutes ces valeurs sont supérieures à six.

Idéalement, chaque nœud doit scinder les données en deux, afin qu’à chaque niveau la moitié des valeurs soit éliminée. On obtient alors des recherches extrêmement rapides. Cependant, selon l’ordre d’insertion, on peut obtenir un arbre déséquilibré qui ne scinde pas efficacement les données. Par exemple, insérer des valeurs de la plus petite à la plus grande produit un arbre linéaire, qui n’est pas meilleur qu’une liste.

Qu’est-ce qu’un arbre AVL ?

Un arbre AVL est un arbre binaire de recherche doté de la propriété supplémentaire suivante :

Pour chaque nœud, la hauteur des sous-arbres gauche et droit diffère d’au plus un.

Décomposons cette définition : le sous-arbre gauche d’un nœud regroupe tous les nœuds situés à sa gauche, tandis que le sous-arbre droit comprend tous les nœuds situés à sa droite. La hauteur d’un arbre est définie comme la longueur du plus long chemin entre la racine (le nœud supérieur) et l’une de ses feuilles (nœuds sans enfants).

Le facteur d’équilibre d’un nœud est calculé comme la différence de hauteur entre son sous-arbre gauche et son sous-arbre droit :

balance(N) = hauteur(sous-arbre gauche de N) - hauteur(sous-arbre droit de N)

Par exemple, balance(6) = 1 - 3 = -2.

Dans le schéma, le nœud 6 présente un facteur d’équilibre de -2, ce qui indique que l’arbre ne respecte pas les critères des arbres AVL. Pour qu’un arbre soit classé AVL, le facteur d’équilibre de chaque nœud doit être -1, 0 ou 1.

Pourquoi utiliser des arbres AVL

L’efficacité des requêtes dans un arbre binaire de recherche dépend de la hauteur de l’arbre. Dans le pire des cas, le nombre de nœuds à examiner est égal à cette hauteur. Un problème clé des BST est que la hauteur peut égaler le nombre de nœuds : une requête peut alors nécessiter d’examiner chaque nœud.

Notons M(h) le nombre minimal de nœuds à ajouter à un arbre binaire de recherche pour atteindre une hauteur h. Pour de simples BST, on observe que M(h) = h : on peut atteindre une hauteur h avec seulement h nœuds. Cela signifie que la hauteur d’un BST peut croître linéairement avec le nombre de nœuds, et donc que le temps de requête est proportionnel à la taille du jeu de données.

Preuve que les arbres AVL ont une hauteur logarithmique

Considérons le nombre minimal de nœuds, M(h), requis pour créer un arbre AVL de hauteur h. Comme il s’agit d’un arbre AVL, il est important de noter que le facteur d’équilibre de chaque nœud ne peut être que -1, 0 ou 1.

Cependant, étant donné notre hypothèse que l’arbre contient le minimum de nœuds pour atteindre la hauteur h, la racine ne peut pas avoir un équilibre de 0. Sinon, on pourrait retirer un nœud à gauche ou à droite pour obtenir un équilibre de -1 ou 1 et conserver un arbre AVL valide.

Supposons que l’équilibre de la racine soit 1 (le raisonnement est identique pour -1). Cela implique que l’arbre est structuré comme suit :

Par ailleurs, les sous-arbres gauche et droit doivent aussi être des arbres AVL, chacun avec le nombre minimal de nœuds pour leurs hauteurs respectives (sinon, on pourrait retirer des nœuds supplémentaires). Le nombre total de nœuds est égal à 1 (pour la racine) plus le nombre de nœuds dans le sous-arbre gauche, plus celui du sous-arbre droit.

M(h) = 1 + (nœuds dans L) + (nœuds dans R) = 1 + M(h - 1) + M(h - 2)

À mesure que la hauteur augmente, il faut ajouter plus de nœuds pour l’atteindre. Donc :

M(h - 1) > M(h - 2)

En combinant les deux, on obtient :

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Nous pouvons appliquer cela h/2 fois jusqu’à atteindre M(1) = 1 ou M(2) = 2 :

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Pour plus de clarté, l’image suivante montre les cas spécifiques h = 7 et h = 6 :

Nous concluons que le nombre minimal de nœuds dans un arbre AVL de hauteur h est au moins 2(h/2) :

M(h) > 2(h/2)

En appliquant le logarithme en base deux des deux côtés, on obtient :

log2(M(h)) > log2(2(h/2)) = h/2

Par conséquent, en multipliant les deux côtés par deux, on déduit que la hauteur est au plus deux fois le logarithme en base 2 du nombre de nœuds :

2 × log2(M(h)) > h

Nous avons montré que :

La hauteur d’un arbre AVL contenant N nœuds est au plus 2 × log2(N).

Cela signifie que les requêtes dans un arbre AVL n’exigent d’examiner qu’une petite partie du jeu de données. Par exemple, pour un milliard d’entrées, le logarithme vaut environ 30 : même avec un milliard de points de données, il suffit d’en examiner environ 60 pour trouver une entrée spécifique. C’est un gain considérable par rapport aux BST qui, dans le pire des cas, imposeraient d’inspecter le milliard complet de points.

Pour approfondir la complexité temporelle des algorithmes et la différence entre complexité linéaire et logarithmique, consultez cet article de blog sur la notation Big-O et la complexité temporelle.

Maintenir l’équilibre avec les arbres AVL

Les arbres AVL garantissent des requêtes rapides en imposant que l’équilibre de chaque nœud soit -1, 0 ou 1. Pour maintenir cet équilibre, il faut rééquilibrer l’arbre après chaque insertion d’une nouvelle valeur.

L’insertion dans un arbre binaire de recherche suit le chemin depuis la racine vers le bas : on va à gauche quand la valeur à insérer est plus petite, sinon à droite.

Une insertion augmente la hauteur d’au plus un. Donc, si la propriété d’équilibre n’est pas respectée après insertion, c’est qu’un nœud avec un équilibre -1 est passé à -2, ou qu’un nœud avec un équilibre 1 est passé à 2. Le premier cas se produit dans l’exemple ci-dessus.

Rotations simples

Pour rétablir l’équilibre, on s’appuie sur des rotations. Une rotation gauche sur le nœud A réorganise l’arbre en faisant pivoter A vers la gauche, comme ci-dessous :

Sur le schéma :

• BL représente le sous-arbre gauche de B
• BR est le sous-arbre droit
• AL est le sous-arbre gauche de A

Notez qu’après rotation, l’ordre des nœuds reste valide :

1. Le nœud A est plus petit que B car B était son enfant droit.
2. Les nœuds de BL sont supérieurs à A car ils étaient à droite de A.
3. Les nœuds de AL sont inférieurs à B puisqu’ils sont inférieurs à A.

Une rotation droite fonctionne de manière symétrique en faisant pivoter A vers la droite.

Voyons un exemple concret en corrigeant le déséquilibre apparu après l’insertion de 19 via une rotation gauche sur le nœud 6.

Après l’insertion, nous corrigeons le déséquilibre en faisant pivoter un nœud dont l’équilibre vaut -2 ou 2. Ici, le facteur d’équilibre du nœud 6 était -2 : l’arbre penchait à droite, nous avons donc appliqué une rotation gauche (dans le sens opposé au déséquilibre). Si l’équilibre vaut 2, on applique une rotation droite.

Rotations doubles

Dans l’exemple précédent, l’arbre penchait totalement à droite, donc une seule rotation gauche suffisait. Mais il existe des déséquilibres en zigzag : l’arbre penche d’un côté, mais le sous-arbre penche de l’autre. Pour l’illustrer, revenons à l’arbre initial, avant l’insertion de 19, et insérons 7 à la place :

Ici, l’arbre penche toujours à droite, mais le sous-arbre enraciné en 10 penche à gauche. On commence donc par faire une rotation droite sur le nœud 10 :

Notez que le nœud B n’a pas d’enfant droit. Nous le laissons en bleu dans le schéma pour faciliter la visualisation.

Après la rotation droite, on retombe dans le cas précédent : une rotation gauche sur 6 rétablit l’équilibre :

Comment implémenter un arbre AVL en Python

Commençons par l’implémentation d’un nœud.

Implémentation du nœud

Chaque nœud de l’arbre possède cinq attributs :

• La valeur stockée (self.value)
• Le nœud parent (self.parent)
• L’enfant gauche (self.left)
• L’enfant droit (self.right)
• La hauteur du sous-arbre enraciné à ce nœud (self.height)

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1

Nous utilisons la valeur None pour représenter les nœuds manquants. La height par défaut est fixée à 1, car un arbre réduit à un seul nœud a une hauteur de 1.

Pour faciliter l’implémentation de l’arbre, nous ajoutons plusieurs méthodes à la classe Node.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self

Notez que nous utilisons les méthodes .set_left() et .set_right() pour affecter respectivement les enfants gauche et droit. Plutôt que de modifier directement self.left et self.right, ces méthodes garantissent qu’à chaque changement d’enfant, le parent du nouvel enfant est mis à jour ainsi que la hauteur du nœud.

Implémentation de l’arbre AVL

L’arbre AVL maintient un paramètre : la racine de l’arbre, c’est-à-dire son nœud supérieur.

class AVLTree:
  def __init__(self):
    self.root = None

Pour maintenir l’équilibre, nous devons implémenter les rotations gauche et droite. Rappelons comment une rotation gauche est illustrée sur le schéma :

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it

Les rotations droites s’implémentent de façon symétrique :

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b

À l’aide des rotations, nous pouvons rééquilibrer l’arbre. Un nœud nécessite un rééquilibrage lorsque son facteur d’équilibre atteint 2 (l’arbre penche à gauche) ou -2 (l’arbre penche à droite). Au total, quatre cas sont à considérer :

Nous implémentons ces quatre cas dans la méthode .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)

Remarquez que chaque cas renvoie la racine du sous-arbre qui vient d’être équilibré. Cette nouvelle racine sera utilisée ensuite pour mettre à jour les enfants pendant le processus de rééquilibrage.

L’ajout d’un nœud à un arbre AVL ressemble à celui d’un BST, avec en plus la restauration de l’équilibre après insertion. Pour ajouter un nœud dans un BST, on part de la racine et on descend dans l’arbre. À chaque étape, on compare la valeur à ajouter à celle du nœud courant : si elle est plus petite, on va à gauche ; sinon, à droite. En descendant, on mémorise le parent pour insérer le nouveau nœud comme enfant.

Une fois un emplacement vide atteint, deux cas se présentent :

1. Le parent est None : l’arbre est vide, le nouveau nœud devient la racine.
2. On a trouvé le parent : on affecte le nouveau nœud à gauche ou à droite selon les valeurs.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)

La seule différence entre la méthode .add() d’un BST et celle d’un arbre AVL tient à l’étape finale : remonter l’arbre depuis le nœud ajouté jusqu’à la racine et rééquilibrer chaque nœud grâce à .rebalance().

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None

Notez que .rebalance() ne fait rien si le nœud est déjà équilibré : elle renvoie simplement ce nœud. C’est pourquoi, en remontant l’arbre, on peut l’appeler des deux côtés, même si un seul peut être déséquilibré. L’autre appel ne change rien.

Rappelons que nous avons conçu .rebalance() pour qu’elle renvoie la (potentielle) nouvelle racine du sous-arbre. Ainsi, en remontant, nous pouvons mettre à jour les enfants gauche et droit des nœuds courants tout en restaurant l’équilibre.

Le schéma suivant illustre les étapes de .restore_balance() en remontant l’arbre.

Dans l’exemple, nous ajoutons d’abord le nœud 8. Le processus de restauration commence alors à ce nœud et remonte l’arbre, en vérifiant et rééquilibrant les enfants gauche et droit de chaque nœud rencontré, jusqu’au nœud 10. Jusqu’à ce point, les appels à .rebalance() n’ont aucun effet, les nœuds restant équilibrés.

En revanche, au niveau du nœud 10, on constate que son enfant gauche, le nœud 7, a un facteur d’équilibre de -2 : un rééquilibrage est nécessaire. L’appel .rebalance(7) remplace alors l’enfant gauche de 10 par la nouvelle racine du sous-arbre gauche, le nœud 8, restaurant l’équilibre.

Opérations supplémentaires sur les arbres AVL

Outre l’ajout et la suppression tout en conservant l’équilibre, les arbres AVL prennent en charge d’autres opérations essentielles.

Minimum et maximum

Grâce à l’ordre des BST, la valeur minimale se trouve au nœud le plus à gauche de l’arbre, et la valeur maximale au nœud le plus à droite.

Nous avons implémenté deux fonctions utilitaires qui identifient les nœuds extrêmes gauche et droit à partir d’un nœud donné. Elles facilitent notamment la suppression de nœuds.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value

Contains

Pour savoir si un arbre contient une valeur donnée, on s’appuie sur la propriété d’ordre : depuis la racine, on part à gauche si la valeur recherchée est inférieure au nœud courant, sinon à droite. Si l’on atteint la fin de l’arbre sans trouver la valeur, c’est qu’elle n’y figure pas.

Pour cela, nous implémentons une méthode utilitaire .locate_node(), utile pour la recherche mais aussi pour la suppression. Nous utilisons également la méthode .__contains__() qui permet d’employer l’opérateur in pour vérifier simplement la présence d’une valeur dans l’arbre.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None

Suppression

Supprimer un nœud dans un arbre AVL peut être délicat lorsqu’il se situe au milieu de l’arbre. S’il s’agit d’une feuille, c’est-à-dire sans enfant, on peut simplement le supprimer en mettant à None le pointeur enfant gauche ou droit de son parent selon le cas.

Cas particulier : si le nœud à supprimer est la racine, on peut l’enlever en définissant la racine à None.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None

Pour supprimer une valeur d’un arbre AVL, on commence par localiser le nœud qui la contient via .locate_node(). Si c’est une feuille, on le retire avec .delete_leaf(). Sinon, une suppression directe casserait la structure : il faut trouver un nœud de remplacement. Si le nœud à supprimer a un enfant gauche, on choisit le nœud le plus à droite de son sous-arbre gauche. Cette approche préserve l’ordre de l’arbre.

Le schéma ci-dessous illustre la suppression du nœud 10. Comme il a un enfant gauche, on le remplace par le nœud le plus à droite du sous-arbre gauche. Après remplacement, il est crucial de rééquilibrer l’arbre en partant du parent du nœud remplacé.

Dans cet exemple, le nœud de remplacement est une feuille. Mais s’il a des enfants, il faut les rattacher au parent du nœud de remplacement. Comme ce nœud est extrême (le plus à gauche ou à droite), il ne peut avoir qu’un seul enfant : ce rattachement est donc toujours possible.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)

Requête de plage

Les requêtes de plage consistent à identifier toutes les valeurs comprises entre deux bornes. Grâce à l’ordre des arbres AVL, on peut les localiser efficacement.

Pour trouver toutes les valeurs comprises entre la borne inférieure lb et la borne supérieure ub, nous parcourons récursivement l’arbre. Pour chaque nœud dont la valeur est dans l’intervalle, nous l’ajoutons aux résultats, puis explorons ses sous-arbres gauche et droit.

On ignore le sous-arbre gauche si la valeur du nœud est inférieure à la borne inférieure, car toutes les valeurs du sous-arbre gauche sont plus petites que celle du nœud. De même, on ignore le sous-arbre droit si la valeur du nœud est supérieure à la borne supérieure, car toutes ses valeurs seront plus grandes.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results

Autres arbres auto-équilibrés

Nous avons implémenté un arbre AVL capable d’exécuter les opérations suivantes :

• Ajout d’une valeur
• Suppression d’une valeur
• Recherche d’une valeur
• Interrogation des minimum et maximum
• Interrogation de toutes les valeurs entre deux bornes

Le package avltree propose une implémentation Python reflétant ces capacités.

D’autres arbres binaires de recherche auto-équilibrés, tels que les arbres rouge-noir, les splay trees et les B-arbres, offrent des fonctionnalités similaires. En général, leurs performances sont comparables dans la plupart des applications, car ils conservent tous une hauteur logarithmique garantie. Les arbres AVL sont toutefois plus finement équilibrés : ils optimisent la recherche au prix d’insertions parfois plus lentes à cause d’un rééquilibrage plus strict.

Les splay trees sont particulièrement efficaces lorsque les éléments récemment consultés sont souvent réutilisés ; ils sont donc très adaptés aux mécanismes de cache.

Les B-arbres sont conçus pour fonctionner efficacement sur disque plutôt qu’en mémoire. Ils sont précieux pour gérer de très grands volumes de données dépassant la mémoire, comme pour la création d’index de bases de données.

Pistes d’amélioration

Plusieurs améliorations sont possibles. Voici quelques idées d’exercices pour approfondir votre compréhension des arbres AVL :

• Dans notre implémentation, les nœuds stockent une seule valeur. Pour un usage en index de base de données, il faut stocker des lignes entières, car la valeur correspond à une colonne. On peut enrichir l’implémentation pour faire fonctionner l’arbre AVL comme un dictionnaire, liant les valeurs à leurs lignes.
• Notre implémentation ne gère pas les doublons. On peut la modifier pour autoriser plusieurs nœuds partageant la même valeur.
• Classiquement, les arbres AVL sont implémentés de façon récursive. Nous avons choisi l’itératif pour éviter d’exiger une forte maîtrise de la récursion. Les versions récursives sont souvent plus élégantes et concises, mais nécessitent une compréhension solide du concept.

Conclusion

Les BST sont un type d’arbre binaire qui organise les données selon un ordre précis. Cette organisation évite d’inspecter l’ensemble du jeu de données lors des recherches. Cependant, ils peuvent se déséquilibrer et dégrader les performances, pouvant aller jusqu’à exiger l’inspection complète du jeu de données.

Les arbres AVL résolvent ce problème en imposant des propriétés d’équilibre via des rotations. Ces propriétés garantissent une hauteur logarithmique par rapport à la taille des données, ce qui améliore nettement les performances.

Une complexité logarithmique représente un progrès majeur par rapport à une complexité linéaire : les arbres AVL sont donc très efficaces pour les requêtes. Même avec des milliards d’entrées, ils ne nécessitent d’inspecter que très peu de points de données pour trouver un élément.