logo

TechCodeview

Úvod do Červeno-čierneho stromu

Binárne vyhľadávacie stromy sú základom dátová štruktúra, ale ich výkon môže utrpieť, ak sa strom stane nevyváženým. Červené čierne stromy sú typom vyvážený binárny vyhľadávací strom ktoré používajú súbor pravidiel na udržanie rovnováhy a zabezpečujú logaritmickú časovú zložitosť pre operácie ako napr vkladanie, mazanie a vyhľadávanie , bez ohľadu na počiatočný tvar stromu. Červené čierne stromy sú samovyvažujúce, využívajúce jednoduchú schému farebného kódovania na úpravu stromu po každej úprave.

Červeno-čierny strom



príkaz git push

Obsah

Čo je to červeno-čierny strom?

A Červeno-čierny strom je samovyvažovanie binárny vyhľadávací strom kde každý uzol má ďalší atribút: farbu, ktorá môže byť buď červená alebo čierna . Primárnym cieľom týchto stromov je udržiavať rovnováhu pri vkladaní a vymazávaní, čím sa zabezpečuje efektívne získavanie údajov a manipulácia s nimi.

Vlastnosti červeno-čiernych stromov

A Červeno-čierny strom majú nasledujúce vlastnosti:



  1. Farba uzla : Každý uzol je buď červený alebo čierna .
  2. Koreňová vlastnosť : Koreň stromu je vždy čierna .
  3. Červená nehnuteľnosť : Červené uzly nemôžu mať červené deti (žiadne dva po sebe idúce červené uzly na žiadnej ceste).
  4. Čierny majetok : Každá cesta od uzla k jeho podriadeným nulovým uzlom (listom) má rovnaký počet čierna uzly.
  5. Vlastnosť listu : Všetky listy (uzly NIL) sú čierna .

Tieto vlastnosti zaisťujú, že najdlhšia cesta od koreňa k akémukoľvek listu nie je viac ako dvakrát dlhšia ako najkratšia cesta, čím sa zachováva rovnováha stromu a efektívny výkon.

Príklad červeno-čierneho stromu

The Správny červeno-čierny strom na obrázku vyššie zaisťuje, že každá cesta od koreňa po listový uzol má rovnaký počet čiernych uzlov. V tomto prípade existuje jeden (okrem koreňového uzla).



The Nesprávny červený čierny strom nesleduje červeno-čierne vlastnosti ako dva červené uzly susedia navzájom. Ďalším problémom je, že jedna z ciest k listovému uzlu má nula čiernych uzlov, zatiaľ čo ostatné dve obsahujú čierny uzol.

dekódovať base64 javascript

Prečo červeno-čierne stromy?

Väčšina operácií BST (napr. vyhľadávanie, max, min, vloženie, vymazanie atď.) trvá O(h) čas, kde h je výška BST . Náklady na tieto operácie sa môžu zvýšiť O(n) za skreslený Binárny strom. Ak dbáme na to, aby výška stromu zostala O (log n) po každom vložení a vymazaní, potom môžeme zaručiť hornú hranicu O (log n) pre všetky tieto operácie. Výška červeno-čierneho stromu je vždy O (log n) kde n je počet uzlov v strome.

pán č.AlgoritmusČasová zložitosť
1.VyhľadávanieO (log n)
2.VložiťO (log n)
3.OdstrániťO (log n)

Porovnanie s AVL strom :

AVL stromy sú vyváženejšie v porovnaní s červeno-čiernymi stromami, ale môžu spôsobiť viac rotácií počas vkladania a odstraňovania. Takže ak vaša aplikácia zahŕňa časté vkladanie a mazanie, mali by ste uprednostniť červeno-čierne stromy. A ak sú vkladanie a vymazávanie menej časté a vyhľadávanie je častejšou operáciou, potom AVL strom by mal byť uprednostnený pred červeno-čiernym stromom.

Ako červeno-čierny strom zabezpečuje rovnováhu?

Jednoduchý príklad na pochopenie vyvažovania je, že reťazec 3 uzlov nie je možný v červeno-čiernom strome. Môžeme vyskúšať akúkoľvek kombináciu farieb a zistiť, či všetky porušujú vlastnosť stromu Červeno-čierna.

Správna štruktúra trojčlenného červeno-čierneho stromu

Zaujímavé body o červeno-čiernom strome:

  • The čierna výška červeno-čierneho stromu je počet čiernych uzlov na ceste od koreňového uzla po listový uzol. Listové uzliny sa tiež počítajú ako čierna uzly. Takže, červeno-čierny strom výšky h má výška čiernej>= h/2 .
  • Výška červeno-čierneho stromu s n uzly je h<= 2 log 2 (n + 1) .
  • Všetky listy (NIL) sú čierna .
  • The čierna hĺbka uzla je definovaná ako počet čiernych uzlov od koreňa k tomuto uzlu, t.j. počet čiernych predkov.

Základné operácie na červeno-čiernom strome:

Medzi základné operácie na červeno-čiernom strome patria:

  1. Vkladanie
  2. Vyhľadávanie
  3. Vymazanie
  4. Rotácia

1. Vkladanie

Vloženie nového uzla do červeno-čierneho stromu zahŕňa dvojkrokový proces: vykonanie štandardu vkladanie binárneho vyhľadávacieho stromu (BST). , po ktorom nasleduje oprava všetkých porušení červeno-čiernych vlastností.

mylivecricket v

Kroky vkladania

  1. Vložka BST : Vložte nový uzol ako v štandardnom BST.
  2. Opravte porušenia :
    • Ak je rodič nového uzla čierna , nie sú porušené žiadne vlastnosti.
    • Ak je rodič červená , strom môže porušovať červenú vlastnosť a vyžaduje opravy.

Oprava porušení počas vkladania

Po vložení nového uzla ako a červená uzol, môžeme sa stretnúť s niekoľkými prípadmi v závislosti od farieb rodiča a strýka uzla (súrodenca rodiča):

  • Prípad 1: Strýko je červený : Prefarbiť rodiča a strýka na čierna , a starý rodič do červená . Potom prejdite na strom a skontrolujte ďalšie porušenia.
  • Prípad 2: Strýko je čierny :
    • Podprípad 2.1: Uzol je správne dieťa : Vykonajte rotáciu doľava na rodičovi.
    • Podprípad 2.2: Node je ľavé dieťa : Vykonajte rotáciu vpravo na starom rodičovi a vhodne prefarbite.

2. Hľadanie

Hľadanie uzla v červeno-čiernom strome je podobné ako hľadanie v štandarde Binárny vyhľadávací strom (BST) . Operácia vyhľadávania sleduje priamu cestu z koreň do a list , porovnávajúc cieľovú hodnotu s hodnotou aktuálneho uzla a podľa toho sa posúvať doľava alebo doprava.

Kroky vyhľadávania

  1. Začnite pri koreni : Začnite vyhľadávanie v koreňovom uzle.
  2. Prejdite stromom :
    • Ak sa cieľová hodnota rovná hodnote aktuálneho uzla, uzol sa nájde.
    • Ak je cieľová hodnota menšia ako hodnota aktuálneho uzla, prejdite na ľavého potomka.
    • Ak je cieľová hodnota väčšia ako hodnota aktuálneho uzla, prejdite na správneho potomka.
  3. Opakujte : Pokračujte v tomto procese, kým sa nenájde cieľová hodnota alebo kým sa nedosiahne uzol NIL (čo znamená, že hodnota sa v strome nenachádza).

3. Vymazanie

Vymazanie uzla z červeno-čierneho stromu tiež zahŕňa dvojkrokový proces: vykonanie vymazania BST, po ktorom nasleduje oprava všetkých vzniknutých porušení.

Kroky odstraňovania

  1. Vymazanie BST : Odstráňte uzol pomocou štandardných pravidiel BST.
  2. Fix Double Black :
    • Ak sa odstráni čierny uzol, môže nastať stav dvojitej čiernej, ktorý si vyžaduje špecifické opravy.

Oprava porušení počas odstraňovania

Keď sa odstráni čierny uzol, riešime problém s dvojitou čiernou na základe farby súrodenca a farieb jeho detí:

  • Prípad 1: Súrodenec je červený : Otočte rodiča a prefarbite súrodenca a rodiča.
  • Prípad 2: Súrodenec je čierny :
    • Podprípad 2.1: Súrodencove deti sú čierne : Prefarbite súrodenca a propagujte dvojitú čiernu smerom nahor.
    • Podprípad 2.2: Aspoň jedno z detí súrodenca je červené :
      • Ak je vzdialené dieťa súrodenca červené : Vykonajte rotáciu na rodičovi a súrodencovi a vhodne prefarbite.
      • Ak je blízke dieťa súrodenca červené : Otočte súrodenca a jeho dieťa, potom postupujte podľa vyššie uvedeného.

4. Rotácia

Rotácie sú základnými operáciami pri udržiavaní vyváženej štruktúry červeno-čierneho stromu (RBT). Pomáhajú zachovať vlastnosti stromu a zabezpečujú, že najdlhšia cesta od koreňa k akémukoľvek listu nie je väčšia ako dvojnásobok dĺžky najkratšej cesty. Rotácie existujú v dvoch typoch: ľavé rotácie a pravé rotácie.

1. Otočenie doľava

Ľavá rotácia v uzle 𝑥 X pohyby 𝑥 X dole doľava a jeho pravé dieťa 𝑦 a až zobrať 𝑥 X miesto.

Vizualizácia ľavého chodu 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Kroky otáčania doľava:

  1. Set a byť tým správnym dieťaťom X .
  2. Pohybujte sa a 's ponechal podstrom do X pravý podstrom.
  3. Aktualizujte rodiča X a a .
  4. Aktualizovať X rodič, na ktorého sa má ukázať a namiesto X .
  5. Set a nechal dieťa X .
  6. Aktualizovať X rodič a .

Pseudokód rotácie doľava:

Ľavá rotácia 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->správny;  x->vpravo = y->vľavo;  if (y->vľavo != NIL) { y->vľavo->rodič = x;  } y->rodic = x->rodic;  if (x->rodic == nullptr) { root = y;  } else if (x == x->rodič->ľavý) { x->rodič->ľavý = y;  } else { x->rodic->pravo = y;  } y->vľavo = x;  x->rodič = y; }>

2. Pravá rotácia

Pravá rotácia v uzle 𝑥 X pohyby 𝑥 X dole napravo a jeho ľavé dieťa 𝑦 a až zobrať 𝑥 X miesto.

Vizualizácia rotácie doprava: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Kroky otáčania doprava:

  1. Set a byť ľavým dieťaťom X .
  2. Pohybujte sa a je pravý podstrom X ľavý podstrom.
  3. Aktualizujte rodiča X a a .
  4. Aktualizovať X rodič, na ktorého sa má ukázať a namiesto X .
  5. Set a to pravé dieťa X .
  6. Aktualizovať X rodič a .

Pseudokód rotácie doprava:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->vľavo;  x->vľavo = y->vpravo;  if (y->vpravo != NIL) { y->vpravo->rodic = x;  } y->rodic = x->rodic;  if (x->rodic == nullptr) { root = y;  } else if (x == x->rodič->vpravo) { x->rodič->vpravo = y;  } else { x->rodic->vľavo = y;  } y->vpravo = x;  x->rodič = y; }>

Kedy vykonávať rotácie?

Rotácie v červeno-čiernych stromoch sa zvyčajne vykonávajú počas vkladania a vymazávania, aby sa zachovali vlastnosti stromu. Nižšie sú uvedené scenáre rotácie:

herec govinda

1. Oprava porušení po vložení

Po vložení nového uzla je vždy zafarbený na červeno. To môže spôsobiť porušenie vlastností červeno-čierneho stromu, konkrétne:

  • Koreň musí byť čierna .
  • Červená uzly nemôžu mať červená deti.

Analýza prípadu na upevnenie vložiek:

  • Prípad 1: Prefarbenie a šírenie smerom nahor
    • Ak sú rodič a strýko nového uzla obaja červená , prefarbiť rodiča a strýka na čierna , a starý rodič do červená . Potom rekurzívne aplikujte opravu na starého rodiča.
  • Prípad 2: Rotácia a prefarbenie
    • Ak je strýko nového uzla čierna a nový uzol je pravým potomkom ľavého potomka (alebo naopak), vykonajte rotáciu, aby ste posunuli nový uzol nahor a zarovnali ho.
    • Ak je strýko nového uzla čierna a nový uzol je ľavé dieťa ľavého dieťaťa (alebo pravé právo), vykonajte rotáciu a prefarbite rodiča a starého rodiča, aby ste napravili porušenie.

2. Oprava porušení po vymazaní

Po odstránení môže strom potrebovať opravu, aby sa obnovili vlastnosti:

  • Keď sa odstráni čierny uzol alebo sa červený uzol nahradí čiernym, môže nastať situácia dvojitej čiernej.

Analýza prípadov na opravu vymazaní:

  • Prípad 1: Súrodenec je červený
    • Prefarbite súrodenca a rodiča a vykonajte rotáciu.
  • Prípad 2: Súrodenec je čierny s čiernymi deťmi
    • Prefarbite súrodenca na červenú a posuňte problém na rodiča.
  • Prípad 3: Súrodenec je čierny a má aspoň jedno červené dieťa
    • Problém s dvojitou čiernou opravíte otočením a prefarbením.

Implementácia červeno-čierneho stromu:

Tu je podrobná implementácia červeno-čierneho stromu vrátane funkcií vkladania, vyhľadávania a otáčania:

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->správny;  x->vpravo = y->vľavo;  if (y->vľavo != NIL) { y->vľavo->rodič = x;  } y->rodic = x->rodic;  if (x->rodic == nullptr) { root = y;  } else if (x == x->rodič->ľavý) { x->rodič->ľavý = y;  } else { x->rodic->pravo = y;  } y->vľavo = x;  x->rodič = y;  } // Pomôcka funkcia na vykonanie rotácie doprava void rightRotate(Node* x) { Node* y = x->left;  x->vľavo = y->vpravo;  if (y->vpravo != NIL) { y->vpravo->rodic = x;  } y->rodic = x->rodic;  if (x->rodic == nullptr) { root = y;  } else if (x == x->rodič->vpravo) { x->rodič->vpravo = y;  } else { x->rodic->vľavo = y;  } y->vpravo = x;  x->rodič = y;  } // Funkcia na opravu vlastností Red-Black Tree po // vložení void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->rodič == k->rodič->rodič->ľavý) { Uzol* u = k->rodič->rodič->vpravo; // strýko if (u->farba == 'ČERVENÁ') { k->rodič->farba = 'ČIERNA';  u->farba = 'ČIERNA';  k->rodic->rodic->farba = 'RED';  k = k->rodič->rodič;  } else { if (k == k->rodic->vpravo) { k = k->rodic;  doľavaRotate(k);  } k->rodic->farba = 'BLACK';  k->rodic->rodic->farba = 'RED';  rightRotate(k->rodič->rodič);  } } else { Uzol* u = k->rodic->rodic->vľavo; // strýko if (u->farba == 'ČERVENÁ') { k->rodič->farba = 'ČIERNA';  u->farba = 'ČIERNA';  k->rodic->rodic->farba = 'RED';  k = k->rodič->rodič;  } else { if (k == k->rodic->vľavo) { k = k->rodic;  dopravaRotate(k);  } k->rodic->farba = 'BLACK';  k->rodic->rodic->farba = 'RED';  doľavaRotate(k->rodič->rodič);  } } } root->color = 'BLACK';  } // Pomocná funkcia prechodu void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->left);  cout<< node->údajov<< ' ';  inorderHelper(node->správny);  } } // Pomocná funkcia vyhľadávania Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } if (údaje< node->data) { return searchHelper(uzol->left, data);  } return searchHelper(uzol->vpravo, data);  } public: // Konštruktor RedBlackTree() { NIL = new Node(0);  NIL->farba = 'ČIERNA';  NIL->vľavo = NIL->vpravo = NIL;  koreň = NIL;  } // Vloženie funkcie void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL;  novy_uzol->vpravo = NIL;  Node* parent = nullptr;  Uzol* aktuálny = koreň;  // BST vložiť while (aktuálne != NIL) { parent = current;  if (nový_uzol->údaje< current->data) { aktualny = aktualny->lavy;  } else { aktualny = aktualny->pravy;  } } novy_uzol->rodic = rodic;  if (rodič == nullptr) { root = novy_uzol;  } else if (nový_uzol->údaje< parent->data) { parent->left = novy_uzol;  } else { rodič->vpravo = nový_uzol;  } if (novy_uzol->rodic == nullptr) { novy_uzol->farba = 'BLACK';  návrat;  } if (novy_uzol->rodic->rodic == nullptr) { return;  } fixInsert(nový_uzol);  } // Inorder traversal void inorder() { inorderHelper(root); } // Funkcia vyhľadávania Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Vloženie prvkov 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; }>

Výhody červeno-čiernych stromov:

  • Vyvážené: Červeno-čierne stromy sú samovyvažujúce, čo znamená, že automaticky udržiavajú rovnováhu medzi výškami ľavého a pravého podstromu. To zaisťuje, že operácie vyhľadávania, vkladania a vymazávania budú v najhoršom prípade trvať O(log n).
  • Efektívne vyhľadávanie, vkladanie a odstraňovanie: Vďaka svojej vyváženej štruktúre ponúkajú Red-Black Trees efektívne operácie. Vyhľadávanie, vkladanie a mazanie trvá v najhoršom prípade čas O(log n).
  • Jednoduchá implementácia: Pravidlá udržiavania vlastností Červeno-čierneho stromu sú pomerne jednoduché a priamočiare na implementáciu.
  • Široko používané: Červeno-čierne stromy sú populárnou voľbou pre implementáciu rôznych dátových štruktúr, ako sú mapy, sady a prioritné fronty.

Nevýhody červeno-čiernych stromov:

  • Zložitejšie ako iné vyvážené stromy: V porovnaní s jednoduchšími vyváženými stromami, ako sú stromy AVL, majú Red-Black Trees zložitejšie pravidlá vkladania a odstraňovania.
  • Konštantná réžia: Udržiavanie vlastností Červeno-čierneho stromu pridáva malú réžiu každej operácii vkladania a vymazania.
  • Nie je optimálne pre všetky prípady použitia: Hoci sú Red-Black Trees účinné pre väčšinu operácií, nemusia byť najlepšou voľbou pre aplikácie, kde sa vyžaduje časté vkladanie a odstraňovanie, pretože neustále režijné náklady môžu byť značné.

Aplikácia červeno-čiernych stromov:

  • Implementácia máp a zostáv: Červeno-čierne stromy sa často používajú na implementáciu máp a súborov, kde je rozhodujúce efektívne vyhľadávanie, vkladanie a mazanie.
  • Prioritné fronty: Červeno-čierne stromy možno použiť na implementáciu prioritných frontov, kde sú prvky usporiadané na základe ich priority.
  • Systémy súborov: Červeno-čierne stromy sa používajú v niektorých súborových systémoch na správu súborových a adresárových štruktúr.
  • Databázy v pamäti: Červeno-čierne stromy sa niekedy používajú v databázach v pamäti na efektívne ukladanie a získavanie údajov.
  • Grafika a vývoj hier: Red-Black Trees možno použiť v grafike a hre rozvoj pre úlohy, ako je detekcia kolízií a hľadanie cesty.

Často kladené otázky (FAQ) o červeno-čiernom strome:

1. Čo je to červeno-čierny strom?

Červeno-čierny strom je samovyvažujúci binárny vyhľadávací strom, ktorý udržuje rovnováhu medzi výškami ľavého a pravého podstromu. To zaisťuje, že operácie vyhľadávania, vkladania a vymazávania budú v najhoršom prípade trvať O(log n). Red-Black Trees sú široko používané v rôznych aplikáciách, kde sa vyžadujú efektívne dátové štruktúry.

2. Ako si červeno-čierny strom udržiava rovnováhu?

Červeno-čierne stromy si udržiavajú rovnováhu tým, že presadzujú špecifické pravidlá pre farby uzlov (ČERVENÁ alebo ČIERNA) a vzťahy medzi nimi. Tieto pravidlá zabezpečujú, že strom zostane vyvážený a že výškový rozdiel medzi ľavým a pravým podstromom je najviac 1.

3. Aké sú výhody používania červeno-čierneho stromu?

  • Vyvážené: Red-Black Trees sú samovyvažujúce a zabezpečujú efektívne operácie vyhľadávania, vkladania a vymazávania.
  • Efektívne: Ponúkajú časovú zložitosť O(log n) pre väčšinu operácií.
  • Jednoduchá implementácia: Pravidlá udržiavania vlastností Červeno-čierneho stromu sú pomerne jednoduché.
  • Široko používané: Sú populárnou voľbou pre implementáciu rôznych dátových štruktúr a algoritmov.

4. Aké sú nevýhody používania Červeno-čierneho stromu?

  • V porovnaní s jednoduchšími vyváženými stromami, ako sú stromy AVL, majú Red-Black Trees zložitejšie pravidlá vkladania a odstraňovania.
  • Udržiavanie vlastností Červeno-čierneho stromu pridáva malú réžiu každej operácii vkladania a vymazania.
  • Pre aplikácie s častým vkladaním a vymazávaním môžu byť vhodnejšie iné vyvážené stromové štruktúry.

5. Aké sú niektoré bežné aplikácie červeno-čiernych stromov?

  • Implementácia máp a zostáv
  • Prioritné fronty
  • Súborové systémy
  • Databázy v pamäti
  • Grafika a vývoj hier (detekcia kolízií, hľadanie ciest)
  • Definícia a význam červeno-čierneho stromu v DSA
  • Samovyvažovacie binárne vyhľadávacie stromy
  • Red Black Tree vs AVL Tree
  • Aký je rozdiel medzi haldou a červeno-čiernym stromom?
  • Vloženie do červeno-čierneho stromu
  • Vymazanie v červeno-čiernom strome
  • Červeno-čierne stromy | Vkladanie zhora nadol