logo

TechCodeview

Úvod do Red-Black Tree

Binární vyhledávací stromy jsou základní datová struktura, ale jejich výkon může utrpět, pokud se strom stane nevyváženým. Červené černé stromy jsou typem vyvážený binární vyhledávací strom které používají sadu pravidel k udržení rovnováhy a zajišťují logaritmickou časovou složitost pro operace, jako je vkládání, mazání a vyhledávání , bez ohledu na počáteční tvar stromu. Červené černé stromy jsou samovyvažující a používají jednoduché schéma barevného kódování k úpravě stromu po každé úpravě.

Červeno-černý strom



Obsah

Co je to červeno-černý strom?

A Červeno-černý strom je samovyvažování binární vyhledávací strom kde každý uzel má další atribut: barvu, která může být buď Červené nebo Černá . Primárním cílem těchto stromů je udržovat rovnováhu během vkládání a mazání, což zajišťuje efektivní vyhledávání a manipulaci s daty.

Vlastnosti červeno-černých stromů

A Červeno-černý strom mají následující vlastnosti:



  1. Barva uzlu : Každý uzel je buď červený nebo Černá .
  2. Kořenová vlastnost : Kořen stromu je vždy Černá .
  3. Červená nemovitost : Červené uzly nemohou mít červené potomky (žádné dva po sobě jdoucí červené uzly na žádné cestě).
  4. Černý majetek : Každá cesta od uzlu k jeho podřízeným nulovým uzlům (listům) má stejný počet Černá uzly.
  5. Vlastnost listu : Všechny listy (uzly NIL) jsou Černá .

Tyto vlastnosti zajišťují, že nejdelší cesta od kořene k jakémukoli listu není více než dvakrát delší než nejkratší cesta, čímž je zachována rovnováha stromu a efektivní výkon.

Příklad červeno-černého stromu

The Správný červeno-černý strom na obrázku výše zajišťuje, že každá cesta z kořene do listového uzlu má stejný počet černých uzlů. V tomto případě existuje jeden (kromě kořenového uzlu).



The Nesprávný červený černý strom nesleduje červeno-černé vlastnosti jako dva červené uzly sousedí spolu. Dalším problémem je, že jedna z cest k listovému uzlu má nula černých uzlů, zatímco ostatní dvě obsahují černý uzel.

Proč červeno-černé stromy?

Většina operací BST (např. vyhledávání, max., min., vkládání, mazání atd.) trvá Ach) čas, kde h je výška BST . Náklady na tyto operace se mohou zvýšit Na) za zkreslený Binární strom. Pokud dbáme na to, aby zůstala výška stromu O(log n) po každém vložení a smazání pak můžeme zaručit horní hranici O(log n) pro všechny tyto operace. Výška červeno-černého stromu je vždy O(log n) kde n je počet uzlů ve stromu.

pan č.AlgoritmusČasová složitost
1.VyhledáváníO(log n)
2.VložitO(log n)
3.VymazatO(log n)

Srovnání s Strom AVL :

Stromy AVL jsou vyváženější ve srovnání s stromy Red-Black Trees, ale mohou způsobit více rotací během vkládání a mazání. Pokud tedy vaše aplikace zahrnuje časté vkládání a mazání, pak by měly být preferovány stromy Red-Black. A pokud jsou vkládání a mazání méně časté a vyhledávání je častější operací, pak strom AVL by měl mít přednost před červeno-černým stromem.

Jak červeno-černý strom zajišťuje rovnováhu?

Jednoduchým příkladem pro pochopení balancování je, že řetěz 3 uzlů není možný v červeno-černém stromu. Můžeme vyzkoušet libovolnou kombinaci barev a zjistit, zda všechny porušují vlastnost stromu Red-Black.

stlc

Správná struktura tříčlenného červeno-černého stromu

Zajímavosti o Red-Black Tree:

  • The Černá výška červeno-černého stromu je počet černých uzlů na cestě od kořenového uzlu k listovému uzlu. Uzly listů se také počítají jako Černá uzly. Takže červeno-černý strom výšky h má výška černé>= h/2 .
  • Výška červeno-černého stromu s n uzly je h<= 2 log 2 (n + 1) .
  • Všechny listy (NIL) jsou Černá .
  • The Černá hloubka uzlu je definována jako počet černých uzlů od kořene k tomuto uzlu, tj. počet černých předků.

Základní operace na Red-Black Tree:

Mezi základní operace na červeno-černém stromě patří:

  1. Vložení
  2. Vyhledávání
  3. Vymazání
  4. Otáčení

1. Vložení

Vložení nového uzlu do červeno-černého stromu zahrnuje dvoukrokový proces: provedení standardu vkládání binárního vyhledávacího stromu (BST). , po kterém následuje oprava všech porušení červeno-černých vlastností.

Kroky vkládání

  1. Vložka BST : Vložte nový uzel jako ve standardním BST.
  2. Opravte porušení :
    • Pokud je rodič nového uzlu Černá , nejsou porušeny žádné vlastnosti.
    • Pokud je rodič Červené , strom může porušovat Red Property a vyžadovat opravy.

Oprava porušení během vkládání

Po vložení nového uzlu jako a Červené uzel, můžeme se setkat s několika případy v závislosti na barvách rodiče a strýce uzlu (sourozenec rodiče):

  • Případ 1: Strýček je červený : Přebarvit rodiče a strýce na Černá , a prarodič do Červené . Poté se posuňte po stromě a zkontrolujte další porušení.
  • Případ 2: Strýček je černý :
    • Podpřípad 2.1: Uzel je správné dítě : Proveďte rotaci doleva na rodiči.
    • Dílčí případ 2.2: Uzel je levé podřízené : Proveďte otočení vpravo na prarodičích a vhodně přebarvěte.

2. Hledání

Hledání uzlu v červeno-černém stromě je podobné hledání ve standardu Binární vyhledávací strom (BST) . Vyhledávací operace sleduje přímou cestu z vykořenit do a list , porovnává cílovou hodnotu s hodnotou aktuálního uzlu a podle toho se pohybuje doleva nebo doprava.

Kroky vyhledávání

  1. Začněte u kořene : Začněte hledat v kořenovém uzlu.
  2. Projděte strom :
    • Pokud je cílová hodnota rovna hodnotě aktuálního uzlu, bude uzel nalezen.
    • Pokud je cílová hodnota menší než hodnota aktuálního uzlu, přejděte k levému potomkovi.
    • Pokud je cílová hodnota větší než hodnota aktuálního uzlu, přesuňte se na pravého potomka.
  3. Opakovat : Pokračujte v tomto procesu, dokud není nalezena cílová hodnota nebo dokud není dosaženo uzlu NIL (což znamená, že hodnota není přítomna ve stromu).

3. Vymazání

Odstranění uzlu z Červeno-černého stromu také zahrnuje dvoustupňový proces: provedení odstranění BST, po kterém následuje oprava všech porušení, která nastanou.

Kroky odstranění

  1. Vymazání BST : Odstraňte uzel pomocí standardních pravidel BST.
  2. Fix Double Black :
    • Pokud je černý uzel odstraněn, může nastat stav dvojité černé, který vyžaduje specifické opravy.

Oprava porušení během mazání

Když je odstraněn černý uzel, řešíme problém s dvojitou černou na základě barvy sourozence a barev jeho potomků:

  • Případ 1: Sourozenec je červený : Otočte rodiče a přebarvěte sourozence a rodiče.
  • Případ 2: Sourozenec je černý :
    • Podpřípad 2.1: Děti sourozenců jsou černé : Přebarvit sourozence a rozšířit dvojitou černou nahoru.
    • Podpřípad 2.2: Alespoň jedno z dětí sourozence je červené :
      • Pokud je vzdálené dítě sourozence červené : Proveďte otočení u rodiče a sourozence a odpovídajícím způsobem přebarvěte.
      • Pokud je blízké dítě sourozence červené : Otočte sourozence a jeho dítě a zacházejte jako výše.

4. Rotace

Rotace jsou základní operace při udržování vyvážené struktury červeno-černého stromu (RBT). Pomáhají zachovat vlastnosti stromu a zajišťují, že nejdelší cesta od kořene k libovolnému listu není větší než dvojnásobek délky nejkratší cesty. Rotace existují ve dvou typech: levé rotace a pravé rotace.

1. Levá rotace

Levá rotace v uzlu 𝑥 X pohyby 𝑥 X dolů nalevo a jeho pravé dítě 𝑦 a až k odběru 𝑥 X místo.

Vizualizace levé rotace 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Kroky otáčení doleva:

  1. Soubor a být tím správným dítětem X .
  2. Hýbat se a 's vlevo podstrom k X pravý podstrom.
  3. Aktualizujte nadřazenou položku X a a .
  4. Aktualizace X rodič, na kterého má ukázat a namísto X .
  5. Soubor a nechal dítě X .
  6. Aktualizace X jeho rodič a .

Pseudokód rotace vlevo:

Levá rotace 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->že jo;  x->vpravo = y->vlevo;  if (y->levý != NIL) { y->levý->rodič = x;  } y->rodič = x->rodič;  if (x->parent == nullptr) { root = y;  } else if (x == x->rodič->vlevo) { x->rodič->vlevo = y;  } else { x->rodič->vpravo = y;  } y->vlevo = x;  x->rodič = y; }>

2. Pravá rotace

Pravá rotace v uzlu 𝑥 X pohyby 𝑥 X dolů vpravo a jeho levé dítě 𝑦 a až k odběru 𝑥 X místo.

Vizualizace pravé rotace: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Kroky otáčení vpravo:

  1. Soubor a být levým dítětem X .
  2. Hýbat se a je pravý podstrom k X levý podstrom.
  3. Aktualizujte nadřazenou položku X a a .
  4. Aktualizace X rodič, na kterého má ukázat a namísto X .
  5. Soubor a to správné dítě X .
  6. Aktualizace X jeho rodič a .

Pseudokód pravé rotace:

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

Kdy provádět rotace?

Rotace v červeno-černých stromech se obvykle provádějí během vkládání a mazání, aby se zachovaly vlastnosti stromu. Níže jsou scénáře pro rotace:

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

Po vložení nového uzlu je vždy zbarven červeně. To může způsobit porušení vlastností Červeno-černého stromu, konkrétně:

  • Kořen musí být Černá .
  • Červené uzly nemohou mít Červené děti.

Analýza případu pro upevnění vložek:

  • Případ 1: Přebarvení a šíření nahoru
    • Pokud jsou rodiče a strýc nového uzlu oba Červené , přebarvit rodiče a strýce na Černá , a prarodič do Červené . Poté rekurzivně aplikujte opravu na prarodiče.
  • Případ 2: Rotace a přebarvení
    • Pokud je strýcem nového uzlu Černá a nový uzel je pravým potomkem levého potomka (nebo naopak), proveďte rotaci, abyste posunuli nový uzel nahoru a zarovnali jej.
    • Pokud je strýcem nového uzlu Černá a nový uzel je levý potomek levého potomka (nebo pravý pravý), proveďte rotaci a přebarvěte rodiče a prarodiče, abyste napravili porušení.

2. Oprava porušení po smazání

Po odstranění může strom potřebovat opravu, aby se obnovily vlastnosti:

  • Když je odstraněn černý uzel nebo je červený uzel nahrazen černým, může nastat situace dvojité černé.

Analýza případu pro opravu odstranění:

  • Případ 1: Sourozenec je červený
    • Znovu vybarvěte sourozence a rodiče a proveďte rotaci.
  • Případ 2: Sourozenec je černý s černými dětmi
    • Přebarvi sourozence na červenou a přesuňte problém na rodiče.
  • Případ 3: Sourozenec je černý s alespoň jedním červeným dítětem
    • Otočte a znovu vybarvěte problém s dvojitou černou.

Realizace Red-Black Tree:

Zde je podrobná implementace červeno-černého stromu včetně funkcí vkládání, vyhledávání a otáčení:

návod na reakci js
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->že jo;  x->vpravo = y->vlevo;  if (y->levý != NIL) { y->levý->rodič = x;  } y->rodič = x->rodič;  if (x->parent == nullptr) { root = y;  } else if (x == x->rodič->vlevo) { x->rodič->vlevo = y;  } else { x->rodič->vpravo = y;  } y->vlevo = x;  x->rodič = y;  } // Obslužná funkce pro provedení rotace doprava void rightRotate(Node* x) { Node* y = x->left;  x->vlevo = y->vpravo;  if (y->vpravo != NIL) { y->vpravo->rodič = x;  } y->rodič = x->rodič;  if (x->parent == nullptr) { root = y;  } else if (x == x->rodič->vpravo) { x->rodič->vpravo = y;  } else { x->rodič->vlevo = y;  } y->vpravo = x;  x->rodič = y;  } // Funkce pro 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č->vlevo) { Uzel* u = k->rodič->rodič->vpravo; // strýček if (u->barva == 'ČERVENÁ') { k->rodič->barva = 'ČERNÁ';  u->barva = 'ČERNÁ';  k->rodič->rodič->barva = 'ČERVENÁ';  k = k->rodič->rodič;  } else { if (k == k->rodic->vpravo) { k = k->rodic;  dolevaRotate(k);  } k->rodič->barva = 'ČERNÁ';  k->rodič->rodič->barva = 'ČERVENÁ';  rightRotate(k->rodič->rodič);  } } else { Uzel* u = k->rodic->rodic->vlevo; // strýček if (u->barva == 'ČERVENÁ') { k->rodič->barva = 'ČERNÁ';  u->barva = 'ČERNÁ';  k->rodič->rodič->barva = 'ČERVENÁ';  k = k->rodič->rodič;  } else { if (k == k->rodic->vlevo) { k = k->rodic;  rightRotate(k);  } k->rodič->barva = 'ČERNÁ';  k->rodič->rodič->barva = 'ČERVENÁ';  leftRotate(k->parent->parent);  } } } root->color = 'BLACK';  } // Pomocná funkce pro procházení void inorderHelper(Node* node) { if (uzel != NIL) { inorderHelper(uzel->left);  cout<< node->data<< ' ';  inorderHelper(node->že jo);  } } // Pomocná funkce hledání Node* searchHelper(Uzel* uzel, int data) { if (uzel == NIL || data == uzel->data) { return uzel;  } if (data< node->data) { return searchHelper(uzel->left, data);  } return searchHelper(uzel->vpravo, data);  } public: // Konstruktor RedBlackTree() { NIL = new Node(0);  NIL->barva = 'ČERNÁ';  NIL->levý = NIL->pravý = NIL;  kořen = NIL;  } // Vložení funkce void insert(int data) { Uzel* novy_uzel = new Uzel(data);  novy_uzel->vlevo = NIL;  novy_uzel->vpravo = NIL;  Node* parent = nullptr;  Uzel* aktuální = kořen;  // vložení BST while (aktuální != NIL) { rodič = aktuální;  if (nový_uzel->data< current->data) { aktuální = aktuální->levý;  } else { aktuální = aktuální->pravý;  } } nový_uzel->rodič = rodič;  if (rodič == nullptr) { root = nový_uzel;  } else if (nový_uzel->data< parent->data) { parent->left = novy_uzel;  } else { rodič->vpravo = nový_uzel;  } if (novy_uzel->rodic == nullptr) { novy_uzel->barva = 'BLACK';  vrátit se;  } if (nový_uzel->rodič->rodič == nullptr) { return;  } fixInsert(nový_uzel);  } // Inorder traversal void inorder() { inorderHelper(root); } // Funkce hledání Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Vkládání prvků 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-černých stromů:

  • Vyrovnaný: Červeno-černé stromy jsou samovyrovnávací, což znamená, že automaticky udržují rovnováhu mezi výškami levého a pravého podstromu. To zajišťuje, že operace vyhledávání, vkládání a mazání zaberou v nejhorším případě čas O(log n).
  • Efektivní vyhledávání, vkládání a mazání: Díky své vyvážené struktuře nabízejí Red-Black Trees efektivní operace. Vyhledávání, vkládání a mazání trvá v nejhorším případě čas O(log n).
  • Jednoduchá implementace: Pravidla pro zachování vlastností Red-Black Tree jsou poměrně jednoduchá a přímočará na implementaci.
  • Široce používaný: Red-Black Trees jsou oblíbenou volbou pro implementaci různých datových struktur, jako jsou mapy, sady a prioritní fronty.

Nevýhody červeno-černých stromů:

  • Složitější než jiné vyvážené stromy: Ve srovnání s jednoduššími vyváženými stromy, jako jsou stromy AVL, mají Red-Black Trees složitější pravidla pro vkládání a mazání.
  • Konstantní režie: Zachování vlastností Red-Black Tree přidává malou režii každé operaci vkládání a mazání.
  • Není optimální pro všechny případy použití: Přestože jsou Red-Black Trees efektivní pro většinu operací, nemusí být nejlepší volbou pro aplikace, kde je vyžadováno časté vkládání a mazání, protože neustálá režie může být významná.

Aplikace červeno-černých stromů:

  • Implementace map a sad: Red-Black Trees se často používají k implementaci map a sad, kde je klíčové efektivní vyhledávání, vkládání a mazání.
  • Prioritní fronty: Červeno-černé stromy lze použít k implementaci prioritních front, kde jsou prvky seřazeny podle priority.
  • Souborové systémy: Červeno-černé stromy se používají v některých souborových systémech ke správě struktur souborů a adresářů.
  • Databáze v paměti: Červeno-černé stromy se někdy používají v databázích uložených v paměti k efektivnímu ukládání a získávání dat.
  • Grafika a vývoj her: Red-Black Trees lze použít v grafice a hře rozvoj pro úkoly, jako je detekce kolizí a hledání cesty.

Často kladené otázky (FAQ) o Red-Black Tree:

1. Co je to červeno-černý strom?

Červeno-černý strom je samovyvažující binární vyhledávací strom, který udržuje rovnováhu mezi výškami levého a pravého podstromu. To zajišťuje, že operace vyhledávání, vkládání a mazání zaberou v nejhorším případě čas O(log n). Red-Black Trees jsou široce používány v různých aplikacích, kde jsou vyžadovány efektivní datové struktury.

2. Jak si červeno-černý strom udržuje rovnováhu?

Červeno-černé stromy si udržují rovnováhu tím, že prosazují specifická pravidla pro barvy uzlů (ČERVENÁ nebo ČERNÁ) a vztahy mezi nimi. Tato pravidla zajišťují, že strom zůstane vyvážený a že výškový rozdíl mezi levým a pravým podstromem je maximálně 1.

3. Jaké jsou výhody použití červeno-černého stromu?

  • Vyrovnaný: Red-Black Trees jsou samovyvažující a zajišťují efektivní operace vyhledávání, vkládání a mazání.
  • Účinný: Nabízejí časovou složitost O(log n) pro většinu operací.
  • Jednoduchá implementace: Pravidla pro udržování vlastností Red-Black Tree jsou poměrně jednoduchá.
  • Široce používaný: Jsou oblíbenou volbou pro implementaci různých datových struktur a algoritmů.

4. Jaké jsou nevýhody použití červeno-černého stromu?

  • Ve srovnání s jednoduššími vyváženými stromy, jako jsou stromy AVL, mají Red-Black Trees složitější pravidla pro vkládání a mazání.
  • Zachování vlastností Red-Black Tree přidává malou režii každé operaci vkládání a mazání.
  • Pro aplikace s častým vkládáním a mazáním mohou být vhodnější jiné vyvážené stromové struktury.

5. Jaké jsou některé běžné aplikace Red-Black Trees?

  • Implementace map a sad
  • Prioritní fronty
  • Souborové systémy
  • In-memory databáze
  • Grafika a vývoj her (detekce kolize, hledání cest)
  • Definice a význam červeno-černého stromu v DSA
  • Samovyrovnávací binární vyhledávací stromy
  • Red Black Tree vs AVL Tree
  • Jaký je rozdíl mezi haldou a červeno-černým stromem?
  • Vložení do červeno-černého stromu
  • Smazání v červeno-černém stromě
  • Červeno-černé stromy | Vkládání shora dolů