logo

TechCodeview

Introduksjon til rød-svart tre

Binære søketrær er en grunnleggende data struktur, men ytelsen deres kan lide hvis treet blir ubalansert. Røde svarte trær er en type balansert binært søketre som bruker et sett med regler for å opprettholde balansen, og sikrer logaritmisk tidskompleksitet for operasjoner som innsetting, sletting og søking , uavhengig av den opprinnelige formen på treet. Røde svarte trær er selvbalanserende, ved å bruke et enkelt fargekodeskjema for å justere treet etter hver endring.

Rød-svart tre

Innholdsfortegnelse



beregning av ansettelsesforhold i excel

Hva er et rød-svart tre?

EN Rød-svart tre er en selvbalansering binært søketre hvor hver node har et tilleggsattributt: en farge, som kan være enten rød eller svart . Hovedmålet med disse trærne er å opprettholde balanse under innsetting og sletting, og sikre effektiv datainnhenting og manipulering.

Egenskaper til rød-svarte trær

EN Rød-svart tre har følgende egenskaper:

  1. Nodefarge : Hver node er enten rød eller svart .
  2. Root Property : Roten til treet er alltid svart .
  3. Rød eiendom : Røde noder kan ikke ha røde barn (ingen to påfølgende røde noder på noen bane).
  4. Svart eiendom : Hver vei fra en node til dens etterkommer nullnoder (blader) har samme antall svart noder.
  5. Leaf Eiendom : Alle blader (NIL-noder) er svart .

Disse egenskapene sikrer at den lengste veien fra roten til ethvert blad ikke er mer enn dobbelt så lang som den korteste veien, og opprettholder treets balanse og effektive ytelse.

Eksempel på rød-svart tre

js flerlinjet streng

De Riktig rød-svart tre i bildet ovenfor sikrer at hver vei fra roten til en bladnode har samme antall svarte noder. I dette tilfellet er det en (unntatt rotnoden).

De Feil rødt svart tre følger ikke de rød-svarte egenskapene som to røde noder ligger ved siden av hverandre. Et annet problem er at en av banene til en bladnode har null svarte noder, mens de to andre inneholder en svart node.

Hvorfor rød-svarte trær?

De fleste av BST-operasjonene (f.eks. søk, maks, min, sett inn, slett osv.) tar Åh) tid hvor h er høyden på BST . Kostnaden for disse operasjonene kan bli På) for en skjev Binært tre. Hvis vi sørger for at høyden på treet forblir O(log n) etter hver innsetting og sletting, så kan vi garantere en øvre grense for O(log n) for alle disse operasjonene. Høyden på et rød-svart tre er alltid O(log n) hvor n er antall noder i treet.

Mr. Nei.AlgoritmeTidskompleksitet
1.SøkO(log n)
2.Sett innO(log n)
3.SlettO(log n)

Sammenligning med AVL-tre :

AVL-trærne er mer balanserte sammenlignet med rød-svarte trær, men de kan forårsake flere rotasjoner under innsetting og sletting. Så hvis søknaden din involverer hyppige innsettinger og slettinger, bør rød-svarte trær foretrekkes. Og hvis innsettinger og slettinger er sjeldnere og søk er en hyppigere operasjon, da AVL-tre bør foretrekkes fremfor det rød-svarte treet.

Hvordan sikrer et rød-svart tre balanse?

Et enkelt eksempel for å forstå balansering er at en kjede med 3 noder ikke er mulig i det rød-svarte treet. Vi kan prøve hvilken som helst kombinasjon av farger og se om alle bryter med egenskapen rød-svart tre.

Riktig struktur av tre nodede rød-svart tre

Interessante poeng om Red-Black Tree:

  • De svart høyden på det rød-svarte treet er antall svarte noder på en sti fra rotnoden til en bladnoden. Bladnoder regnes også som svart noder. Så, et rød-svart tre med høyde h har svart høyde>= h/2 .
  • Høyde på et rød-svart tre med n noder er h<= 2 log 2 (n + 1) .
  • Alle blader (NIL) er svart .
  • De svart dybden til en node er definert som antall svarte noder fra roten til den noden, dvs. antall svarte forfedre.

Grunnleggende operasjoner på rød-svart tre:

De grunnleggende operasjonene på et rød-svart tre inkluderer:

iPhone-emojis på Android-telefon
  1. Innsetting
  2. Søk
  3. Sletting
  4. Rotasjon

1. Innsetting

Å sette inn en ny node i et rød-svart tre innebærer en to-trinns prosess: å utføre en standard innsetting av binært søketre (BST). , etterfulgt av å fikse eventuelle brudd på rød-svarte egenskaper.

Innsettingstrinn

  1. BST-innlegg : Sett inn den nye noden som i en standard BST.
  2. Rett opp brudd :
    • Hvis overordnet til den nye noden er svart , ingen egenskaper er krenket.
    • Hvis forelderen er rød , kan treet bryte med den røde egenskapen, som krever reparasjoner.

Retting av brudd under innsetting

Etter å ha satt inn den nye noden som en rød node, kan vi støte på flere tilfeller avhengig av fargene til nodens forelder og onkel (søsken til forelderen):

  • Tilfelle 1: Onkel er rød : Farge om forelderen og onkelen til svart , og besteforelderen til rød . Flytt deretter opp i treet for å se etter ytterligere brudd.
  • Tilfelle 2: Onkel er svart :
    • Deltilfelle 2.1: Node er et rett barn : Utfør en venstrerotasjon på forelderen.
    • Deltilfelle 2.2: Node er et venstrebarn : Utfør en høyrerotasjon på besteforelderen og farg på riktig måte.

2. Søking

Å søke etter en node i et rød-svart tre ligner på å søke i en standard Binært søketre (BST) . Søkeoperasjonen følger en grei vei fra rot til en blad , sammenligne målverdien med gjeldende nodes verdi og flytte til venstre eller høyre tilsvarende.

Søketrinn

  1. Start ved roten : Begynn søket ved rotnoden.
  2. Gå gjennom treet :
    • Hvis målverdien er lik den gjeldende nodens verdi, blir noden funnet.
    • Hvis målverdien er mindre enn den gjeldende nodens verdi, flytt til venstre underordnede.
    • Hvis målverdien er større enn den gjeldende nodens verdi, flytt til høyre underordnet.
  3. Gjenta : Fortsett denne prosessen til målverdien er funnet eller en NIL-node er nådd (som indikerer at verdien ikke er tilstede i treet).

3. Sletting

Å slette en node fra et rød-svart tre innebærer også en to-trinns prosess: å utføre BST-slettingen, etterfulgt av å fikse eventuelle brudd som oppstår.

Slettingstrinn

  1. BST-sletting : Fjern noden ved å bruke standard BST-regler.
  2. Fiks Double Black :
    • Hvis en svart node slettes, kan det oppstå en dobbel svart tilstand, som krever spesifikke rettelser.

Retting av brudd under sletting

Når en svart node slettes, håndterer vi problemet med dobbel svart basert på søskens farge og fargene til barna:

  • Tilfelle 1: Søsken er rød : Roter forelderen og farg søsken og forelder på nytt.
  • Tilfelle 2: Søsken er svart :
    • Undertilfelle 2.1: Søskens barn er svarte : Farg søskenet på nytt og forplant den doble sorten oppover.
    • Undertilfelle 2.2: Minst ett av søskenets barn er rødt :
      • Hvis søskens fjerne barn er rødt : Utfør en rotasjon på forelder og søsken, og farg på riktig måte.
      • Hvis søskens nærmeste barn er rødt : Roter søsken og barnet, og håndter deretter som ovenfor.

4. Rotasjon

Rotasjoner er grunnleggende operasjoner for å opprettholde den balanserte strukturen til et rød-svart tre (RBT). De bidrar til å bevare egenskapene til treet, og sikrer at den lengste veien fra roten til ethvert blad ikke er mer enn dobbelt så lang som den korteste veien. Rotasjoner kommer i to typer: venstre rotasjoner og høyre rotasjoner.

1. Venstre rotasjon

En venstrerotasjon ved node 𝑥 x beveger seg 𝑥 x ned til venstre og høyre barn 𝑦 og opp å ta 𝑥 x sin plass.

Visualisering av venstre roasjon 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Venstrerotasjonstrinn:

  1. Sett og å være det rette barnet til x .
  2. Bevege seg og sitt venstre undertre til x sitt høyre undertre.
  3. Oppdater forelderen til x og og .
  4. Oppdater x sin forelder å peke på og i stedet for x .
  5. Sett og 's venstre barn til x .
  6. Oppdater x sin forelder til og .

Pseudokode for venstrerotasjon:

Venstre rotasjon 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->Ikke sant;  x->høyre = y->venstre;  if (y->venstre != NIL) { y->venstre->forelder = x;  } y->forelder = x->forelder;  if (x->parent == nullptr) { rot = y;  } annet hvis (x == x->foreldre->venstre) { x->foreldre->venstre = y;  } annet { x->parent->right = y;  } y->venstre = x;  x->forelder = y; }>

2. Høyre rotasjon

En høyrerotasjon ved node 𝑥 x beveger seg 𝑥 x ned til høyre og venstre barn 𝑦 og opp å ta 𝑥 x sin plass.

innsettingssorteringsalgoritme
Visualisering av høyrerotasjon: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Høyre rotasjonstrinn:

  1. Sett og å være venstre barn av x .
  2. Bevege seg og sitt høyre undertre til x sitt venstre undertre.
  3. Oppdater forelderen til x og og .
  4. Oppdater x sin forelder å peke på og i stedet for x .
  5. Sett og sitt rette barn til x .
  6. Oppdater x sin forelder til og .

Pseudokode for høyrerotasjon:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->venstre;  x->venstre = y->høyre;  if (y->right != NIL) { y->right->parent = x;  } y->forelder = x->forelder;  if (x->parent == nullptr) { rot = y;  } else if (x == x->parent->right) { x->parent->right = y;  } annet { x->foreldre->venstre = y;  } y->høyre = x;  x->forelder = y; }>

Når skal man utføre rotasjoner?

Rotasjoner i rød-svarte trær utføres vanligvis under innsettinger og slettinger for å opprettholde egenskapene til treet. Nedenfor er scenariene for rotasjoner:

1. Retting av brudd etter innsetting

Når en ny node settes inn, er den alltid rød. Dette kan skape brudd på Red-Black Tree-egenskapene, spesielt:

  • Roten må være svart .
  • rød noder ikke kan ha rød barn.

Saksanalyse for fiksing av innsettinger:

  • Tilfelle 1: Omfarging og forplantning oppover
    • Hvis forelderen og onkelen til den nye noden er begge rød , recolor forelder og onkel til svart , og besteforelderen til rød . Påfør deretter reparasjonen rekursivt til besteforelderen.
  • Tilfelle 2: Rotasjon og nyfarging
    • Hvis den nye nodens onkel er svart og den nye noden er det høyre barnet til et venstre barn (eller omvendt), utfør en rotasjon for å flytte den nye noden opp og justere den.
    • Hvis den nye nodens onkel er svart og den nye noden er det venstre barnet til et venstre barn (eller høyre for et høyre), utfør en rotasjon og farg foreldrene og besteforelderen på nytt for å fikse bruddet.

2. Retting av brudd etter sletting

Etter sletting må treet kanskje fikses for å gjenopprette egenskaper:

  • Når en svart node fjernes, eller en rød node erstattes av en svart node, kan det oppstå en dobbel-svart situasjon.

Saksanalyse for å fikse slettinger:

vikas diviakirti
  • Tilfelle 1: Søsken er rød
    • Farg søsken og forelderen på nytt, og utfør en rotasjon.
  • Tilfelle 2: Søsken er svart med svarte barn
    • Farg søskenet på nytt til rødt og flytt problemet opp til forelderen.
  • Tilfelle 3: Søsken er svart med minst ett rødt barn
    • Roter og fargelegg på nytt for å fikse problemet med dobbelt-svart.

Implementering av rød-svart tre:

Her er en detaljert implementering av et rød-svart tre inkludert innsettings-, søk- og rotasjonsfunksjoner:

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->Ikke sant;  x->høyre = y->venstre;  if (y->venstre != NIL) { y->venstre->forelder = x;  } y->forelder = x->forelder;  if (x->parent == nullptr) { rot = y;  } annet hvis (x == x->foreldre->venstre) { x->foreldre->venstre = y;  } annet { x->parent->right = y;  } y->venstre = x;  x->forelder = y;  } // Verktøyfunksjon for å utføre høyrerotasjon void rightRotate(Node* x) { Node* y = x->venstre;  x->venstre = y->høyre;  if (y->right != NIL) { y->right->parent = x;  } y->forelder = x->forelder;  if (x->parent == nullptr) { rot = y;  } else if (x == x->parent->right) { x->parent->right = y;  } annet { x->foreldre->venstre = y;  } y->høyre = x;  x->forelder = y;  } // Funksjon for å fikse Red-Black Tree-egenskaper etter // insertion void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->foreldre == k->foreldre->foreldre->venstre) { Node* u = k->foreldre->foreldre->høyre; // onkel if (u->farge == 'RØD') { k->foreldre->farge = 'SORT';  u->farge = 'SORT';  k->foreldre->foreldre->farge = 'RØD';  k = k->foreldre->forelder;  } else { if (k == k->foreldre->høyre) { k = k->foreldre;  venstreRoter(k);  } k->foreldre->farge = 'SORT';  k->foreldre->foreldre->farge = 'RØD';  rightRotate(k->foreldre->foreldre);  } } else { Node* u = k->parent->parent->venstre; // onkel if (u->farge == 'RØD') { k->foreldre->farge = 'SORT';  u->farge = 'SORT';  k->foreldre->foreldre->farge = 'RØD';  k = k->foreldre->forelder;  } else { if (k == k->foreldre->venstre) { k = k->foreldre;  høyreRoter(k);  } k->foreldre->farge = 'SORT';  k->foreldre->foreldre->farge = 'RØD';  venstreRoter(k->foreldre->foreldre);  } } } root->color = 'SVART';  } // Inorder traversal helper function void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->venstre);  cout<< node->data<< ' ';  inorderHelper(node->Ikke sant);  } } // Søk hjelpefunksjon Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } hvis (data< node->data) { return searchHelper(node->venstre, data);  } return searchHelper(node->høyre, data);  } public: // Constructor RedBlackTree() { NIL = new Node(0);  NIL->farge = 'SORT';  NIL->venstre = NIL->høyre = NIL;  rot = NIL;  } // Insert function void insert(int data) { Node* new_node = new Node(data);  ny_node->venstre = NIL;  new_node->right = NIL;  Node* overordnet = nullptr;  Node* strøm = rot;  // BST insert while (current != NIL) { parent = current;  if (ny_node->data< current->data) { gjeldende = gjeldende->venstre;  } annet { gjeldende = gjeldende->høyre;  } } new_node->parent = overordnet;  if (foreldre == nullptr) { rot = ny_node;  } annet hvis (ny_node->data< parent->data) { overordnet->venstre = ny_node;  } else { parent->right = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'SVART';  komme tilbake;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(ny_node);  } // Inorder traversal void inorder() { inorderHelper(root); } // Søkefunksjon Node* søk(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Setter inn elementer rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(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; }>

Fordeler med rød-svarte trær:

  • Balansert: Rød-svarte trær er selvbalanserende, noe som betyr at de automatisk opprettholder en balanse mellom høydene til venstre og høyre undertrær. Dette sikrer at søk, innsetting og sletting tar O(log n) tid i verste fall.
  • Effektivt søk, innsetting og sletting: På grunn av sin balanserte struktur tilbyr rød-svarte trær effektiv drift. Søk, innsetting og sletting tar alle O(log n) tid i verste fall.
  • Enkel å implementere: Reglene for vedlikehold av Red-Black Tree-egenskapene er relativt enkle og greie å implementere.
  • Bredt brukt: Rød-svarte trær er et populært valg for å implementere ulike datastrukturer, for eksempel kart, sett og prioriterte køer.

Ulemper med rød-svarte trær:

  • Mer komplekse enn andre balanserte trær: Sammenlignet med enklere balanserte trær som AVL-trær, har rød-svarte trær mer komplekse regler for innsetting og sletting.
  • Konstant overhead: Ved å opprettholde egenskapene for rød-svart tre legges det til en liten overhead for hver innsettings- og slettingsoperasjon.
  • Ikke optimalt for alle brukstilfeller: Selv om det er effektivt for de fleste operasjoner, er rød-svarte trær kanskje ikke det beste valget for applikasjoner der hyppige innsettinger og slettinger er nødvendig, da den konstante overheaden kan bli betydelig.

Bruksområder for rød-svarte trær:

  • Implementering av kart og sett: Rød-svarte trær brukes ofte til å implementere kart og sett, hvor effektivt søk, innsetting og sletting er avgjørende.
  • Prioriterte køer: Rød-svarte trær kan brukes til å implementere prioriterte køer, der elementene er sortert basert på deres prioritet.
  • Filsystemer: Rød-svarte trær brukes i enkelte filsystemer for å administrere fil- og katalogstrukturer.
  • Databaser i minnet: Rød-svarte trær brukes noen ganger i databaser i minnet for å lagre og hente data effektivt.
  • Grafikk og spillutvikling: Rød-svarte trær kan brukes i grafikk og spill utvikling for oppgaver som kollisjonsdeteksjon og veisøking.

Ofte stilte spørsmål (FAQs) om rød-svart tre:

1. Hva er et rød-svart tre?

Et rød-svart tre er et selvbalanserende binært søketre som opprettholder en balanse mellom høydene til venstre og høyre undertrær. Dette sikrer at søk, innsetting og sletting tar O(log n) tid i verste fall. Rød-svarte trær er mye brukt i ulike applikasjoner der det kreves effektive datastrukturer.

2. Hvordan opprettholder et rød-svart tre balansen?

Rød-svarte trær opprettholder balansen ved å håndheve spesifikke regler for fargene på noder (RØD eller SVART) og forholdet mellom dem. Disse reglene sikrer at treet forblir balansert og at høydeforskjellen mellom venstre og høyre undertre er maksimalt 1.

3. Hva er fordelene med å bruke et rød-svart tre?

  • Balansert: Rød-svarte trær er selvbalanserende, og sikrer effektiv søking, innsetting og sletting.
  • Effektiv: De tilbyr O(log n) tidskompleksitet for de fleste operasjoner.
  • Enkel å implementere: Reglene for å vedlikeholde Red-Black Tree-egenskaper er relativt enkle.
  • Bredt brukt: De er et populært valg for implementering av ulike datastrukturer og algoritmer.

4. Hva er ulempene ved å bruke et rød-svart tre?

  • Sammenlignet med enklere balanserte trær som AVL-trær, har rød-svarte trær mer komplekse regler for innsetting og sletting.
  • Ved å opprettholde egenskapene for rød-svart tre legges det til en liten overhead for hver innsettings- og slettingsoperasjon.
  • For applikasjoner med hyppige innsettinger og slettinger kan andre balanserte trestrukturer være mer egnet.

5. Hva er noen vanlige bruksområder for rød-svarte trær?

  • Implementering av kart og sett
  • Prioriterte køer
  • Filsystemer
  • Databaser i minnet
  • Grafikk og spillutvikling (kollisjonsdeteksjon, stifinning)
  • Rød-svart tre definisjon og betydning i DSA
  • Selvbalanserende binære søketrær
  • Red Black Tree vs AVL Tree
  • Hva er forskjellen mellom Heap og Red-Black Tree?
  • Innsetting i rød-svart tre
  • Sletting i rød-svart tre
  • Rød-svarte trær | Topp-ned-innsetting