logo

TechCodeview

Įvadas į raudonai juodą medį

Dvejetainiai paieškos medžiai yra esminiai duomenų struktūra, tačiau jų veikimas gali nukentėti, jei medis išsibalansuoja. Raudoni juodi medžiai yra tipas subalansuotas dvejetainis paieškos medis kurie naudoja taisyklių rinkinį, kad išlaikytų pusiausvyrą, užtikrinant logaritminį laiko sudėtingumą tokioms operacijoms kaip įterpimas, ištrynimas ir paieška , nepriklausomai nuo pradinės medžio formos. Raudoni juodi medžiai yra savaime išsibalansuojantys, naudojant paprastą spalvų kodavimo schemą, kad po kiekvieno modifikavimo pakoreguotų medį.

Raudonas-Juodas medis



Turinys

Kas yra raudonai juodas medis?

A Raudonas-Juodas medis yra savibalansas dvejetainis paieškos medis kur kiekvienas mazgas turi papildomą atributą: spalvą, kuri gali būti bet kuri raudona arba juodas . Pagrindinis šių medžių tikslas yra išlaikyti pusiausvyrą įterpiant ir ištrinant, užtikrinant veiksmingą duomenų gavimą ir manipuliavimą.

Raudonai juodų medžių savybės

A Raudonas-Juodas medis turi šias savybes:



  1. Mazgo spalva : kiekvienas mazgas yra raudonas arba juodas .
  2. Šakninė nuosavybė : Medžio šaknis visada juodas .
  3. Raudonasis turtas : Raudonieji mazgai negali turėti raudonų antrųjų (nėra dviejų iš eilės raudonų mazgų jokiame kelyje).
  4. Juodoji nuosavybė : Kiekvienas kelias nuo mazgo iki jo palikuonių nulinių mazgų (lapų) turi tą patį skaičių juodas mazgai.
  5. Lapų nuosavybė : Visi lapai (NIL mazgai) yra juodas .

Šios savybės užtikrina, kad ilgiausias kelias nuo šaknies iki bet kurio lapo yra ne daugiau kaip du kartus ilgesnis už trumpiausią kelią, išlaikant medžio pusiausvyrą ir efektyvų veikimą.

Raudonai juodo medžio pavyzdys

The Teisingas raudonai juodas medis aukščiau pateiktame paveikslėlyje užtikrina, kad kiekvienas kelias nuo šaknies iki lapo mazgo turi tiek pat juodųjų mazgų. Šiuo atveju yra vienas (išskyrus šakninį mazgą).



The Neteisingas raudonas juodas medis nesilaiko raudonos-juodos savybės kaip du raudoni mazgai yra greta vienas kito. Kita problema yra ta, kad viename iš kelių į lapo mazgą nėra juodų mazgų, o kituose dviejuose yra juodas mazgas.

Kodėl raudonai juodi medžiai?

Dauguma BST operacijų (pvz., paieška, maksimalus, min., įterpimas, ištrynimas.. ir tt) atliekamos Oi) laikas, kur h yra aukštis BST . Šių operacijų kaina gali tapti O(n) už iškreiptą Dvejetainis medis. Jeigu pasirūpinsime, kad medžio aukštis išliktų O(log n) po kiekvieno įterpimo ir ištrynimo galime garantuoti viršutinę ribą O(log n) visoms šioms operacijoms. Raudonai juodo medžio aukštis visada yra O(log n) kur n yra medžio mazgų skaičius.

ponas Nr.AlgoritmasLaiko sudėtingumas
1.PaieškaO(log n)
2.ĮdėtiO(log n)
3.IštrintiO(log n)

Palyginimas su AVL medis :

AVL medžiai yra labiau subalansuoti, palyginti su raudonai juodais medžiais, tačiau įterpiant ir ištrinant jie gali sukelti daugiau apsisukimų. Taigi, jei jūsų programa dažnai įterpiama ir ištrinama, pirmenybė turėtų būti teikiama raudonai juodiems medžiams. Ir jei įterpimai ir ištrynimai atliekami rečiau, o paieška yra dažnesnė operacija, tada AVL medis turėtų būti teikiama pirmenybė raudonai juodam medžiui.

Kaip raudonai juodas medis užtikrina pusiausvyrą?

Paprastas pavyzdys, kaip suprasti balansavimą, yra tas, kad 3 mazgų grandinė neįmanoma raudonai juodame medyje. Galime išbandyti bet kokį spalvų derinį ir pažiūrėti, ar visi jie nepažeidžia raudono-juodo medžio savybę.

reaguoti inline stiliumi

Tinkama trijų mazgų raudonai juodo medžio struktūra

Įdomūs punktai apie raudonai juodą medį:

  • The juodas raudonai juodo medžio aukštis yra juodų mazgų skaičius kelyje nuo šaknies mazgo iki lapo mazgo. Lapų mazgai taip pat skaičiuojami kaip juodas mazgai. Taigi, raudonai juodas aukščio medis h turi juodas aukštis>= h/2 .
  • Raudonai juodo medžio aukštis su n mazgai yra h<= 2 žurnalai 2 (n + 1) .
  • Visi lapai (NIL) yra juodas .
  • The juodas mazgo gylis apibrėžiamas kaip juodųjų mazgų skaičius nuo šaknies iki to mazgo, ty juodųjų protėvių skaičius.

Pagrindinės operacijos su raudonai juodu medžiu:

Pagrindinės operacijos su raudonai juodu medžiu apima:

  1. Įdėjimas
  2. Paieška
  3. Ištrynimas
  4. Rotacija

1. Įdėjimas

Naujo mazgo įterpimas į raudonai juodą medį apima dviejų etapų procesą: standartinio dvejetainio paieškos medžio (BST) įterpimas , po to pašalinami visi raudonai juodos spalvos savybių pažeidimai.

Įdėjimo žingsniai

  1. BST įdėklas : Įdėkite naują mazgą kaip į standartinį BST.
  2. Ištaisyti pažeidimus :
    • Jei naujo mazgo pirminis yra juodas , jokios savybės nepažeidžiamos.
    • Jei tėvas yra raudona , medis gali pažeisti raudonąją ypatybę, todėl reikia pataisyti.

Pažeidimų taisymas įdėjimo metu

Įdėjus naują mazgą kaip a raudona mazgas, galime susidurti su keliais atvejais, priklausomai nuo mazgo tėvo ir dėdės (tėvo brolio) spalvų:

  • 1 atvejis: dėdė raudonas : perspalvinkite tėvą ir dėdę juodas , o senelis į raudona . Tada pakelkite medį ir patikrinkite, ar nėra kitų pažeidimų.
  • 2 atvejis: dėdė juodaodis :
    • 2.1 antrinis atvejis: Mazgas yra tinkamas vaikas : atlikite pirminį pasukimą į kairę.
    • 2.2 antrinis atvejis: Mazgas yra kairysis vaikas : tinkamai pasukite senelį ir atitinkamai pakeiskite spalvą.

2. Ieškoma

Mazgo paieška raudonai juodame medyje yra panaši į paiešką standartiniame Dvejetainis paieškos medis (BST) . Paieškos operacija atliekama paprastu keliu nuo šaknis į a lapelis , lygindami tikslinę vertę su dabartinio mazgo reikšme ir atitinkamai judėdami kairėn arba dešinėn.

Paieškos žingsniai

  1. Pradėkite nuo šaknies : pradėkite paiešką nuo šakninio mazgo.
  2. Pereikite per medį :
    • Jei tikslinė vertė yra lygi dabartinio mazgo vertei, mazgas randamas.
    • Jei tikslinė vertė yra mažesnė už dabartinę mazgo vertę, pereikite prie kairiojo antrinio.
    • Jei tikslinė vertė yra didesnė už dabartinę mazgo vertę, pereikite prie tinkamo antrinio.
  3. Pakartokite : Tęskite šį procesą, kol bus rasta tikslinė reikšmė arba pasiektas NIL mazgas (tai reiškia, kad reikšmės medyje nėra).

3. Ištrynimas

Mazgo ištrynimas iš raudonai juodo medžio taip pat apima dviejų etapų procesą: atliekamas BST trynimas, po kurio pašalinami visi atsiradę pažeidimai.

Ištrynimo žingsniai

  1. BST ištrynimas : pašalinkite mazgą naudodami standartines BST taisykles.
  2. Pataisykite Double Black :
    • Jei juodas mazgas bus ištrintas, gali atsirasti dvigubos juodos būsenos, kurią reikia pataisyti.

Pažeidimų šalinimas ištrynimo metu

Kai juodas mazgas ištrinamas, dvigubos juodos spalvos problemą sprendžiame atsižvelgdami į brolio ir seserų spalvą ir jo vaikų spalvas:

  • 1 atvejis: sesuo yra raudona : pasukite tėvą ir perspalvinkite brolį ir seserį bei tėvą.
  • 2 atvejis: sesuo yra juodaodis :
    • 2.1 atvejis: brolių ir seserų vaikai yra juodaodžiai : perspalvinkite brolį ir pakelkite dvigubą juodą spalvą aukštyn.
    • 2.2 atvejis: bent vienas iš brolių ir seserų vaikų yra raudonas :
      • Jei tolimasis brolio vaikas yra raudonas : sukite vieną iš tėvų ir seserų ir atitinkamai pakeiskite spalvą.
      • Jei šalia esančio brolio ir sesers vaikas yra raudonas : Pasukite brolį ir seserį ir jo vaiką, tada elkitės taip, kaip nurodyta aukščiau.

4. Rotacija

Sukimai yra pagrindinės operacijos, padedančios išlaikyti subalansuotą raudonai juodo medžio (RBT) struktūrą. Jie padeda išsaugoti medžio savybes, užtikrina, kad ilgiausias kelias nuo šaknies iki bet kurio lapo būtų ne daugiau kaip du kartus didesnis už trumpiausią kelią. Sukimai būna dviejų tipų: sukimai į kairę ir teisingi sukimai.

1. Pasukimas į kairę

Pasukimas į kairę mazge 𝑥 x juda 𝑥 x žemyn į kairę ir jo dešinįjį vaiką 𝑦 ir iki pasiimti 𝑥 x vieta.

Kairiojo sukimosi vizualizacija 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Sukimo į kairę žingsniai:

  1. Nustatyti ir būti tinkamu vaiku x .
  2. Judėti ir ’s paliko pomedį į x dešinysis pomedis.
  3. Atnaujinkite tėvą x ir ir .
  4. Atnaujinti x tėvas, į kurį reikia atkreipti dėmesį ir vietoj x .
  5. Nustatyti ir ’s paliko vaiką x .
  6. Atnaujinti x o tėvas ir .

Kairėn sukimosi pseudokodas:

Rotacija į kairę 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->teisė;  x->dešinė = y->kairė;  if (y->left != NIL) { y->left->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { šaknis = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->parent->right = y;  } y->kairė = x;  x->tėvas = y; }>

2. Pasukimas į dešinę

Teisingas sukimasis mazge 𝑥 x juda 𝑥 x žemyn į dešinę ir jo kairįjį vaiką 𝑦 ir iki pasiimti 𝑥 x vieta.

Dešiniojo sukimosi vizualizacija: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Dešiniojo sukimosi žingsniai:

  1. Nustatyti ir būti kairiuoju vaiku x .
  2. Judėti ir ’s dešinysis pomedis x kairysis pomedis.
  3. Atnaujinkite tėvą x ir ir .
  4. Atnaujinti x tėvas, į kurį reikia atkreipti dėmesį ir vietoj x .
  5. Nustatyti ir tinkamas vaikas x .
  6. Atnaujinti x o tėvas ir .

Dešiniojo sukimosi pseudokodas:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->kairėje;  x->kairė = y->dešinė;  if (y->right != NIL) { y->right->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { šaknis = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->left = y;  } y->dešinė = x;  x->tėvas = y; }>

Kada atlikti sukimus?

Pasukimai raudonai juoduose medžiuose paprastai atliekami įterpiant ir ištrinant, kad būtų išlaikytos medžio savybės. Toliau pateikiami sukimosi scenarijai:

1. Pažeidimų taisymas po įdėjimo

Kai įterpiamas naujas mazgas, jis visada būna raudonos spalvos. Tai gali pažeisti raudonai juodo medžio savybes, ypač:

  • Šaknis turi būti juodas .
  • Raudona mazgai negali turėti raudona vaikai.

Atvejo analizė, skirta taisyti intarpus:

  • 1 atvejis: perspalvinimas ir dauginimas aukštyn
    • Jei naujojo mazgo tėvas ir dėdė yra abu raudona , perdažykite tėvą ir dėdę juodas , o senelis į raudona . Tada rekursyviai pritaikykite taisymą seneliui.
  • 2 atvejis: sukimas ir perspalvinimas
    • Jei naujojo mazgo dėdė yra juodas o naujasis mazgas yra kairiojo vaiko dešinysis antrinis (arba atvirkščiai), atlikite pasukimą, kad perkeltumėte naują mazgą aukštyn ir sulygiuotumėte.
    • Jei naujojo mazgo dėdė yra juodas o naujas mazgas yra kairiojo vaiko kairysis vaikas (arba dešinysis dešinysis), atlikite sukimąsi ir perspalvinkite tėvą ir senelį, kad ištaisytumėte pažeidimą.

2. Pažeidimų taisymas po ištrynimo

Ištrynus medį gali reikėti taisyti, kad būtų atkurtos savybės:

  • Kai juodas mazgas pašalinamas arba raudonas mazgas pakeičiamas juodu, gali susidaryti dvigubai juoda situacija.

Ištrynimų taisymo atvejų analizė:

  • 1 atvejis: sesuo yra raudona
    • Perspalvinkite brolį ir seserį bei tėvą ir atlikite sukimąsi.
  • 2 atvejis: brolis ir sesuo yra juodaodžiai su juodaodžiais vaikais
    • Perdažykite brolį ir seserį į raudoną spalvą ir perkelkite problemą tėvui.
  • 3 atvejis: brolis ir sesuo yra juodaodis ir turi bent vieną raudoną vaiką
    • Pasukite ir perspalvinkite, kad išspręstumėte dvigubos juodos spalvos problemą.

Raudonai juodo medžio įgyvendinimas:

Čia pateikiamas išsamus raudonai juodo medžio įgyvendinimas, įskaitant įterpimo, paieškos ir pasukimo funkcijas:

ekspertų sistemos
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->teisė;  x->dešinė = y->kairė;  if (y->left != NIL) { y->left->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { šaknis = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->parent->right = y;  } y->kairė = x;  x->tėvas = y;  } // Naudingumo funkcija, skirta sukimui į dešinę atlikti void rightRotate(Node* x) { Node* y = x->left;  x->kairė = y->dešinė;  if (y->right != NIL) { y->right->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { šaknis = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->left = y;  } y->dešinė = x;  x->tėvas = y;  } // Funkcija, skirta pataisyti raudonos ir juodos spalvos medžio savybes po // įterpimo void fixInsert(Node* k) { while (k != šaknis && k->parent->color == 'RED') { if (k->parent == k->parent->parent->left) { Mazgas* u = k->parent->parent->dešinė; // dėdė if (u->spalva == 'RED') { k->parent->color = 'JUODA';  u->spalva = 'JUODA';  k->parent->parent->spalva = 'RED';  k = k->tėvas->tėvas;  } else { if (k == k->parent->right) { k = k->parent;  leftPasukti(k);  } k->parent->spalva = 'JUODA';  k->parent->parent->spalva = 'RED';  rightRotate(k->parent->parent);  } } else { Mazgas* u = k->parent->parent->left; // dėdė if (u->spalva == 'RED') { k->parent->color = 'BLACK';  u->spalva = 'JUODA';  k->parent->parent->spalva = 'RED';  k = k->tėvas->tėvas;  } else { if (k == k->parent->left) { k = k->parent;  dešinėnPasukti(k);  } k->parent->spalva = 'JUODA';  k->parent->parent->spalva = 'RED';  leftRotate(k->parent->parent);  } } } šaknis->spalva = 'JUODA';  } // Inorder traversal helper function void inorderHelper(Node* node) { if (mazgas != NIL) { inorderHelper(mazgas->left);  cout<< node->duomenis<< ' ';  inorderHelper(node->teisė);  } } // Paieškos pagalbinė funkcija Node* searchHelper(Node* node, int data) { if (mazgas == NIL || data == mazgas->duomenys) { return mazgas;  } if (duomenys< node->duomenys) { return searchHelper(mazgas->kairysis, duomenys);  } return searchHelper(mazgas->dešinė, duomenys);  } public: // Konstruktorius RedBlackTree() { NIL = new Node(0);  NIL->spalva = 'JUODA';  NIL->kairė = NIL->dešinė = NIL;  šaknis = NIL;  } // Įterpimo funkcija void insert(int data) { Mazgas* naujas_mazgas = naujas Mazgas(duomenys);  naujas_mazgas->kairė = NIL;  naujas_mazgas->dešinė = NIL;  Mazgas* pirminis = nullptr;  Mazgas* srovė = šaknis;  // BST įterpti while (current != NIL) { tėvas = srovė;  if (naujas_mazgas->duomenys< current->duomenys) { srovė = srovė->kairė;  } else { dabartinis = dabartinis->dešinė;  } } naujas_mazgas->parent = pirminis;  if (parent == nullptr) { root = naujas_mazgas;  } else if (naujas_mazgas->duomenys< parent->duomenys) { tėvas->kairė = naujas_mazgas;  } else { tėvas->dešinė = naujas_mazgas;  } if (naujas_mazgas->parent == nullptr) { naujas_mazgas->spalva = 'JUoda';  grąžinti;  } if (naujas_mazgas->parent->parent == nullptr) { return;  } fixInsert(naujas_mazgas);  } // Inorder traversal void inorder() { inorderHelper(root); } // Paieškos funkcija Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Elementų įterpimas 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; }>

Raudonai juodų medžių privalumai:

  • Subalansuotas: Raudonai juodi medžiai yra savaime balansuojantys, tai reiškia, kad jie automatiškai palaiko pusiausvyrą tarp kairiojo ir dešiniojo pomedžių aukščių. Tai užtikrina, kad paieškos, įterpimo ir ištrynimo operacijos užtrunka O (log n) laiko blogiausiu atveju.
  • Veiksminga paieška, įterpimas ir ištrynimas: Dėl subalansuotos struktūros „Red-Black Trees“ siūlo efektyvias operacijas. Blogiausiu atveju paieška, įterpimas ir ištrynimas užtrunka O (log n).
  • Paprasta įgyvendinti: Red-Black Tree savybių priežiūros taisyklės yra gana paprastos ir lengvai įgyvendinamos.
  • Plačiai naudojamas: Raudonai juodi medžiai yra populiarus pasirinkimas diegiant įvairias duomenų struktūras, tokias kaip žemėlapiai, rinkiniai ir prioritetinės eilės.

Raudonai juodų medžių trūkumai:

  • Sudėtingesnis nei kiti subalansuoti medžiai: Palyginti su paprastesniais subalansuotais medžiais, tokiais kaip AVL medžiai, raudonai juodi medžiai turi sudėtingesnes įterpimo ir ištrynimo taisykles.
  • Nuolatinės pridėtinės išlaidos: Raudonojo-juodojo medžio ypatybių palaikymas kiekvienai įterpimo ir ištrynimo operacijai prideda šiek tiek papildomų išlaidų.
  • Ne visais atvejais optimalus: Nors raudonai juodi medžiai yra veiksmingi daugeliui operacijų, jie gali būti ne geriausias pasirinkimas programoms, kuriose reikia dažnai įterpti ir ištrinti, nes nuolatinės papildomos išlaidos gali tapti reikšmingos.

Raudonai juodų medžių pritaikymas:

  • Žemėlapių ir rinkinių įgyvendinimas: Raudonai juodi medžiai dažnai naudojami žemėlapiams ir rinkiniams diegti, kur efektyvi paieška, įterpimas ir ištrynimas yra labai svarbūs.
  • Prioritetinės eilės: Raudonai juodi medžiai gali būti naudojami prioritetinėms eilėms įgyvendinti, kai elementai išdėstomi pagal jų prioritetą.
  • Failų sistemos: Raudonai juodi medžiai naudojami kai kuriose failų sistemose failų ir katalogų struktūroms valdyti.
  • Atmintyje esančios duomenų bazės: Raudonai juodi medžiai kartais naudojami atmintyje esančiose duomenų bazėse, siekiant efektyviai saugoti ir gauti duomenis.
  • Grafika ir žaidimų kūrimas: Raudonai juodi medžiai gali būti naudojami grafikoje ir žaidimuose plėtra tokioms užduotims kaip susidūrimo aptikimas ir kelio paieška.

Dažnai užduodami klausimai (DUK) apie raudoną-juodą medį:

1. Kas yra raudonai juodas medis?

Raudonai juodas medis yra savaime balansuojantis dvejetainis paieškos medis, kuris palaiko pusiausvyrą tarp kairiojo ir dešiniojo pomedžio aukščių. Tai užtikrina, kad paieškos, įterpimo ir ištrynimo operacijos užtrunka O (log n) laiko blogiausiu atveju. Raudonai juodi medžiai yra plačiai naudojami įvairiose programose, kur reikalingos veiksmingos duomenų struktūros.

2. Kaip raudonai juodas medis išlaiko pusiausvyrą?

Raudonai juodi medžiai išlaiko savo pusiausvyrą, vykdydami konkrečias mazgų spalvų (raudonos arba JUODOS) ir santykių tarp jų taisykles taisykles. Šios taisyklės užtikrina, kad medis išliktų subalansuotas ir kad aukščio skirtumas tarp kairiojo ir dešiniojo pomedžio būtų ne didesnis kaip 1.

3. Kokie yra raudonai juodo medžio naudojimo pranašumai?

  • Subalansuotas: Raudonai juodi medžiai yra savaime balansuojami, todėl užtikrina efektyvias paieškos, įterpimo ir ištrynimo operacijas.
  • Efektyvus: Jie siūlo O(log n) laiko sudėtingumą daugeliui operacijų.
  • Paprasta įgyvendinti: Red-Black Tree savybių priežiūros taisyklės yra gana paprastos.
  • Plačiai naudojamas: Jie yra populiarus pasirinkimas diegiant įvairias duomenų struktūras ir algoritmus.

4. Kokie yra raudonai juodo medžio naudojimo trūkumai?

  • Palyginti su paprastesniais subalansuotais medžiais, tokiais kaip AVL medžiai, raudonai juodi medžiai turi sudėtingesnes įterpimo ir ištrynimo taisykles.
  • Raudonojo-juodojo medžio ypatybių palaikymas kiekvienai įterpimo ir ištrynimo operacijai prideda šiek tiek papildomų išlaidų.
  • Programoms, kuriose dažnai įterpiami ir ištrinami, gali tikti kitos subalansuotos medžio struktūros.

5. Kokie dažniausiai naudojami raudonai juodi medžiai?

  • Žemėlapių ir rinkinių įgyvendinimas
  • Prioritetinės eilės
  • Failų sistemos
  • Atmintyje esančios duomenų bazės
  • Grafika ir žaidimų kūrimas (susidūrimų aptikimas, kelio paieška)
  • Raudonojo ir juodo medžio apibrėžimas ir reikšmė DSA
  • Savarankiškai balansuojantys dvejetainiai paieškos medžiai
  • Raudonas juodas medis prieš AVL medį
  • Kuo skiriasi „Heap“ ir „Red-Black Tree“?
  • Įterpimas į raudonai juodą medį
  • Ištrynimas raudonai juodame medyje
  • Raudonai juodi medžiai | Įterpimas iš viršaus į apačią