logo

TechCodeview

Introduction à l'arbre rouge-noir

Arbres de recherche binaires sont un élément fondamental Structure de données, mais leurs performances peuvent en souffrir si l'arbre devient déséquilibré. Arbres noirs rouges sont un type de arbre de recherche binaire équilibré qui utilisent un ensemble de règles pour maintenir l'équilibre, garantissant une complexité temporelle logarithmique pour des opérations telles que insertion, suppression et recherche , quelle que soit la forme initiale de l'arbre. Arbres noirs rouges sont auto-équilibrés, utilisant un simple schéma de codage couleur pour ajuster l'arbre après chaque modification.

Arbre rouge-noir



Table des matières

Qu'est-ce qu'un arbre rouge-noir ?

UN Arbre rouge-noir est un auto-équilibrage arbre de recherche binaire où chaque nœud possède un attribut supplémentaire : une couleur, qui peut être soit rouge ou noir . L'objectif principal de ces arbres est de maintenir l'équilibre lors des insertions et des suppressions, garantissant ainsi une récupération et une manipulation efficaces des données.

Propriétés des arbres rouge-noir

UN Arbre rouge-noir ont les propriétés suivantes :



  1. Couleur du nœud : Chaque nœud est soit rouge, soit noir .
  2. Propriété racine : La racine de l'arbre est toujours noir .
  3. Propriété rouge : Les nœuds rouges ne peuvent pas avoir d'enfants rouges (pas de deux nœuds rouges consécutifs sur un chemin).
  4. Propriété noire  : Chaque chemin d'un nœud à ses nœuds nuls descendants (feuilles) a le même nombre de noir nœuds.
  5. Propriété de la feuille : Toutes les feuilles (nœuds NIL) sont noir .

Ces propriétés garantissent que le chemin le plus long depuis la racine jusqu’à n’importe quelle feuille n’est pas plus de deux fois plus long que le chemin le plus court, maintenant ainsi l’équilibre et les performances efficaces de l’arbre.

Exemple d'arbre rouge-noir

l'actrice indienne rani mukerji

Le Corriger l'arbre rouge-noir dans l'image ci-dessus garantit que chaque chemin depuis la racine vers un nœud feuille a le même nombre de nœuds noirs. Dans ce cas,​ il y en a un (hors nœud racine).



Le Arbre rouge noir incorrect ne suit pas les propriétés rouge-noir comme deux nœuds rouges sont adjacents les uns aux autres. Un autre problème est que l’un des chemins vers un nœud feuille n’a aucun nœud noir, alors que les deux autres contiennent un nœud noir.

np.log

Pourquoi des arbres rouge-noir ?

La plupart des opérations BST (par exemple, recherche, max, min, insertion, suppression, etc.) prennent Oh) moment où h est la hauteur du BST . Le coût de ces opérations peut devenir Sur) pour un biais Arbre binaire. Si l'on s'assure que la hauteur de l'arbre reste O (log n) après chaque insertion et suppression, nous pouvons alors garantir une limite supérieure de O (log n) pour toutes ces opérations. La hauteur d'un arbre rouge-noir est toujours O (log n) où n est le nombre de nœuds dans l’arborescence.

M. Non.AlgorithmeComplexité temporelle
1.RechercheO (log n)
2.InsérerO (log n)
3.SupprimerO (log n)

Comparaison avec Arbre AVL :

Les arbres AVL sont plus équilibrés que les arbres rouge-noir, mais ils peuvent provoquer davantage de rotations lors de l'insertion et de la suppression. Ainsi, si votre application implique des insertions et des suppressions fréquentes, les arbres Rouge-Noir doivent être préférés. Et si les insertions et les suppressions sont moins fréquentes et que la recherche est une opération plus fréquente, alors Arbre AVL devrait être préféré à l’arbre rouge-noir.

Comment un Arbre Rouge-Noir assure-t-il l’équilibre ?

Un exemple simple pour comprendre l’équilibrage est qu’une chaîne de 3 nœuds n’est pas possible dans l’arbre Rouge-Noir. Nous pouvons essayer n'importe quelle combinaison de couleurs et voir si elles violent toutes la propriété de l'arbre Rouge-Noir.

Structure appropriée d'un arbre rouge-noir à trois nœuds

Points intéressants sur l’Arbre Rouge-Noir :

  • Le noir la hauteur de l'arbre rouge-noir est le nombre de nœuds noirs sur un chemin allant du nœud racine à un nœud feuille. Les nœuds feuilles sont également comptés comme noir nœuds. Donc, un arbre rouge-noir de hauteur h a hauteur du noir>= h/2 .
  • Hauteur d'un arbre rouge-noir avec n les nœuds sont h<= 2 log 2 (n+1) .
  • Toutes les feuilles (NIL) sont noir .
  • Le noir la profondeur d'un nœud est définie comme le nombre de nœuds noirs de la racine à ce nœud, c'est-à-dire le nombre d'ancêtres noirs.

Opérations de base sur l'arbre rouge-noir :

Les opérations de base sur un arbre rouge-noir comprennent :

  1. Insertion
  2. Recherche
  3. Effacement
  4. Rotation

1. Insertion

L'insertion d'un nouveau nœud dans un arbre rouge-noir implique un processus en deux étapes : effectuer une insertion d'un arbre de recherche binaire (BST) , suivi de la correction de toute violation des propriétés Rouge-Noir.

si sinon boucle en java

Étapes d'insertion

  1. Insertion BST : Insérez le nouveau nœud comme dans un BST standard.
  2. Corriger les violations :
    • Si le parent du nouveau nœud est noir , aucune propriété n'est violée.
    • Si le parent est rouge , l'arborescence peut violer la propriété Red, nécessitant des correctifs.

Correction des violations lors de l'insertion

Après avoir inséré le nouveau nœud en tant que rouge nœud, nous pouvons rencontrer plusieurs cas selon les couleurs du parent et de l’oncle du nœud (le frère ou la sœur du parent) :

  • Cas 1 : Oncle est rouge : Recolorer le parent et l'oncle pour noir , et le grand-parent à rouge . Remontez ensuite dans l’arborescence pour vérifier d’autres violations.
  • Cas 2 : oncle est noir :
    • Sous-cas 2.1 : Le nœud est un bon enfant : Effectue une rotation vers la gauche sur le parent.
    • Sous-cas 2.2 : Le nœud est un enfant gauche : Effectuez une rotation à droite sur le grand-parent et recolorez en conséquence.

2. Recherche

La recherche d'un nœud dans un arbre rouge-noir est similaire à la recherche dans un arbre standard. Arbre de recherche binaire (BST) . L'opération de recherche suit un chemin simple depuis le racine à un feuille , en comparant la valeur cible avec la valeur du nœud actuel et en se déplaçant vers la gauche ou la droite en conséquence.

Étapes de recherche

  1. Commencez à la racine : Commencez la recherche au niveau du nœud racine.
  2. Traverser l'arbre :
    • Si la valeur cible est égale à la valeur du nœud actuel, le nœud est trouvé.
    • Si la valeur cible est inférieure à la valeur du nœud actuel, déplacez-vous vers l'enfant de gauche.
    • Si la valeur cible est supérieure à la valeur du nœud actuel, passez au bon enfant.
  3. Répéter : Continuez ce processus jusqu'à ce que la valeur cible soit trouvée ou qu'un nœud NIL soit atteint (indiquant que la valeur n'est pas présente dans l'arborescence).

3. Effacement

La suppression d'un nœud d'un arbre rouge-noir implique également un processus en deux étapes : effectuer la suppression BST, suivie de la correction des violations éventuelles.

Étapes de suppression

  1. Suppression de la BST  : supprimez le nœud à l'aide des règles BST standard.
  2. Réparer le double noir :
    • Si un nœud noir est supprimé, une condition de double noir peut survenir, ce qui nécessite des correctifs spécifiques.

Correction des violations lors de la suppression

Lorsqu'un nœud noir est supprimé, nous traitons le problème du double noir en fonction de la couleur du frère et des couleurs de ses enfants :

  • Cas 1 : le frère ou la sœur est rouge : Faites pivoter le parent et recolorez le frère et le parent.
  • Cas 2 : un frère ou une sœur est noir :
    • Sous-cas 2.1 : Les enfants d’un frère ou d’une sœur sont noirs : Recolorer la fratrie et propager le double noir vers le haut.
    • Sous-cas 2.2 : Au moins un des enfants de la fratrie est rouge :
      • Si l'enfant éloigné du frère ou de la sœur est rouge : Effectuez une rotation sur le parent et le frère ou la sœur, et recolorez de manière appropriée.
      • Si l’enfant proche du frère ou de la sœur est rouge : Faites pivoter le frère et son enfant, puis manipulez comme ci-dessus.

4. Rotations

Les rotations sont des opérations fondamentales pour maintenir la structure équilibrée d’un Arbre Rouge-Noir (RBT). Ils aident à préserver les propriétés de l’arbre, en garantissant que le chemin le plus long depuis la racine jusqu’à une feuille ne dépasse pas deux fois la longueur du chemin le plus court. Les rotations sont de deux types : rotations à gauche et rotations à droite.

1. Rotation à gauche

Une rotation gauche au nœud 𝑥 X bouge 𝑥 X en bas vers la gauche et son enfant droit 𝑦 et debout pour prendre 𝑥 X L'endroit.

Visualisation de la rotation gauche 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Étapes de rotation à gauche :

  1. Ensemble et être le bon enfant de X .
  2. Se déplacer et le sous-arbre gauche de X le sous-arbre droit.
  3. Mettre à jour le parent de X et et .
  4. Mise à jour X le parent de pointer du doigt et au lieu de X .
  5. Ensemble et a laissé l'enfant à X .
  6. Mise à jour X le parent de et .

Pseudocode de rotation à gauche :

Rotation à gauche 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->droite;  x->droite = y->gauche ;  if (y->gauche != NIL) { y->gauche->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { racine = y;  } else if (x == x->parent->gauche) { x->parent->gauche = y;  } else { x->parent->right = y;  } y->gauche = x;  x->parent = y ; }>

2. Rotation à droite

Une rotation à droite au nœud 𝑥 X bouge 𝑥 X en bas à droite et son enfant gauche 𝑦 et debout pour prendre 𝑥 X L'endroit.

Visualisation de la rotation droite : 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Étapes de rotation à droite :

  1. Ensemble et être l'enfant gauche de X .
  2. Se déplacer et le sous-arbre droit de X Le sous-arbre gauche.
  3. Mettre à jour le parent de X et et .
  4. Mise à jour X le parent de pointer du doigt et au lieu de X .
  5. Ensemble et C'est mon enfant qui a raison de X .
  6. Mise à jour X le parent de et .

Pseudocode de rotation droite :

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->gauche;  x->gauche = y->droite ;  if (y->right != NIL) { y->right->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { racine = y;  } else if (x == x->parent->droit) { x->parent->droit = ​​y;  } else { x->parent->gauche = y;  } y->droite = x;  x->parent = y ; }>

Quand effectuer les rotations ?

Les rotations dans les arbres rouge-noir sont généralement effectuées lors des insertions et des suppressions pour conserver les propriétés de l'arbre. Voici les scénarios de rotations :

regroupement

1. Correction des violations après l'insertion

Lorsqu'un nouveau nœud est inséré, il est toujours coloré en rouge. Cela peut créer des violations des propriétés de l'arbre rouge-noir, en particulier :

  • La racine doit être noir .
  • Rouge les nœuds ne peuvent pas avoir rouge enfants.

Analyse de cas pour la correction des insertions :

  • Cas 1 : Recoloration et propagation vers le haut
    • Si le parent et l'oncle du nouveau nœud sont tous deux rouge , recolore le parent et l'oncle pour noir , et le grand-parent à rouge . Ensuite, appliquez de manière récursive le correctif au grand-parent.
  • Cas 2 : Rotation et recoloration
    • Si l'oncle du nouveau nœud est noir et le nouveau nœud est l'enfant droit d'un enfant gauche (ou vice versa), effectuez une rotation pour déplacer le nouveau nœud vers le haut et l'aligner.
    • Si l'oncle du nouveau nœud est noir et le nouveau nœud est l'enfant gauche d'un enfant gauche (ou droit d'un enfant droit), effectuez une rotation et recolorez le parent et le grand-parent pour corriger la violation.

2. Correction des violations après la suppression

Après la suppression, l'arborescence devra peut-être être corrigée pour restaurer les propriétés :

  • Lorsqu’un nœud noir est supprimé ou qu’un nœud rouge est remplacé par un nœud noir, une situation de double noir peut survenir.

Analyse de cas pour corriger les suppressions :

  • Cas 1 : le frère ou la sœur est rouge
    • Recolorez le frère et le parent et effectuez une rotation.
  • Cas 2 : un frère ou une sœur est noir et a des enfants noirs
    • Recolorez le frère en rouge et déplacez le problème vers le parent.
  • Cas 3 : un frère ou une sœur est noir avec au moins un enfant rouge
    • Faites pivoter et recolorez pour résoudre le problème du double noir.

Implémentation de l'Arbre Rouge-Noir :

Voici une implémentation détaillée d'un arbre rouge-noir comprenant les fonctions d'insertion, de recherche et de rotation :

C++ 
#include  using namespace std; // Node structure for the Red-Black Tree struct Node {  int data;  string color;  Node *left, *right, *parent;  Node(int data)  : data(data)  , color('RED')  , left(nullptr)  , right(nullptr)  , parent(nullptr)  {  } }; // Red-Black Tree class class RedBlackTree { private:  Node* root;  Node* NIL;  // Utility function to perform left rotation  void leftRotate(Node* x)  {  Node* y = x->droite;  x->droite = y->gauche ;  if (y->gauche != NIL) { y->gauche->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { racine = y;  } else if (x == x->parent->gauche) { x->parent->gauche = y;  } else { x->parent->right = y;  } y->gauche = x;  x->parent = y ;  } // Fonction utilitaire pour effectuer une rotation à droite void rightRotate(Node* x) { Node* y = x->left;  x->gauche = y->droite ;  if (y->right != NIL) { y->right->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { racine = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->gauche = y;  } y->droite = x;  x->parent = y ;  } // Fonction pour corriger les propriétés de l'arbre rouge-noir après // insertion void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->parent == k->parent->parent->gauche) { Noeud* u = k->parent->parent->droite; // oncle if (u->color == 'RED') { k->parent->color = 'NOIR';  u->couleur = 'NOIR';  k->parent->parent->color = 'ROUGE';  k = k->parent->parent;  } else { if (k == k->parent->droit) { k = k->parent;  rotation gauche(k);  } k->parent->couleur = 'NOIR';  k->parent->parent->color = 'ROUGE';  rightRotate(k->parent->parent);  } } else { Noeud* u = k->parent->parent->left; // oncle if (u->color == 'RED') { k->parent->color = 'NOIR';  u->couleur = 'NOIR';  k->parent->parent->color = 'ROUGE';  k = k->parent->parent;  } else { if (k == k->parent->gauche) { k = k->parent;  rotation à droite(k);  } k->parent->couleur = 'NOIR';  k->parent->parent->color = 'ROUGE';  leftRotate(k->parent->parent);  } } } racine->couleur = 'NOIR';  } // Fonction d'assistance au parcours dans l'ordre void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->left);  cout<< node->données<< ' ';  inorderHelper(node->droite);  } } // Fonction d'aide à la recherche Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } si (données< node->données) { return searchHelper (nœud->gauche, données);  } return searchHelper(node->right, data);  } public : // Constructeur RedBlackTree() { NIL = new Node(0);  NIL->couleur = 'NOIR';  NIL->gauche = NIL->droite = NIL ;  racine = NIL ;  } // Insérer une fonction void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL ;  new_node->right = NIL ;  Nœud* parent = nullptr ;  Nœud* actuel = racine ;  // BST insère while (current != NIL) { parent = current;  if (new_node->données< current->données) { actuel = actuel -> gauche ;  } else { actuel = actuel->droite ;  } } new_node->parent = parent;  if (parent == nullptr) { root = new_node;  } else if (new_node->données< parent->données) { parent->left = new_node;  } else { parent->right = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'NOIR';  retour;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(nouveau_node);  } // Traversée dans l'ordre void inorder() { inorderHelper(root); } // Fonction de recherche Node* search(int data) { return searchHelper(root, data);  } } ; int main() { RedBlackTree rbt ;  // Insertion d'éléments rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(15);  // Cout de parcours dans l'ordre<< 'Inorder traversal:' << endl;  rbt.inorder(); // Output: 10 15 20 30  // Search for a node  cout << '
Search for 15: '  << (rbt.search(15) != rbt.search(0))  << endl; // Output: 1 (true)  cout << 'Search for 25: '  << (rbt.search(25) != rbt.search(0))  << endl; // Output: 0 (false)  return 0; }>

Avantages des arbres rouge-noir :

  • Équilibré: Les arbres rouge-noir sont auto-équilibrés, ce qui signifie qu'ils maintiennent automatiquement un équilibre entre les hauteurs des sous-arbres gauche et droit. Cela garantit que les opérations de recherche, d'insertion et de suppression prennent un temps O (log n) dans le pire des cas.
  • Recherche, insertion et suppression efficaces : Grâce à leur structure équilibrée, les arbres rouge-noir offrent des opérations efficaces. La recherche, l'insertion et la suppression prennent toutes un temps O (log n) dans le pire des cas.
  • Simple à mettre en œuvre : Les règles de maintenance des propriétés de l'arbre rouge-noir sont relativement simples et simples à mettre en œuvre.
  • Largement utilisé : Les arbres rouge-noir sont un choix populaire pour implémenter diverses structures de données, telles que des cartes, des ensembles et des files d'attente prioritaires.

Inconvénients des arbres rouge-noir :

  • Plus complexe que les autres arbres équilibrés : Comparés aux arbres équilibrés plus simples comme les arbres AVL, les arbres rouge-noir ont des règles d'insertion et de suppression plus complexes.
  • Frais généraux constants : Le maintien des propriétés de l'arbre rouge-noir ajoute une petite surcharge à chaque opération d'insertion et de suppression.
  • Pas optimal pour tous les cas d’utilisation : Bien qu'efficaces pour la plupart des opérations, les arborescences rouge-noir ne constituent peut-être pas le meilleur choix pour les applications nécessitant des insertions et des suppressions fréquentes, car la surcharge constante peut devenir importante.

Applications des arbres rouge-noir :

  • Implémentation de cartes et d'ensembles : Les arbres rouge-noir sont souvent utilisés pour implémenter des cartes et des ensembles, où une recherche, une insertion et une suppression efficaces sont cruciales.
  • Files d'attente prioritaires : Les arbres rouge-noir peuvent être utilisés pour implémenter des files d'attente prioritaires, dans lesquelles les éléments sont classés en fonction de leur priorité.
  • Systèmes de fichiers : Les arbres rouge-noir sont utilisés dans certains systèmes de fichiers pour gérer les structures de fichiers et de répertoires.
  • Bases de données en mémoire : Les arbres rouge-noir sont parfois utilisés dans les bases de données en mémoire pour stocker et récupérer efficacement des données.
  • Développement graphique et de jeux : Les arbres rouge-noir peuvent être utilisés dans les graphiques et les jeux développement pour des tâches telles que la détection de collision et la recherche de chemin.

Foire aux questions (FAQ) sur l'arbre rouge-noir :

1. Qu'est-ce qu'un arbre rouge-noir ?

Un arbre rouge-noir est un arbre de recherche binaire auto-équilibré qui maintient un équilibre entre les hauteurs de ses sous-arbres gauche et droit. Cela garantit que les opérations de recherche, d'insertion et de suppression prennent un temps O (log n) dans le pire des cas. Les arbres rouge-noir sont largement utilisés dans diverses applications où des structures de données efficaces sont requises.

2. Comment un arbre rouge-noir maintient-il son équilibre ?

Les Arbres Rouge-Noir maintiennent leur équilibre en appliquant des règles spécifiques sur les couleurs des nœuds (ROUGE ou NOIR) et les relations entre eux. Ces règles garantissent que l'arbre reste équilibré et que la différence de hauteur entre les sous-arbres gauche et droit est d'au plus 1.

3. Quels sont les avantages d’utiliser un arbre rouge-noir ?

  • Équilibré: Les arbres rouge-noir s'auto-équilibrent, garantissant des opérations de recherche, d'insertion et de suppression efficaces.
  • Efficace: Ils offrent une complexité temporelle O(log n) pour la plupart des opérations.
  • Simple à mettre en œuvre : Les règles de maintien des propriétés de l'arbre rouge-noir sont relativement simples.
  • Largement utilisé : Ils constituent un choix populaire pour implémenter diverses structures de données et algorithmes.

4. Quels sont les inconvénients de l’utilisation d’un arbre rouge-noir ?

  • Comparés aux arbres équilibrés plus simples comme les arbres AVL, les arbres rouge-noir ont des règles d'insertion et de suppression plus complexes.
  • Le maintien des propriétés de l'arbre rouge-noir ajoute une petite surcharge à chaque opération d'insertion et de suppression.
  • Pour les applications avec des insertions et des suppressions fréquentes, d’autres structures arborescentes équilibrées pourraient être plus adaptées.

5. Quelles sont les applications courantes des arbres rouge-noir ?

  • Implémentation de cartes et d'ensembles
  • Files d'attente prioritaires
  • Systèmes de fichiers
  • Bases de données en mémoire
  • Développement graphique et de jeux (détection de collision, pathfinding)
  • Définition et signification de l’arbre rouge-noir dans DSA
  • Arbres de recherche binaires auto-équilibrés
  • Arbre noir rouge vs arbre AVL
  • Quelle est la différence entre le tas et l’arbre rouge-noir ?
  • Insertion dans l'arbre rouge-noir
  • Suppression dans l'arbre rouge-noir
  • Arbres rouge-noir | Insertion descendante