logo

TechCodeview

Inleiding tot rood-zwarte boom

Binaire zoekbomen zijn fundamenteel data structuur, maar hun prestaties kunnen eronder lijden als de boom uit balans raakt. Rode zwarte bomen zijn een soort evenwichtige binaire zoekboom die een reeks regels gebruiken om het evenwicht te bewaren, waardoor een logaritmische tijdscomplexiteit wordt gegarandeerd voor bewerkingen zoals invoegen, verwijderen en zoeken , ongeacht de oorspronkelijke vorm van de boom. Rode zwarte bomen zijn zelfbalancerend en gebruiken een eenvoudig kleurcoderingsschema om de boom na elke wijziging aan te passen.

Rood-zwarte boom



Inhoudsopgave

Wat is een rood-zwarte boom?

A Rood-zwarte boom is een zelfbalancerend middel binaire zoekboom waarbij elk knooppunt een extra attribuut heeft: een kleur, die beide kan zijn rood of zwart . Het primaire doel van deze bomen is het handhaven van het evenwicht tijdens het invoegen en verwijderen, waardoor het efficiënt ophalen en manipuleren van gegevens wordt gegarandeerd.

Eigenschappen van roodzwarte bomen

A Rood-zwarte boom hebben de volgende eigenschappen:



  1. Knooppuntkleur : Elk knooppunt is rood of zwart .
  2. Root-eigenschap : De wortel van de boom is altijd zwart .
  3. Rode eigenschap : Rode knooppunten kunnen geen rode kinderen hebben (geen twee opeenvolgende rode knooppunten op een pad).
  4. Zwart eigendom : Elk pad van een knooppunt naar zijn onderliggende nulknooppunten (bladeren) heeft hetzelfde aantal zwart knooppunten.
  5. Blad eigendom : Alle bladeren (NIL-knooppunten) zijn zwart .

Deze eigenschappen zorgen ervoor dat het langste pad van de wortel naar welk blad dan ook niet meer dan twee keer zo lang is als het kortste pad, waardoor het evenwicht en de efficiënte prestaties van de boom behouden blijven.

Voorbeeld van rood-zwarte boom

Java-anonieme functie

De Correcte rood-zwarte boom in bovenstaande afbeelding zorgt ervoor dat elk pad van de wortel naar een bladknooppunt hetzelfde aantal zwarte knooppunten heeft. In dit geval is er één (exclusief het hoofdknooppunt).



De Onjuiste roodzwarte boom volgt niet de rood-zwart-eigenschappen als twee rode knooppunten liggen naast elkaar. Een ander probleem is dat een van de paden naar een bladknooppunt nul zwarte knooppunten heeft, terwijl de andere twee een zwart knooppunt bevatten.

Waarom roodzwarte bomen?

De meeste BST-bewerkingen (bijvoorbeeld zoeken, max, min, invoegen, verwijderen.. enz.) duren Oh) tijd waarbij h de hoogte is van de BST . De kosten van deze operaties kunnen stijgen Op) voor een scheef Binaire boom. Als we ervoor zorgen dat de hoogte van de boom behouden blijft O(logboek n) na elke invoeging en verwijdering, dan kunnen we een bovengrens garanderen van O(logboek n) voor al deze operaties. De hoogte van een Rood-Zwarte boom is altijd O(logboek n) waarbij n het aantal knooppunten in de boom is.

Meneer Nee.AlgoritmeTijdcomplexiteit
1.ZoekopdrachtO(logboek n)
2.InvoegenO(logboek n)
3.VerwijderenO(logboek n)

Vergelijking met AVL-boom :

De AVL-bomen zijn evenwichtiger dan rood-zwarte bomen, maar kunnen tijdens het inbrengen en verwijderen meer rotaties veroorzaken. Dus als uw toepassing veelvuldige invoegingen en verwijderingen met zich meebrengt, verdient rood-zwarte bomen de voorkeur. En als de invoegingen en verwijderingen minder frequent voorkomen en zoeken een frequentere bewerking is, dan AVL-boom verdient de voorkeur boven de roodzwarte boom.

Hoe zorgt een Rood-Zwarte Boom voor evenwicht?

Een eenvoudig voorbeeld om balancering te begrijpen is dat een keten van 3 knooppunten niet mogelijk is in de rood-zwarte boom. We kunnen elke combinatie van kleuren uitproberen en kijken of ze allemaal de rood-zwarte boomeigenschap schenden.

Goede structuur van een rood-zwarte boom met drie knooppunten

Interessante punten over rood-zwarte boom:

  • De zwart hoogte van de roodzwarte boom is het aantal zwarte knooppunten op een pad van het wortelknooppunt naar een bladknooppunt. Bladknopen worden ook meegeteld als zwart knooppunten. Een rood-zwarte boom van hoogte dus H heeft zwart hoogte>= h/2 .
  • Hoogte van een roodzwarte boom met N knooppunten is h<= 2 logboek 2 (n + 1) .
  • Alle bladeren (NIL) zijn zwart .
  • De zwart De diepte van een knooppunt wordt gedefinieerd als het aantal zwarte knooppunten vanaf de wortel tot dat knooppunt, d.w.z. het aantal zwarte voorouders.

Basisbewerkingen op rood-zwarte boom:

De basisbewerkingen op een rood-zwarte boom zijn onder meer:

  1. Plaatsing
  2. Zoekopdracht
  3. Verwijdering
  4. Rotatie

1. Plaatsing

Het invoegen van een nieuw knooppunt in een rood-zwarte boom omvat een proces in twee stappen: het uitvoeren van een standaard binaire zoekboom (BST) invoegen , gevolgd door het oplossen van eventuele schendingen van Rood-Zwart-eigendommen.

Invoegstappen

  1. BST-invoeging : Voeg het nieuwe knooppunt in zoals in een standaard BST.
  2. Overtredingen oplossen :
    • Als de ouder van het nieuwe knooppunt dat is zwart , er worden geen eigenschappen geschonden.
    • Als de ouder dat is rood , kan de boom de rode eigenschap schenden, waardoor reparaties nodig zijn.

Overtredingen tijdens het inbrengen herstellen

Nadat u het nieuwe knooppunt hebt ingevoegd als een rood knooppunt, kunnen we verschillende gevallen tegenkomen, afhankelijk van de kleuren van de ouder en oom van het knooppunt (de broer of zus van de ouder):

  • Geval 1: Oom is rood : Kleur de ouder en oom opnieuw in zwart , en de grootouder ook rood . Ga vervolgens omhoog in de boom om te controleren op verdere overtredingen.
  • Geval 2: Oom is zwart :
    • Subgeval 2.1: Knooppunt is een rechterkind : Voer een rotatie naar links uit op de ouder.
    • Subgeval 2.2: Knooppunt is een linkerkind : Voer een rotatie naar rechts uit op de grootouder en kleur opnieuw op de juiste manier.

2. Zoeken

Het zoeken naar een knooppunt in een Rood-Zwarte Boom is vergelijkbaar met het zoeken in een standaard Binaire zoekboom (BST) . De zoekoperatie volgt een eenvoudig pad vanaf de wortel naar een blad , waarbij de doelwaarde wordt vergeleken met de waarde van het huidige knooppunt en dienovereenkomstig naar links of rechts wordt verplaatst.

Zoekstappen

  1. Begin bij de wortel : Begin de zoekopdracht bij het hoofdknooppunt.
  2. Doorkruis de boom :
    • Als de doelwaarde gelijk is aan de waarde van het huidige knooppunt, wordt het knooppunt gevonden.
    • Als de doelwaarde kleiner is dan de waarde van het huidige knooppunt, ga dan naar het linkerkind.
    • Als de doelwaarde groter is dan de waarde van het huidige knooppunt, ga dan naar het juiste onderliggende knooppunt.
  3. Herhalen : Ga door met dit proces totdat de doelwaarde is gevonden of een NIL-knooppunt is bereikt (wat aangeeft dat de waarde niet aanwezig is in de boom).

3. Verwijdering

Het verwijderen van een knooppunt uit een rood-zwarte boom omvat ook een proces in twee stappen: het uitvoeren van de BST-verwijdering, gevolgd door het oplossen van eventuele schendingen die zich voordoen.

Verwijderingsstappen

  1. BST-verwijdering : Verwijder het knooppunt met behulp van standaard BST-regels.
  2. Dubbel zwart repareren :
    • Als een zwart knooppunt wordt verwijderd, kan er een dubbele zwarte toestand ontstaan, waarvoor specifieke oplossingen nodig zijn.

Overtredingen tijdens verwijdering herstellen

Wanneer een zwart knooppunt wordt verwijderd, behandelen we het dubbele zwarte probleem op basis van de kleur van het broertje of zusje en de kleuren van zijn kinderen:

  • Geval 1: Broer of zus is rood : Roteer de ouder en kleur de broer of zus en de ouder opnieuw.
  • Geval 2: Broer of zus is zwart :
    • Subgeval 2.1: De kinderen van broers en zussen zijn zwart : Kleur de broer of zus opnieuw en verspreid het dubbele zwart naar boven.
    • Subgeval 2.2: Ten minste één van de kinderen van de broer of zus is rood :
      • Als het verre kind van de broer of zus rood is : Voer een rotatie uit op de ouder en broer of zus en pas de kleur opnieuw aan.
      • Als het naaste kind van de broer of zus rood is : Draai het broertje of zusje en zijn kind en handel vervolgens zoals hierboven.

4. Rotatie

Rotaties zijn fundamentele handelingen bij het handhaven van de evenwichtige structuur van een rood-zwarte boom (RBT). Ze helpen de eigenschappen van de boom te behouden en zorgen ervoor dat het langste pad van de wortel naar welk blad dan ook niet meer dan tweemaal zo lang is als het kortste pad. Rotaties zijn er in twee soorten: linkse rotaties En juiste rotaties.

1. Linksdraaien

Een rotatie naar links bij knooppunt 𝑥 X beweegt 𝑥 X naar links en het rechterkind 𝑦 En op te nemen 𝑥 X 's plaats.

Visualisatie van linkse rotatie 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Links rotatie stappen:

  1. Set En om het juiste kind van te zijn X .
  2. Beweging En 's linker subboom naar X 's rechter subboom.
  3. Update de ouder van X En En .
  4. Update X de ouder om naar te wijzen En in plaats van X .
  5. Set En het linkerkind van X .
  6. Update X de ouder van En .

Pseudocode van linksdraaien:

Linksom draaien 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->rechts;  x->rechts = y->links;  if (y->links!= NIL) { y->links->ouder = x;  } y->ouder = x->ouder;  if (x->parent == nullptr) { root = y;  } else if (x == x->ouder->links) { x->ouder->links = y;  } anders { x->bovenliggend->rechts = y;  } y->links = x;  x->ouder = y; }>

2. Rechts draaien

Een rotatie naar rechts bij knooppunt 𝑥 X beweegt 𝑥 X naar rechts en het linkerkind 𝑦 En op te nemen 𝑥 X 's plaats.

Visualisatie van rechtsrotatie: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Rechter rotatiestappen:

  1. Set En het linkerkind zijn van X .
  2. Beweging En is de rechter subboom van X 's linker subboom.
  3. Update de ouder van X En En .
  4. Update X de ouder om naar te wijzen En in plaats van X .
  5. Set En is het juiste kind van X .
  6. Update X de ouder van En .

Pseudocode van rechtsrotatie:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->links;  x->links = y->rechts;  if (y->right != NIL) { y->right->parent = x;  } y->ouder = x->ouder;  if (x->parent == nullptr) { root = y;  } else if (x == x->ouder->rechts) { x->ouder->rechts = y;  } anders { x->ouder->links = y;  } y->rechts = x;  x->ouder = y; }>

Wanneer rotaties uitvoeren?

Rotaties in rood-zwarte bomen worden doorgaans uitgevoerd tijdens invoegingen en verwijderingen om de eigenschappen van de boom te behouden. Hieronder staan ​​de scenario's voor rotaties:

1. Overtredingen na invoeging herstellen

Wanneer een nieuw knooppunt wordt ingevoegd, is dit altijd rood gekleurd. Dit kan schendingen van de eigenschappen van de Rood-Zwarte Boom veroorzaken, met name:

  • De wortel moet zijn zwart .
  • Rood knooppunten kunnen dat niet hebben rood kinderen.

Casusanalyse voor het fixeren van inserties:

  • Geval 1: Opnieuw kleuren en naar boven voortplanten
    • Als de ouder en de oom van het nieuwe knooppunt beide zijn rood , kleur de ouder en oom opnieuw in zwart , en de grootouder ook rood . Pas vervolgens de fix-up recursief toe op de grootouder.
  • Geval 2: Rotatie en opnieuw kleuren
    • Als de oom van het nieuwe knooppunt dat is zwart en het nieuwe knooppunt het rechterkind van een linkerkind is (of omgekeerd), voer een rotatie uit om het nieuwe knooppunt omhoog te verplaatsen en uit te lijnen.
    • Als de oom van het nieuwe knooppunt dat is zwart en het nieuwe knooppunt is het linkerkind van een linkerkind (of de rechterkant van een rechterkind), voer een rotatie uit en geef de ouder en grootouder een nieuwe kleur om de overtreding op te lossen.

2. Overtredingen na verwijdering herstellen

Na verwijdering moet de boom mogelijk worden gerepareerd om de eigenschappen te herstellen:

  • Wanneer een zwarte knoop wordt verwijderd, of een rode knoop wordt vervangen door een zwarte knoop, kan er een dubbelzwarte situatie ontstaan.

Casusanalyse voor het herstellen van verwijderingen:

  • Geval 1: Broer of zus is rood
    • Geef de broer of zus en de ouder een nieuwe kleur en voer een rotatie uit.
  • Geval 2: Broer of zus is zwart met zwarte kinderen
    • Kleur het broertje of zusje opnieuw in rood en verplaats het probleem naar de ouder.
  • Geval 3: Broer of zus is zwart met minstens één rood kind
    • Draai en kleur opnieuw om het probleem met dubbel zwart op te lossen.

Implementatie van Rood-Zwarte Boom:

Hier is een gedetailleerde implementatie van een rood-zwarte boom, inclusief invoeg-, zoek- en rotatiefuncties:

dynamische java-array
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->rechts;  x->rechts = y->links;  if (y->links!= NIL) { y->links->ouder = x;  } y->ouder = x->ouder;  if (x->parent == nullptr) { root = y;  } else if (x == x->ouder->links) { x->ouder->links = y;  } anders { x->bovenliggend->rechts = y;  } y->links = x;  x->ouder = y;  } // Hulpprogramma voor het uitvoeren van rotatie naar rechts void rightRotate(Node* x) { Node* y = x->left;  x->links = y->rechts;  if (y->right != NIL) { y->right->parent = x;  } y->ouder = x->ouder;  if (x->parent == nullptr) { root = y;  } else if (x == x->ouder->rechts) { x->ouder->rechts = y;  } anders { x->ouder->links = y;  } y->rechts = x;  x->ouder = y;  } // Functie om rood-zwarte boomeigenschappen te herstellen na // insertion void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->ouder == k->ouder->ouder->links) { Knooppunt* u = k->ouder->ouder->rechts; // oom if (u->kleur == 'ROOD') { k->ouder->kleur = 'ZWART';  u->kleur = 'ZWART';  k->ouder->ouder->kleur = 'ROOD';  k = k->ouder->ouder;  } else { if (k == k->ouder->rechts) { k = k->ouder;  linksRoteren(k);  } k->ouder->kleur = 'ZWART';  k->ouder->ouder->kleur = 'ROOD';  rightRotate(k->ouder->ouder);  } } else { Knooppunt* u = k->ouder->ouder->links; // oom if (u->kleur == 'ROOD') { k->ouder->kleur = 'ZWART';  u->kleur = 'ZWART';  k->ouder->ouder->kleur = 'ROOD';  k = k->ouder->ouder;  } else { if (k == k->ouder->links) { k = k->ouder;  rechtsRoteren(k);  } k->ouder->kleur = 'ZWART';  k->ouder->ouder->kleur = 'ROOD';  leftRotate(k->ouder->ouder);  } } } root->kleur = 'ZWART';  } // Inorder traversal helper function void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->left);  uit<< node->gegevens<< ' ';  inorderHelper(node->rechts);  } } // Zoekhulpfunctie Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } als (data< node->data) { return searchHelper(node->left, data);  } return searchHelper(knooppunt->rechts, data);  } public: // Constructor RedBlackTree() { NIL = nieuw knooppunt (0);  NIL->kleur = 'ZWART';  NIL->links = NIL->rechts = NIL;  wortel = NIL;  } // Functie invoegen void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL;  new_node->right = NIL;  Knooppunt* ouder = nullptr;  Knooppunt* huidig ​​= root;  // BST insert while (huidig!= NIL) { parent = huidig;  if (nieuwe_node->data< current->gegevens) { huidig ​​= huidig->links;  } anders { huidige = huidige->rechts;  } } new_node->parent = ouder;  if (ouder == nullptr) {root = nieuw_knooppunt;  } else if (new_node->data< parent->gegevens) { parent->left = new_node;  } else { parent->right = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'ZWART';  opbrengst;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(nieuwe_node);  } // Inorder traversal void inorder() { inorderHelper(root); } // Zoekfunctie Knooppunt* zoeken (int data) { return searchHelper (root, data);  } }; int main() {RedBlackTree rbt;  // Elementen invoegen rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(15);  // Ongeordende traversal cout<< '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; }>

Voordelen van rood-zwarte bomen:

  • Evenwichtig: Rood-zwarte bomen zijn zelfbalancerend, wat betekent dat ze automatisch een evenwicht handhaven tussen de hoogten van de linker- en rechtersubboom. Dit zorgt ervoor dat zoek-, invoeg- en verwijderbewerkingen in het ergste geval O(log n) tijd in beslag nemen.
  • Efficiënt zoeken, invoegen en verwijderen: Door hun evenwichtige structuur bieden Rood-Zwarte Bomen een efficiënte bedrijfsvoering. Zoeken, invoegen en verwijderen nemen in het ergste geval allemaal O(log n) tijd in beslag.
  • Eenvoudig te implementeren: De regels voor het onderhouden van de eigenschappen van de Rood-Zwarte Boom zijn relatief eenvoudig en eenvoudig te implementeren.
  • Veel gebruikt: Rood-zwarte bomen zijn een populaire keuze voor het implementeren van verschillende datastructuren, zoals kaarten, sets en prioriteitswachtrijen.

Nadelen van roodzwarte bomen:

  • Complexer dan andere gebalanceerde bomen: Vergeleken met eenvoudiger gebalanceerde bomen zoals AVL-bomen, hebben rood-zwarte bomen complexere regels voor het invoegen en verwijderen.
  • Constante overhead: Het behouden van de rood-zwarte boomeigenschappen voegt een kleine overhead toe aan elke invoeg- en verwijderingsbewerking.
  • Niet optimaal voor alle gebruiksscenario's: Hoewel ze efficiënt zijn voor de meeste bewerkingen, zijn Red-Black Trees misschien niet de beste keuze voor toepassingen waarbij frequente invoegingen en verwijderingen vereist zijn, omdat de constante overhead aanzienlijk kan worden.

Toepassingen van roodzwarte bomen:

  • Kaarten en sets implementeren: Rood-zwarte bomen worden vaak gebruikt om kaarten en sets te implementeren, waarbij efficiënt zoeken, invoegen en verwijderen cruciaal zijn.
  • Prioriteitswachtrijen: Rood-zwarte bomen kunnen worden gebruikt om prioriteitswachtrijen te implementeren, waarbij elementen worden geordend op basis van hun prioriteit.
  • Bestandssystemen: Rood-zwarte bomen worden in sommige bestandssystemen gebruikt om bestands- en mapstructuren te beheren.
  • In-memory databases: Rood-zwarte bomen worden soms gebruikt in databases in het geheugen om gegevens efficiënt op te slaan en op te halen.
  • Grafische en game-ontwikkeling: Rood-zwarte bomen kunnen worden gebruikt in graphics en games ontwikkeling voor taken zoals botsingsdetectie en padvinden.

Veelgestelde vragen (FAQ's) over rood-zwarte boom:

1. Wat is een rood-zwarte boom?

Een rood-zwarte boom is een zelfbalancerende binaire zoekboom die een evenwicht handhaaft tussen de hoogten van de linker- en rechtersubboom. Dit zorgt ervoor dat zoek-, invoeg- en verwijderbewerkingen in het ergste geval O(log n) tijd in beslag nemen. Rood-zwarte bomen worden veel gebruikt in verschillende toepassingen waar efficiënte datastructuren vereist zijn.

2. Hoe behoudt een roodzwarte boom zijn evenwicht?

Rood-zwarte bomen behouden hun evenwicht door specifieke regels af te dwingen voor de kleuren van knooppunten (ROOD of ZWART) en de relaties daartussen. Deze regels zorgen ervoor dat de boom in balans blijft en dat het hoogteverschil tussen de linker en rechter deelboom maximaal 1 bedraagt.

3. Wat zijn de voordelen van het gebruik van een rood-zwarte boom?

  • Evenwichtig: Rood-zwarte bomen zijn zelfbalancerend en zorgen voor efficiënte zoek-, invoeg- en verwijderbewerkingen.
  • Efficiënt: Ze bieden O(log n)-tijdcomplexiteit voor de meeste bewerkingen.
  • Eenvoudig te implementeren: De regels voor het behoud van de eigenschappen van de Rood-Zwarte Boom zijn relatief eenvoudig.
  • Veel gebruikt: Ze zijn een populaire keuze voor het implementeren van verschillende datastructuren en algoritmen.

4. Wat zijn de nadelen van het gebruik van een rood-zwarte boom?

  • Vergeleken met eenvoudiger gebalanceerde bomen zoals AVL-bomen, hebben rood-zwarte bomen complexere regels voor het invoegen en verwijderen.
  • Het behouden van de rood-zwarte boomeigenschappen voegt een kleine overhead toe aan elke invoeg- en verwijderingsbewerking.
  • Voor toepassingen met frequente invoegingen en verwijderingen kunnen andere gebalanceerde boomstructuren geschikter zijn.

5. Wat zijn enkele veel voorkomende toepassingen van roodzwarte bomen?

  • Implementeren van kaarten en sets
  • Prioriteitswachtrijen
  • Bestandssystemen
  • Databases in het geheugen
  • Grafische en game-ontwikkeling (botsingsdetectie, pathfinding)
  • Rood-zwarte boomdefinitie en betekenis in DSA
  • Zelfbalancerende binaire zoekbomen
  • Roodzwarte boom versus AVL-boom
  • Wat is het verschil tussen Heap en rood-zwarte boom?
  • Invoeging in rood-zwarte boom
  • Schrapping in rood-zwarte boom
  • Rood-zwarte bomen | Invoeging van boven naar beneden