logo

TechCodeview

Uvod v rdeče-črno drevo

Binarna iskalna drevesa so temeljni struktura podatkov, vendar lahko njihovo delovanje trpi, če drevo postane neuravnoteženo. Rdeča črna drevesa so vrsta uravnoteženo binarno iskalno drevo ki uporabljajo nabor pravil za vzdrževanje ravnotežja, kar zagotavlja logaritemsko časovno kompleksnost za operacije, kot je vstavljanje, brisanje in iskanje , ne glede na prvotno obliko drevesa. Rdeča črna drevesa se samouravnotežijo in uporabljajo preprosto shemo barvnega kodiranja za prilagajanje drevesa po vsaki spremembi.

Rdeče-črno drevo



Kazalo

c#

Kaj je rdeče-črno drevo?

A Rdeče-črno drevo je samouravnotežen binarno iskalno drevo kjer ima vsako vozlišče dodaten atribut: barvo, ki je lahko bodisi rdeča oz Črna . Primarni cilj teh dreves je ohraniti ravnovesje med vstavljanji in brisanjem, kar zagotavlja učinkovito pridobivanje podatkov in manipulacijo.

Lastnosti rdeče-črnih dreves

A Rdeče-črno drevo imajo naslednje lastnosti:



  1. Barva vozlišča : Vsako vozlišče je bodisi rdeče oz Črna .
  2. Korenska lastnost : Korenina drevesa je vedno Črna .
  3. Rdeča lastnina : Rdeča vozlišča ne morejo imeti rdečih otrok (na nobeni poti ni dveh zaporednih rdečih vozlišč).
  4. Črna lastnina : Vsaka pot od vozlišča do njegovih potomcev ničelnih vozlišč (listov) ima enako število Črna vozlišča.
  5. Lastnina listov : Vsi listi (NIL vozlišča) so Črna .

Te lastnosti zagotavljajo, da najdaljša pot od korenine do katerega koli lista ni več kot dvakrat daljša od najkrajše poti, kar ohranja ravnotežje in učinkovito delovanje drevesa.

Primer rdeče-črnega drevesa

The Pravilno rdeče-črno drevo na zgornji sliki zagotavlja, da ima vsaka pot od korenskega do listnega vozlišča enako število črnih vozlišč. V tem primeru obstaja eno (razen korenskega vozlišča).



The Napačno rdeče črno drevo ne sledi rdeče-črni lastnosti kot dva rdeča vozla mejijo drug na drugega. Druga težava je, da ima ena od poti do listnega vozlišča nič črnih vozlišč, medtem ko drugi dve vsebujeta črno vozlišče.

Zakaj rdeče-črna drevesa?

Večina operacij BST (npr. iskanje, max, min, vstavljanje, brisanje... itd.) traja O(h) čas, kjer je h višina BST . Stroški teh operacij lahko postanejo O(n) za poševno Binarno drevo. Če poskrbimo, da višina drevesa ostane O(log n) po vsakem vstavljanju in brisanju lahko zagotovimo zgornjo mejo O(log n) za vse te operacije. Višina rdeče-črnega drevesa je vedno O(log n) kjer je n število vozlišč v drevesu.

gospod št.AlgoritemČasovna zapletenost
1.IskanjeO(log n)
2.VstaviO(log n)
3.IzbrišiO(log n)

Primerjava z Drevo AVL :

Drevesa AVL so bolj uravnotežena v primerjavi z rdeče-črnimi drevesi, vendar lahko povzročijo več vrtenja med vstavljanjem in brisanjem. Torej, če vaša aplikacija vključuje pogosto vstavljanje in brisanje, potem je treba dati prednost rdeče-črnim drevesom. In če so vstavljanja in brisanja manj pogosta in je iskanje pogostejša operacija, potem AVL drevo imeti prednost pred rdeče-črnim drevesom.

Kako rdeče-črno drevo zagotavlja ravnovesje?

Preprost primer za razumevanje uravnoteženja je, da veriga treh vozlišč v rdeče-črnem drevesu ni mogoča. Lahko poskusimo katero koli kombinacijo barv in preverimo, ali vse kršijo lastnost rdeče-črnega drevesa.

Pravilna zgradba rdeče-črnega drevesa s tremi vozli

razvrsti matriko v Javi

Zanimivosti o rdeče-črnem drevesu:

  • The Črna višina rdeče-črnega drevesa je število črnih vozlišč na poti od korenskega vozlišča do listnega vozlišča. Listni vozli se prav tako štejejo kot Črna vozlišča. Torej, rdeče-črno drevo višine h ima črna višina>= h/2 .
  • Višina rdeče-črnega drevesa z n vozlišča je h<= 2 log 2 (n + 1) .
  • Vsi listi (NIL) so Črna .
  • The Črna globina vozlišča je definirana kot število črnih vozlišč od korena do tega vozlišča, tj. število črnih prednikov.

Osnovne operacije na rdeče-črnem drevesu:

Osnovne operacije na rdeče-črnem drevesu vključujejo:

  1. Vstavljanje
  2. Iskanje
  3. Izbris
  4. Rotacija

1. Vstavljanje

Vstavljanje novega vozlišča v rdeče-črno drevo vključuje postopek v dveh korakih: izvajanje standardnega vstavljanje binarnega iskalnega drevesa (BST). , čemur sledi popravljanje morebitnih kršitev lastnosti rdeče-črnih.

Koraki vstavljanja

  1. Vložek BST : Vstavite novo vozlišče kot v standardni BST.
  2. Odpravite kršitve :
    • Če je nadrejeni element novega vozlišča Črna , nobena lastnost ni kršena.
    • Če je starš rdeča , lahko drevo krši rdečo lastnino, kar zahteva popravke.

Odpravljanje kršitev med vstavljanjem

Po vstavitvi novega vozlišča kot a rdeča vozlišča, lahko naletimo na več primerov, odvisno od barv nadrejenega in strica vozlišča (brat nadrejenega):

  • Primer 1: Stric je Rdeč : Prebarvaj starša in strica v Črna , stari starši pa do rdeča . Nato se pomaknite po drevesu navzgor, da preverite nadaljnje kršitve.
  • Primer 2: Stric je črnec :
    • Podprimer 2.1: Vozlišče je desni otrok : Izvedite vrtenje v levo na staršu.
    • Podprimer 2.2: Vozlišče je levi otrok : Izvedite desno rotacijo starega starša in ustrezno prebarvajte.

2. Iskanje

Iskanje vozlišča v rdeče-črnem drevesu je podobno iskanju v standardu Binarno iskalno drevo (BST) . Iskalna akcija poteka po enostavni poti od korenina do a list , ki primerja ciljno vrednost z vrednostjo trenutnega vozlišča in se ustrezno premika levo ali desno.

Koraki iskanja

  1. Začnite pri korenu : Začnite iskanje pri korenskem vozlišču.
  2. Prečkaj drevo :
    • Če je ciljna vrednost enaka vrednosti trenutnega vozlišča, je vozlišče najdeno.
    • Če je ciljna vrednost manjša od vrednosti trenutnega vozlišča, se premaknite na levi podrejeni element.
    • Če je ciljna vrednost večja od vrednosti trenutnega vozlišča, se premaknite na desni podrejeni element.
  3. ponovi : Nadaljujte s tem postopkom, dokler ni najdena ciljna vrednost ali dokler ni doseženo vozlišče NIL (kar kaže, da vrednost ni prisotna v drevesu).

3. Izbris

Brisanje vozlišča iz rdeče-črnega drevesa prav tako vključuje postopek v dveh korakih: izvajanje brisanja BST, ki mu sledi popravljanje morebitnih kršitev, ki se pojavijo.

Koraki brisanja

  1. Brisanje BST : Odstranite vozlišče z uporabo standardnih pravil BST.
  2. Popravi dvojno črno :
    • Če je črno vozlišče izbrisano, se lahko pojavi dvojno črno stanje, ki zahteva posebne popravke.

Odpravljanje kršitev med brisanjem

Ko je črno vozlišče izbrisano, obravnavamo težavo z dvojno črno na podlagi barve sorodnika in barv njegovih otrok:

  • 1. primer: sorojenec je rdeč : Zasukajte starša in prebarvajte sorodnika in starša.
  • 2. primer: sorojenec je temnopolt :
    • Podprimer 2.1: Otroci brata in sestre so temnopolti : Prebarvajte sorodnika in razširite dvojno črno navzgor.
    • Podprimer 2.2: Vsaj eden od otrok brata in sestre je rdeč :
      • Če je sorojenčev daljni otrok rdeč : Izvedite rotacijo na staršu in bratu ter ustrezno prebarvajte.
      • Če je bližnji otrok sorojenca rdeč : Obrnite brata in njegovega otroka, nato pa ravnajte kot zgoraj.

4. Vrtenje

Rotacije so temeljne operacije pri ohranjanju uravnotežene strukture rdeče-črnega drevesa (RBT). Pomagajo ohranjati lastnosti drevesa in zagotavljajo, da najdaljša pot od korenine do katerega koli lista ni več kot dvakrat daljša od najkrajše poti. Rotacije so na voljo v dveh vrstah: levih vrtljajev in desne rotacije.

1. Leva rotacija

Leva rotacija na vozlišču 𝑥 x premika 𝑥 x navzdol na levo in njegov desni otrok 𝑦 in do prevzema 𝑥 x mesto.

Vizualizacija levega vrtenja 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Koraki vrtenja v levo:

  1. Set in biti pravi otrok x .
  2. Premakni se in je levo poddrevo do x desno poddrevo.
  3. Posodobite nadrejenega elementa x in in .
  4. Nadgradnja x starša, na katerega mora pokazati in namesto x .
  5. Set in je prepustil otroku x .
  6. Nadgradnja x njegov starš in .

Psevdokoda rotacije v levo:

Leva rotacija 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->prav;  x->desno = y->levo;  if (y->left != NIL) { y->left->parent = x;  } y->nadrejeni = x->nadrejeni;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->parent->right = y;  } y->levo = x;  x->nadrejeni = y; }>

2. Desna rotacija

Desna rotacija na vozlišču 𝑥 x premika 𝑥 x navzdol na desno in njegov levi otrok 𝑦 in do prevzema 𝑥 x mesto.

Vizualizacija desne rotacije: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Koraki vrtenja v desno:

  1. Set in biti levi otrok x .
  2. Premakni se in je desno poddrevo do x levo poddrevo.
  3. Posodobite nadrejenega elementa x in in .
  4. Nadgradnja x starša, na katerega mora pokazati in namesto x .
  5. Set in ima pravico do otroka x .
  6. Nadgradnja x njegov starš in .

Psevdokoda desne rotacije:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->levo;  x->levo = y->desno;  if (y->right != NIL) { y->right->parent = x;  } y->nadrejeni = x->nadrejeni;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->left = y;  } y->desno = x;  x->nadrejeni = y; }>

Kdaj izvajati rotacije?

Rotacije v rdeče-črnih drevesih se običajno izvajajo med vstavljanjem in brisanjem, da se ohranijo lastnosti drevesa. Spodaj so scenariji za rotacije:

1. Odpravljanje kršitev po vstavitvi

Ko je vstavljeno novo vozlišče, je vedno obarvano rdeče. To lahko povzroči kršitve lastnosti Red-Black Tree, zlasti:

  • Koren mora biti Črna .
  • rdeča vozlišča ne morejo imeti rdeča otroci.

Analiza primerov za popravljanje vstavkov:

  • Primer 1: Prebarvanje in razmnoževanje navzgor
    • Če sta starš in stric novega vozlišča oba rdeča , prebarvaj starša in strica na Črna , stari starši pa do rdeča . Nato rekurzivno uporabite popravek za starega starša.
  • 2. primer: vrtenje in prebarvanje
    • Če je stric novega vozlišča Črna in je novo vozlišče desni otrok levega otroka (ali obratno), izvedite rotacijo, da premaknete novo vozlišče navzgor in ga poravnate.
    • Če je stric novega vozlišča Črna in novo vozlišče je levi otrok levega otroka (ali desno od desnega), izvedite rotacijo in prebarvajte starša in starega starša, da odpravite kršitev.

2. Odpravljanje kršitev po izbrisu

Po izbrisu bo drevo morda treba popraviti za obnovitev lastnosti:

  • Ko črno vozlišče odstranimo ali rdeče vozlišče nadomestimo s črnim vozliščem, lahko pride do dvojno črne situacije.

Analiza primerov za popravljanje izbrisov:

  • 1. primer: sorojenec je rdeč
    • Prebarvajte brata in starša ter izvedite rotacijo.
  • 2. primer: sorojenec je temnopolt s črnimi otroki
    • Prebarvajte sorodnika v rdečo in težavo premaknite na starša.
  • Primer 3: brat ali sestra je temnopolta z vsaj enim rdečim otrokom
    • Zasukajte in prebarvajte, da odpravite težavo z dvojno črno barvo.

Izvedba rdeče-črnega drevesa:

Tukaj je podrobna izvedba rdeče-črnega drevesa, vključno s funkcijami vstavljanja, iskanja in vrtenja:

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->prav;  x->desno = y->levo;  if (y->left != NIL) { y->left->parent = x;  } y->nadrejeni = x->nadrejeni;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->parent->right = y;  } y->levo = x;  x->nadrejeni = y;  } // Pomožna funkcija za izvedbo rotacije v desno void rightRotate(Node* x) { Node* y = x->left;  x->levo = y->desno;  if (y->right != NIL) { y->right->parent = x;  } y->nadrejeni = x->nadrejeni;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->left = y;  } y->desno = x;  x->nadrejeni = y;  } // Funkcija za popravljanje lastnosti rdeče-črnega drevesa po // vstavitvi void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->nadrejeni == k->nadrejeni->nadrejeni->levo) { Vozlišče* u = k->nadrejeni->nadrejeni->desno; // stric if (u->color == 'RED') { k->parent->color = 'BLACK';  u->barva = 'ČRNA';  k->nadrejeni->nadrejeni->barva = 'RDEČA';  k = k->nadrejeni->nadrejeni;  } else { if (k == k->parent->right) { k = k->parent;  Zasukaj levo(k);  } k->nadrejeni->barva = 'ČRNA';  k->nadrejeni->nadrejeni->barva = 'RDEČA';  rightRotate(k->parent->parent);  } } else { Vozlišče* u = k->nadrejeni->nadrejeni->levo; // stric if (u->color == 'RED') { k->parent->color = 'BLACK';  u->barva = 'ČRNA';  k->nadrejeni->nadrejeni->barva = 'RDEČA';  k = k->nadrejeni->nadrejeni;  } else { if (k == k->parent->left) { k = k->parent;  Zasukaj desno(k);  } k->nadrejeni->barva = 'ČRNA';  k->nadrejeni->nadrejeni->barva = 'RDEČA';  leftRotate(k->parent->parent);  } } } koren->barva = 'ČRNA';  } // Funkcija pomočnika pri prehodu po vrstnem redu void inorderHelper(Node* vozlišče) { if (vozlišče != NIL) { inorderHelper(node->left);  cout<< node->podatke<< ' ';  inorderHelper(node->prav);  } } // Funkcija pomočnika pri iskanju Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } če (podatki< node->podatki) { return searchHelper(node->left, data);  } return searchHelper(node->right, data);  } public: // Konstruktor RedBlackTree() { NIL = novo vozlišče(0);  NIL->barva = 'ČRNA';  NIL->levo = NIL->desno = NIL;  koren = NIL;  } // Vstavi funkcijo void insert(int data) { Node* new_node = new Node(data);  novo_vozlišče->levo = NIČ;  novo_vozlišče->desno = NIČ;  Vozlišče* nadrejeni = nullptr;  Vozlišče* trenutni = koren;  // BST vstavi medtem ko (trenutno != NIL) { nadrejeni = trenutni;  če (novo_vozlišče->podatki< current->podatki) { trenutno = trenutno->levo;  } else { trenutno = trenutno->desno;  } } novo_vozlišče->nadrejeni = nadrejeni;  if (parent == nullptr) { root = new_node;  } else if (novo_vozlišče->podatki< parent->podatki) { nadrejeni->levo = novo_vozlišče;  } else { parent->right = novo_vozlišče;  } if (novo_vozlišče->nadrejeno == nullptr) { novo_vozlišče->barva = 'ČRNA';  vrnitev;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(novo_vozlišče);  } // Inorder traversal void inorder() { inorderHelper(root); } // Iskalna funkcija Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Vstavljanje elementov 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; }>

Prednosti rdeče-črnih dreves:

  • Uravnotežen: Rdeče-črna drevesa so samouravnotežena, kar pomeni, da samodejno vzdržujejo ravnotežje med višino levega in desnega poddrevesa. To zagotavlja, da operacije iskanja, vstavljanja in brisanja v najslabšem primeru trajajo O(log n).
  • Učinkovito iskanje, vstavljanje in brisanje: Rdeče-črna drevesa zaradi svoje uravnotežene strukture nudijo učinkovito delovanje. Iskanje, vstavljanje in brisanje v najslabšem primeru traja O(log n) časa.
  • Enostaven za izvedbo: Pravila za vzdrževanje lastnosti Red-Black Tree so razmeroma enostavna in enostavna za implementacijo.
  • Za široko uporabo: Rdeče-črna drevesa so priljubljena izbira za implementacijo različnih podatkovnih struktur, kot so zemljevidi, nizi in prednostne čakalne vrste.

Slabosti rdeče-črnih dreves:

  • Bolj zapleteno kot druga uravnotežena drevesa: V primerjavi s preprostejšimi uravnoteženimi drevesi, kot so drevesa AVL, imajo rdeče-črna drevesa bolj zapletena pravila za vstavljanje in brisanje.
  • Stalni režijski stroški: Vzdrževanje lastnosti rdeče-črnega drevesa dodaja majhen dodaten strošek vsaki operaciji vstavljanja in brisanja.
  • Ni optimalno za vse primere uporabe: Čeprav so učinkoviti za večino operacij, Rdeče-črna drevesa morda niso najboljša izbira za aplikacije, kjer so potrebni pogosti vstavitve in brisanja, saj lahko nenehni stroški postanejo precejšnji.

Uporaba rdeče-črnih dreves:

  • Implementacija zemljevidov in kompletov: Rdeče-črna drevesa se pogosto uporabljajo za implementacijo zemljevidov in nizov, kjer so učinkovito iskanje, vstavljanje in brisanje ključnega pomena.
  • Prednostne čakalne vrste: Rdeče-črna drevesa se lahko uporabljajo za implementacijo prednostnih čakalnih vrst, kjer so elementi razvrščeni glede na njihovo prioriteto.
  • Datotečni sistemi: Rdeče-črna drevesa se v nekaterih datotečnih sistemih uporabljajo za upravljanje struktur datotek in imenikov.
  • Baze podatkov v pomnilniku: Rdeče-črna drevesa se včasih uporabljajo v bazah podatkov v pomnilniku za učinkovito shranjevanje in pridobivanje podatkov.
  • Grafika in razvoj iger: Rdeče-črna drevesa se lahko uporabljajo v grafiki in igrah razvoj za naloge, kot sta zaznavanje trkov in iskanje poti.

Pogosto zastavljena vprašanja (FAQ) o Red-Black Tree:

1. Kaj je rdeče-črno drevo?

Rdeče-črno drevo je samouravnoteženo binarno iskalno drevo, ki ohranja ravnovesje med višinami svojega levega in desnega poddrevesa. To zagotavlja, da operacije iskanja, vstavljanja in brisanja v najslabšem primeru trajajo O(log n). Rdeče-črna drevesa se pogosto uporabljajo v različnih aplikacijah, kjer so potrebne učinkovite podatkovne strukture.

2. Kako rdeče-črno drevo ohranja ravnovesje?

Rdeče-črna drevesa vzdržujejo svoje ravnovesje z uveljavljanjem posebnih pravil o barvah vozlišč (RDEČA ali ČRNA) in razmerjih med njimi. Ta pravila zagotavljajo, da drevo ostane uravnoteženo in da je višinska razlika med levim in desnim poddrevesom največ 1.

pretvorbo niza v celo število

3. Kakšne so prednosti uporabe rdeče-črnega drevesa?

  • Uravnotežen: Rdeče-črna drevesa so samouravnotežena, kar zagotavlja učinkovito iskanje, vstavljanje in brisanje.
  • Učinkovito: Ponujajo O(log n) časovno kompleksnost za večino operacij.
  • Enostaven za izvedbo: Pravila za vzdrževanje lastnosti Red-Black Tree so razmeroma enostavna.
  • Za široko uporabo: So priljubljena izbira za implementacijo različnih podatkovnih struktur in algoritmov.

4. Kakšne so slabosti uporabe rdeče-črnega drevesa?

  • V primerjavi s preprostejšimi uravnoteženimi drevesi, kot so drevesa AVL, imajo rdeče-črna drevesa bolj zapletena pravila za vstavljanje in brisanje.
  • Vzdrževanje lastnosti rdeče-črnega drevesa dodaja majhen dodaten strošek vsaki operaciji vstavljanja in brisanja.
  • Za aplikacije s pogostim vstavljanjem in brisanjem so morda bolj primerne druge uravnotežene drevesne strukture.

5. Katere so nekatere pogoste uporabe rdeče-črnih dreves?

  • Izvajanje zemljevidov in sklopov
  • Prednostne čakalne vrste
  • Datotečni sistemi
  • Baze podatkov v pomnilniku
  • Grafika in razvoj iger (zaznavanje trkov, iskanje poti)
  • Definicija in pomen rdeče-črnega drevesa v DSA
  • Samouravnotežna binarna iskalna drevesa
  • Rdeče črno drevo proti drevesu AVL
  • Kakšna je razlika med Heap in Red-Black Tree?
  • Vstavljanje v rdeče-črno drevo
  • Izbris v rdeče-črnem drevesu
  • Rdeče-črna drevesa | Vstavljanje od zgoraj navzdol