logo

TechCodeview

Introduktion til rød-sort træ

Binære søgetræer er et grundlæggende datastruktur, men deres ydeevne kan lide, hvis træet bliver ubalanceret. Røde sorte træer er en type balanceret binært søgetræ der bruger et sæt regler til at opretholde balancen, hvilket sikrer logaritmisk tidskompleksitet for operationer som f.eks indsættelse, sletning og søgning , uanset træets oprindelige form. Røde sorte træer er selvbalancerende ved at bruge et simpelt farvekodningsskema til at justere træet efter hver ændring.

Rød-sort træ



Indholdsfortegnelse

sql ordre efter dato

Hvad er et rød-sort træ?

EN Rød-sort træ er en selvbalancering binært søgetræ hvor hver node har en ekstra attribut: en farve, som kan være enten rød eller sort . Det primære formål med disse træer er at opretholde balance under indsættelser og sletninger, hvilket sikrer effektiv datahentning og manipulation.

Egenskaber af rød-sorte træer

EN Rød-sort træ har følgende egenskaber:



  1. Node farve : Hver knude er enten rød eller sort .
  2. Root Ejendom : Træets rod er altid sort .
  3. Rød Ejendom : Røde noder kan ikke have røde børn (ikke to på hinanden følgende røde noder på nogen sti).
  4. Sort Ejendom : Hver vej fra en node til dens efterkommer-nul noder (blade) har det samme antal sort noder.
  5. Bladejendom : Alle blade (NIL noder) er sort .

Disse egenskaber sikrer, at den længste vej fra roden til ethvert blad ikke er mere end dobbelt så lang som den korteste vej, hvilket bibeholder træets balance og effektive ydeevne.

Eksempel på rød-sort træ

git add --all

Det Korrekt rød-sort træ i ovenstående billede sikrer, at hver sti fra roden til en bladknude har det samme antal sorte knudepunkter. I dette tilfælde er der en (undtagen rodnoden).



Det Forkert rødt sort træ følger ikke de rød-sorte egenskaber som to røde knudepunkter ligger ved siden af ​​hinanden. Et andet problem er, at en af ​​stierne til en bladknude har nul sorte knudepunkter, hvorimod de to andre indeholder en sort knude.

Hvorfor rød-sorte træer?

De fleste af BST-operationerne (f.eks. søgning, max, min, indsæt, slet... osv.) tager O(h) tid hvor h er højden af BST . Omkostningerne ved disse operationer kan blive På) for en skæv Binært træ. Hvis vi sørger for, at træets højde forbliver O(log n) efter hver indsættelse og sletning, så kan vi garantere en øvre grænse for O(log n) for alle disse operationer. Højden af ​​et rød-sort træ er altid O(log n) hvor n er antallet af noder i træet.

Mr. Nej.AlgoritmeTidskompleksitet
1.SøgO(log n)
2.IndsætO(log n)
3.SletO(log n)

Sammenligning med AVL træ :

AVL-træerne er mere afbalancerede sammenlignet med rød-sorte træer, men de kan forårsage flere rotationer under indsættelse og sletning. Så hvis din ansøgning involverer hyppige indsættelser og sletninger, bør rød-sorte træer foretrækkes. Og hvis indsættelser og sletninger er mindre hyppige, og søgning er en hyppigere operation, så AVL træ bør foretrækkes frem for det rød-sorte træ.

Hvordan sikrer et rød-sort træ balance?

Et simpelt eksempel til at forstå balancering er, at en kæde af 3 noder ikke er mulig i det rød-sort træ. Vi kan prøve enhver kombination af farver og se, om de alle overtræder egenskaben Rød-Sort træ.

Korrekt struktur af tre nodede rød-sort træ

Interessante punkter om Red-Black Tree:

  • Det sort højden af ​​det rød-sorte træ er antallet af sorte noder på en sti fra rodknuden til en bladknude. Bladknuder tælles også som sort noder. Altså et rød-sort træ af højde h har sort højde>= h/2 .
  • Højde af et rød-sort træ med n noder er h<= 2 log 2 (n + 1) .
  • Alle blade (NIL) er sort .
  • Det sort dybden af ​​en node er defineret som antallet af sorte noder fra roden til den node, dvs. antallet af sorte forfædre.

Grundlæggende handlinger på rød-sort træ:

De grundlæggende handlinger på et rød-sort træ inkluderer:

java kerne java
  1. Indskud
  2. Søg
  3. Sletning
  4. Rotation

1. Indskud

Indsættelse af en ny node i et rød-sort træ involverer en to-trins proces: udførelse af en standard binært søgetræ (BST) indsættelse , efterfulgt af at rette eventuelle overtrædelser af rød-sort egenskaber.

Indsættelsestrin

  1. BST indsats : Indsæt den nye node som i en standard BST.
  2. Ret overtrædelser :
    • Hvis forælderen til den nye node er sort , ingen egenskaber krænkes.
    • Hvis forælderen er rød , kan træet krænke den røde egenskab, hvilket kræver rettelser.

Udbedring af overtrædelser under indsættelse

Efter at have indsat den nye node som en rød node, kan vi støde på flere tilfælde afhængigt af farverne på nodens forælder og onkel (forælderens søskende):

  • Case 1: Onkel er rød : Farve forælder og onkel om til sort , og bedsteforælderen til rød . Flyt derefter op i træet for at se efter yderligere overtrædelser.
  • Case 2: Onkel er sort :
    • Undertilfælde 2.1: Node er et ret barn : Udfør en venstredrejning på forælderen.
    • Undertilfælde 2.2: Node er et venstre barn : Udfør en højredrejning på bedsteforælderen og omfarv korrekt.

2. Søgning

At søge efter en node i et rød-sort træ svarer til at søge i en standard Binært søgetræ (BST) . Søgeoperationen følger en ligetil vej fra rod til en blad , sammenligner målværdien med den aktuelle nodes værdi og flytter til venstre eller højre i overensstemmelse hermed.

Søgetrin

  1. Start ved roden : Start søgningen ved rodnoden.
  2. Kør gennem træet :
    • Hvis målværdien er lig med den aktuelle nodes værdi, findes noden.
    • Hvis målværdien er mindre end den aktuelle nodes værdi, skal du flytte til venstre underordnede.
    • Hvis målværdien er større end den aktuelle nodes værdi, skal du flytte til det rigtige underordnede.
  3. Gentage : Fortsæt denne proces, indtil målværdien er fundet, eller en NIL-node er nået (hvilket indikerer, at værdien ikke er til stede i træet).

3. Sletning

Sletning af en node fra et rød-sort træ involverer også en to-trins proces: at udføre BST-sletningen, efterfulgt af at rette eventuelle overtrædelser, der opstår.

Sletningstrin

  1. BST sletning : Fjern noden ved hjælp af standard BST-regler.
  2. Fix Double Black :
    • Hvis en sort node slettes, kan der opstå en dobbelt sort tilstand, som kræver specifikke rettelser.

Udbedring af overtrædelser under sletning

Når en sort node slettes, håndterer vi problemet med dobbelt sort baseret på søskendens farve og dens børns farver:

  • Case 1: Søskende er rød : Roter forælderen og nyfarv søskende og forælder.
  • Case 2: Søskende er sort :
    • Undertilfælde 2.1: Søskendes børn er sorte : Farv søskende igen og forplant den dobbelte sorte opad.
    • Undertilfælde 2.2: Mindst et af søskendens børn er rødt :
      • Hvis søskendes fjerneste barn er rødt : Udfør en rotation på forælderen og søskende, og farve passende.
      • Hvis søskendes nærmeste barn er rødt : Drej søskende og dets barn, og håndter derefter som ovenfor.

4. Rotation

Rotationer er grundlæggende operationer til at opretholde den afbalancerede struktur af et rød-sort træ (RBT). De hjælper med at bevare træets egenskaber og sikrer, at den længste vej fra roden til ethvert blad ikke er mere end dobbelt så lang som den korteste vej. Rotationer findes i to typer: venstre rotationer og højre rotationer.

1. Venstre rotation

En venstredrejning ved node 𝑥 x bevæger sig 𝑥 x ned til venstre og dets højre barn 𝑦 og op at tage 𝑥 x sin plads.

Visualisering af venstre roation 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Venstre rotationstrin:

  1. Sæt og at være det rette barn af x .
  2. Bevæge sig og 's venstre undertræ til x 's højre undertræ.
  3. Opdater forælderen til x og og .
  4. Opdatering x sin forælder at pege på og i stedet for x .
  5. Sæt og 's efterladte barn til x .
  6. Opdatering x sin forælder til og .

Pseudokode for venstrerotation:

Venstre rotation 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->højre;  x->højre = y->venstre;  if (y->venstre != NIL) { y->venstre->forælder = x;  } y->forælder = x->forælder;  if (x->parent == nullptr) { root = y;  } andet hvis (x == x->forælder->venstre) { x->forælder->venstre = y;  } andet { x->forælder->højre = y;  } y->venstre = x;  x->forælder = y; }>

2. Højre rotation

En højrerotation ved node 𝑥 x bevæger sig 𝑥 x ned til højre og dets venstre barn 𝑦 og op at tage 𝑥 x sin plads.

java indeks
Visualisering af højrerotation: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Højre rotationstrin:

  1. Sæt og at være venstre barn af x .
  2. Bevæge sig og ’s højre undertræ til x 's venstre undertræ.
  3. Opdater forælderen til x og og .
  4. Opdatering x sin forælder at pege på og i stedet for x .
  5. Sæt og ’s rette barn til x .
  6. Opdatering x sin forælder til og .

Pseudokode for højrerotation:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->venstre;  x->venstre = y->højre;  if (y->right != NIL) { y->right->parent = x;  } y->forælder = x->forælder;  if (x->parent == nullptr) { root = y;  } andet hvis (x == x->forælder->højre) { x->forælder->højre = y;  } andet { x->forælder->venstre = y;  } y->højre = x;  x->forælder = y; }>

Hvornår skal man udføre rotationer?

Rotationer i rød-sorte træer udføres typisk under indsættelser og sletninger for at bevare træets egenskaber. Nedenfor er scenarierne for rotationer:

1. Udbedring af overtrædelser efter indsættelse

Når en ny node indsættes, er den altid farvet rød. Dette kan skabe krænkelser af Red-Black Tree-egenskaber, specifikt:

  • Roden skal være sort .
  • Rød noder ikke kan have rød børn.

Sagsanalyse for fiksering af indsættelser:

  • Tilfælde 1: Genfarvning og formering opad
    • Hvis forælder og onkel til den nye node er begge rød , omfarve forælder og onkel til sort , og bedsteforælderen til rød . Anvend derefter korrigeringen rekursivt til bedsteforælderen.
  • Tilfælde 2: Rotation og genfarvning
    • Hvis den nye nodes onkel er sort og den nye node er det højre underordnede af et venstre barn (eller omvendt), skal du udføre en rotation for at flytte den nye knude op og justere den.
    • Hvis den nye nodes onkel er sort og den nye node er venstre underordnede af et venstre barn (eller højre for et højre), udfør en rotation og omfarv forælderen og bedsteforælderen for at rette op på overtrædelsen.

2. Udbedring af overtrædelser efter sletning

Efter sletning skal træet muligvis rettes for at gendanne egenskaber:

  • Når en sort knude fjernes, eller en rød knude erstattes af en sort knude, kan der opstå en dobbelt-sort situation.

Sagsanalyse til rettelse af sletninger:

vikas diviakirti
  • Case 1: Søskende er rød
    • Farv søskende og forælder om, og udfør en rotation.
  • Case 2: Søskende er sort med sorte børn
    • Omfarv søskende til rød og flyt problemet op til forælderen.
  • Case 3: Søskende er sort med mindst ét ​​rødt barn
    • Roter og ny farve for at løse problemet med dobbelt-sort.

Implementering af rød-sort træ:

Her er en detaljeret implementering af et rød-sort træ inklusive indsættelses-, søge- og rotationsfunktioner:

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->højre;  x->højre = y->venstre;  if (y->venstre != NIL) { y->venstre->forælder = x;  } y->forælder = x->forælder;  if (x->parent == nullptr) { root = y;  } andet hvis (x == x->forælder->venstre) { x->forælder->venstre = y;  } andet { x->forælder->højre = y;  } y->venstre = x;  x->forælder = y;  } // Hjælpefunktion til at udføre højrerotation void rightRotate(Node* x) { Node* y = x->venstre;  x->venstre = y->højre;  if (y->right != NIL) { y->right->parent = x;  } y->forælder = x->forælder;  if (x->parent == nullptr) { root = y;  } andet hvis (x == x->forælder->højre) { x->forælder->højre = y;  } andet { x->forælder->venstre = y;  } y->højre = x;  x->forælder = y;  } // Funktion til at rette Red-Black Tree-egenskaber efter // insertion void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->forælder == k->forælder->forælder->venstre) { Node* u = k->forælder->forælder->højre; // onkel if (u->farve == 'RØD') { k->forælder->farve = 'SORT';  u->farve = 'SORT';  k->forælder->forælder->farve = 'RØD';  k = k->forælder->forælder;  } else { if (k == k->forælder->højre) { k = k->forælder;  venstreRoter(k);  } k->forælder->farve = 'SORT';  k->forælder->forælder->farve = 'RØD';  højreRoter(k->forælder->forælder);  } } else { Node* u = k->forælder->forælder->venstre; // onkel if (u->farve == 'RØD') { k->forælder->farve = 'SORT';  u->farve = 'SORT';  k->forælder->forælder->farve = 'RØD';  k = k->forælder->forælder;  } else { if (k == k->forælder->venstre) { k = k->forælder;  højreRoter(k);  } k->forælder->farve = 'SORT';  k->forælder->forælder->farve = 'RØD';  venstreRoter(k->forælder->forælder);  } } } root->color = 'SORT';  } // Inorder traversal helper function void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->venstre);  cout<< node->data<< ' ';  inorderHelper(node->højre);  } } // Søg hjælpefunktion Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } hvis (data< node->data) { return searchHelper(node->venstre, data);  } returner searchHelper(node->højre, data);  } public: // Constructor RedBlackTree() { NIL = new Node(0);  NIL->farve = 'SORT';  NIL->venstre = NIL->højre = NIL;  root = NIL;  } // Indsæt funktion void insert(int data) { Node* new_node = new Node(data);  new_node->venstre = NIL;  new_node->right = NIL;  Node* forælder = nullptr;  Node* strøm = rod;  // BST insert while (current != NIL) { parent = current;  if (ny_node->data< current->data) { aktuelle = nuværende->venstre;  } else { current = current->right;  } } new_node->forælder = forælder;  if (forælder == nullptr) { root = new_node;  } andet if (ny_node->data< parent->data) { parent->left = new_node;  } andet { parent->right = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'SORT';  Vend tilbage;  } if (ny_node->forælder->forælder == nullptr) { return;  } fixInsert(ny_node);  } // Inorder traversal void inorder() { inorderHelper(root); } // Søgefunktion Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Indsættelse af elementer rbt.insert(10);  rbt.indsæt(20);  rbt.indsæt(30);  rbt.indsæt(15);  // Inorder 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; }>

Fordele ved rød-sorte træer:

  • Balanceret: Rød-sorte træer er selvbalancerende, hvilket betyder, at de automatisk opretholder en balance mellem højden af ​​venstre og højre undertræ. Dette sikrer, at søgning, indsættelse og sletning tager O(log n) tid i værste fald.
  • Effektiv søgning, indsættelse og sletning: På grund af deres afbalancerede struktur tilbyder rød-sorte træer effektive operationer. Søgning, indsættelse og sletning tager alle O(log n) tid i værste fald.
  • Enkel at implementere: Reglerne for vedligeholdelse af rød-sort træ-egenskaberne er relativt enkle og ligetil at implementere.
  • Alment benyttet: Rød-sorte træer er et populært valg til implementering af forskellige datastrukturer, såsom kort, sæt og prioritetskøer.

Ulemper ved rød-sorte træer:

  • Mere komplekse end andre balancerede træer: Sammenlignet med simplere balancerede træer som AVL-træer har rød-sorte træer mere komplekse indsættelses- og sletningsregler.
  • Konstant overhead: Vedligeholdelse af egenskaberne for rød-sort træ tilføjer en lille overhead til hver indsættelses- og sletningsoperation.
  • Ikke optimalt til alle anvendelsestilfælde: Selvom de er effektive til de fleste operationer, er rød-sorte træer muligvis ikke det bedste valg til applikationer, hvor hyppige indsættelser og sletninger er påkrævet, da den konstante overhead kan blive betydelig.

Anvendelser af rød-sorte træer:

  • Implementering af kort og sæt: Rød-sorte træer bruges ofte til at implementere kort og sæt, hvor effektiv søgning, indsættelse og sletning er afgørende.
  • Prioriterede køer: Rød-sorte træer kan bruges til at implementere prioritetskøer, hvor elementer er ordnet baseret på deres prioritet.
  • Filsystemer: Rød-sorte træer bruges i nogle filsystemer til at administrere fil- og mappestrukturer.
  • In-memory databaser: Rød-sorte træer bruges nogle gange i databaser i hukommelsen til at gemme og hente data effektivt.
  • Grafik og spiludvikling: Rød-sorte træer kan bruges i grafik og spil udvikling til opgaver som kollisionsdetektion og stifinding.

Ofte stillede spørgsmål (ofte stillede spørgsmål) om rød-sort træ:

1. Hvad er et rød-sort træ?

Et rød-sort træ er et selvbalancerende binært søgetræ, der opretholder en balance mellem højden af ​​dets venstre og højre undertræ. Dette sikrer, at søgning, indsættelse og sletning tager O(log n) tid i værste fald. Rød-sorte træer er meget udbredt i forskellige applikationer, hvor der kræves effektive datastrukturer.

2. Hvordan opretholder et rød-sort træ sin balance?

Rød-sorte træer opretholder deres balance ved at håndhæve specifikke regler om farverne på noder (RØD eller SORT) og forholdet mellem dem. Disse regler sikrer, at træet forbliver afbalanceret, og at højdeforskellen mellem venstre og højre undertræ er højst 1.

3. Hvad er fordelene ved at bruge et rød-sort træ?

  • Balanceret: Rød-sorte træer er selvbalancerende, hvilket sikrer effektiv søgning, indsættelse og sletning.
  • Effektiv: De tilbyder O(log n) tidskompleksitet for de fleste operationer.
  • Enkel at implementere: Reglerne for vedligeholdelse af rød-sort træ-egenskaber er relativt ligetil.
  • Alment benyttet: De er et populært valg til implementering af forskellige datastrukturer og algoritmer.

4. Hvad er ulemperne ved at bruge et rød-sort træ?

  • Sammenlignet med simplere balancerede træer som AVL-træer har rød-sorte træer mere komplekse indsættelses- og sletningsregler.
  • Vedligeholdelse af egenskaberne for rød-sort træ tilføjer en lille overhead til hver indsættelses- og sletningsoperation.
  • Til applikationer med hyppige indsættelser og sletninger kan andre afbalancerede træstrukturer være mere egnede.

5. Hvad er nogle almindelige anvendelser af rød-sorte træer?

  • Implementering af kort og sæt
  • Prioriterede køer
  • Filsystemer
  • In-memory databaser
  • Grafik og spiludvikling (kollisionsdetektion, stifinding)
  • Rød-sort træ definition og betydning i DSA
  • Selvbalancerende binære søgetræer
  • Rød sort træ vs AVL træ
  • Hvad er forskellen mellem Heap og Red-Black Tree?
  • Indsættelse i rød-sort træ
  • Sletning i rød-sort træ
  • Rød-sorte træer | Top-down indsættelse