Structures arborescentes avancées

Après avoir maîtrisé les structures d'arbres de base telles que les arbres binaires et les arbres binaires de recherche, nous allons maintenant entrer dans un domaine plus vaste et plus efficace — les structures d'arbres avancées.

Si les arbres de base sont des routes ordinaires dans le monde des structures de données, alors les structures d'arbres avancées sont des autoroutes et des échangeurs soigneusement conçus. Grâce à des règles d'équilibrage ingénieuses et à des stratégies de stockage, elles garantissent d'excellentes performances même lorsque les volumes de données sont énormes ou que les opérations sont fréquentes.

Cette section présenteral'arbre AVL、l'arbre rouge-noir、le B-Treeetle B+ TreeCes quatre structures arborescentes avancées classiques.

Pourquoi avons-nous besoin de structures arborescentes avancées ?

Avant d'aller plus loin, posons d'abord une question : alors que nous disposons d'un arbre binaire de recherche (ABR) efficace, pourquoi avons-nous encore besoin d'arbres plus complexes ?

Imaginez que vous avez une bibliothèque et que vous utilisez un ABR pour stocker des livres triés par titre. Si vous insérez les livres un par un dans l'ordre alphabétique (par exemple :A..., B..., C...), l'arbre dégénère en une chaîne (semblable à une liste chaînée). À ce stade, le temps pour trouver un livre passe de l'idéalO(log n)Dégradation dans le pire des casO(n), une efficacité extrêmement faible.

Figure : schéma d'un arbre binaire de recherche dégénérant en liste chaînée lors de l'insertion de données ordonnées, entraînant une dégradation des performances de recherche.

Les structures arborescentes avancées (arbres auto-équilibrés) sont nées précisément pour résoudre ce problème.. Elles ajustent automatiquement la forme de l'arbre lors de l'insertion ou de la suppression de nœuds, maintiennent l'arbre équilibré, ce qui garantit que la complexité temporelle des opérations telles que la recherche, l'insertion et la suppression reste toujours àO(log n)niveau.

Arbre AVL : le gardien de l'équilibre en hauteur

L'arbre AVL est le premier arbre binaire de recherche auto-équilibré jamais inventé, nommé d'après ses inventeurs Adelson-Velsky et Landis.

L'idée centrale de l'arbre AVL est très simple :Pour tout nœud de l'arbre, la différence de hauteur entre son sous-arbre gauche et son sous-arbre droit ne peut pas dépasser 1.。

Concept clé : facteur d'équilibre

Chaque nœud possède unfacteur d'équilibre, et sa formule de calcul est :Balance factor = height of left subtree - height of right subtreeDans un arbre AVL, le facteur d'équilibre de chaque nœud ne peut être que -1, 0 ou 1.

Déséquilibre et ajustement par rotation

Après l'insertion ou la suppression d'un nœud, si le facteur d'équilibre d'un nœud devient 2 ou -1, l'arbre est déséquilibré. Pour rétablir l'équilibre, l'arbre AVL utilise quatre opérations derotationpour ajuster :

  • Rotation à gauche: gère le cas de déséquilibre « droite-droite ».
  • Rotation à droite: gère le cas de déséquilibre « gauche-gauche ».
  • Rotation gauche-droite: d'abord une rotation à gauche puis une rotation à droite, pour traiter le cas de déséquilibre « gauche-droite ».
  • Rotation droite-gauche: d'abord une rotation à droite puis une rotation à gauche, pour traiter le cas de déséquilibre « droite-gauche ».

Exemple

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.height = 1  # Hauteur du nœud, initialement 1
        self.left = None
        self.right = None

def get_height(node):
    """Obtenir la hauteur d'un nœud (gérer les nœuds vides)"""
    return node.height if node else 0

def get_balance_factor(node):
    """Calculer le facteur d'équilibre d'un nœud"""
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def right_rotate(y):
    """
Effectuer une rotation à droite sur le sous-arbre dont la racine est y
         y                              x
        / \                          /   \
x T4 rotation à droite (y) z y
      / \      - - - - - - - ->    / \  / \
     z   T3                       T1  T2 T3 T4
    / \
  T1   T2
    """
    x = y.left
    T3 = x.right

    # Effectuer la rotation
    x.right = y
    y.left = T3

    # Mettre à jour les hauteurs (il faut d'abord mettre à jour la hauteur de y, puis celle de x)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))

    # Retourner le nouveau nœud racine
    return x

# La fonction de rotation à gauche est symétrique à la rotation à droite ; l'implémentation détaillée est omise ici
def left_rotate(x):
    """Effectuer une rotation à gauche sur le sous-arbre dont la racine est x (la logique est symétrique à la rotation à droite)"""
    pass

Résumé des caractéristiques de l'arbre AVL

Fonctionnalités Description
Strictement équilibré La condition d'équilibre est stricte (différence de hauteur ≤ 1), la hauteur de l'arbre est la plus proche de log n et les performances de recherche sont excellentes.
Ajustements fréquents Après une insertion/suppression, plusieurs rotations du bas vers le haut peuvent être nécessaires pour rétablir l'équilibre.
Scénarios applicables Adaptéaux scénarios comportant davantage de requêtes et moins d'insertions/suppressions, tels que la couche intermédiaire des index de bases de données ou les tables de recherche en mémoire.

Arbre rouge-noir : le roi de la pratique d'ingénierie

L'arbre rouge-noir est un autre arbre binaire de recherche auto-équilibré. Il fait certains « compromis » par rapport à l'arbre AVL. Plutôt que de rechercher un équilibre absolu comme l'arbre AVL, il utilise un ensemble de règles plus souples pour garantir un équilibre approximatif, ce qui réduit le nombre de rotations lors de l'insertion/suppression et donne de meilleurs résultats d'ingénierie au niveau des performances globales. JavaTreeMap、TreeSetet la STL C++map、setToutes leurs implémentations sous-jacentes utilisent des arbres rouge-noir.

Les cinq règles fondamentales des arbres rouge-noir

Les arbres rouge-noir maintiennent l'équilibre en ajoutant un attribut de couleur (rouge ou noir) aux nœuds et en respectant les règles suivantes :

  • Chaque nœud est soit rouge, soit noir.
  • Le nœud racine est noir。
  • Tous les nœuds feuilles (nœuds vides NIL) sont noirs.
  • Les deux enfants d'un nœud rouge doivent être noirs.(c'est-à-dire qu'il ne peut pas y avoir de nœuds rouges consécutifs).
  • Tous les chemins de n'importe quel nœud vers chacun de ses nœuds feuilles contiennentle même nombrede nœuds noirs.

Les règles 4 et 5 sont essentielles à l'équilibre de l'arbre rouge-noir. La règle 5 garantit qu'aucun chemin n'est plus de deux fois plus long qu'un autre chemin, ce qui permet d'atteindre un équilibre approximatif.

Stratégie d'ajustement d'insertion

Lors de l'insertion d'un nouveau nœud, nous le colorons toujours d'abord enRouge(pour éviter de violer la règle 5). Si cela provoque un conflit (principalement en violant la règle 2 ou la règle 4), il doit être ajusté parChangement de couleuretRotationà ajuster. L'idée centrale de l'ajustement est de continuellement "faire remonter" le conflit (rouge) vers la racine jusqu'à ce qu'il puisse être résolu par recoloration ou rotation.

Exemple

class RBNode:
    RED = "RED"
    BLACK = "BLACK"

    def __init__(self, key):
        self.key = key
        self.color = self.RED  # Le nouveau nœud est initialement rouge
        self.left = None
        self.right = None
        self.parent = None  # L'arbre rouge-noir a besoin d'un pointeur vers le parent

def insert_fixup(tree, node):
    """Réparer les propriétés de l'arbre rouge-noir après insertion (description simplifiée de la logique)"""
    while node.parent and node.parent.color == RBNode.RED:
        # Cas 1 : le nœud oncle est rouge -> recolorer
        # Cas 2 & 3 : le nœud oncle est noir -> résolus par rotation et recoloriage
        # ... (L'implémentation réelle implique un grand nombre d'opérations sur les pointeurs ; voici une description logique)
        pass
    tree.root.color = RBNode.BLACK  # S'assurer que le nœud racine est noir

Arbre rouge-noir vs. Arbre AVL

Fonctionnalités Arbre AVL arbre rouge-noir
Critère d'équilibre Strict (différence de hauteur ≤ 1) Souple (équilibre approximatif garanti par des règles de couleur)
Performance de recherche Meilleure(l'arbre est plus équilibré) Légèrement inférieure, mais toujours O(log n)
Insertion/Suppression Peut nécessiterPlus de rotations Moins de rotations,Plus efficace
Scénarios applicables Scénarios nécessitant des recherches fréquentes Exigences élevées en matière de performances globalesscénarios, tels que les bibliothèques standard de langage et les systèmes de fichiers.

B-Tree et B+ Tree : le moteur du stockage sur disque

Lorsque les données sont trop volumineuses pour tenir entièrement en mémoire, elles doivent être stockées sur disque. La vitesse des E/S disque (lecture/écriture) est bien plus lente que l'accès à la mémoire. Les arbres B et B+ sont conçus pourréduire le nombre d'opérations d'E/S disqueConçus pourArbre de recherche équilibré multi-voies, et ils sont largement utilisés dans les index de bases de données et de systèmes de fichiers.

Arbre B : arbre de recherche équilibré multi-voies

Dans un arbre B, chaque nœud ne stocke plus seulement un élément de données et deux pointeurs. Unarbre B d'ordre mUn nœud possède les caractéristiques suivantes :

  • Chaque nœud a au plusm nœuds enfants。
  • Chaque nœud qui n'est ni racine ni feuille a au moins⌈m/2⌉ nœuds enfants。
  • Le nœud racine a au moins 2 nœuds enfants (sauf s'il est lui-même un nœud feuille).
  • Tous les nœuds feuilles sont situés au même niveau.
  • Si un nœud non feuille a k nœuds enfants, il contientk-1 clés, et ces clés partitionnent les plages de valeurs des sous-arbres.

Figure : Un schéma structurel d'un nœud d'arbre B d'ordre 3. Il contient deux clés et trois pointeurs, divisant la plage de données en trois intervalles.

Les avantages des arbres Brésident dans leur forme d'arbre courte et large. Parce qu'un nœud peut stocker plusieurs clés et avoir plusieurs nœuds enfants, la hauteur de l'arbre est considérablement réduite. Lors de la recherche d'un élément de données, moins de pages disque (nœuds) doivent être chargées, ce qui améliore l'efficacité.

Arbre B+ : La version améliorée de l'arbre B

Les arbres B+ apportent des améliorations majeures par rapport aux arbres B et sont lestandard de facto。

Différences fondamentales entre les arbres B+ et les arbres B :

  1. Emplacement de stockage des données: dans l'arbre B+,tous les enregistrements de données (ou pointeurs vers des enregistrements) sont stockés uniquement dans les nœuds feuilles.. Les nœuds internes (nœuds non feuilles) stockent uniquement des clés pour le routage.
  2. Liste chaînée des nœuds feuilles: tous les nœuds feuilles sont reliés par des pointeurs en uneliste doublement chaînée ordonnée。

Figure : diagramme d'un arbre B+. Notez que les données se trouvent uniquement dans les nœuds feuilles, et que les nœuds feuilles forment une liste chaînée ordonnée.

L'énorme avantage des arbres B+

Avantages Explication
Efficacité d'interrogation plus stable Toute recherche doit atteindre un nœud feuille ; les longueurs de chemin sont les mêmes, donc les performances sont stables.
Meilleure utilisation de l'espace Les nœuds internes ne stockent pas de données, donc ils peuvent contenir plus de clés, ce qui rend l'arbre plus court et réduit les E/S.
Requête par plage puissante Grâce à la liste chaînée des nœuds feuilles, il est possible d'effectuer efficacementWHERE age BETWEEN 20 AND 30des requêtes par plage, alors que les arbres B nécessitent un parcours infixe complexe.
Mieux adapté à la prélecture sur disque Les lectures/écritures sur disque se font par pages (blocs). Les nœuds d'un arbre B+ sont généralement conçus pour avoir exactement la taille d'une page, de sorte qu'une seule I/O peut charger davantage de clés, ce qui réduit encore les I/O.

Résumé

Utilisons un tableau pour passer en revue ces quatre structures d'arbres avancées :

Structure d'arbre Objectif principal Caractéristiques clés Applications typiques
Arbre AVL Vitesse de requête ultime Très strictement équilibré, avec de fréquents ajustements par rotation Scénarios nécessitant des recherches rapides en mémoire
arbre rouge-noir Performances globales équilibrées Approximativement équilibré via des règles de couleur, insertion et suppression efficaces Bibliothèques standard du langage (Map/Set), ordonnancement des processus
Arbre B Réduire les E/S disque Équilibré multi-voies, les données peuvent être stockées dans les nœuds internes Premiers systèmes de fichiers, certains index de bases de données
Arbre B+ Optimiser l'index de base de données Données stockées uniquement dans les feuilles, les feuilles forment une liste chaînée, requêtes par plage performantes Index des bases de données relationnelles modernes (MySQL, PostgreSQL)
autres extensions