logo

TechCodeview

Wprowadzenie do czerwono-czarnego drzewa

Drzewa wyszukiwania binarnego są podstawą struktura danych, ale ich wydajność może ucierpieć, jeśli drzewo stanie się niezrównoważone. Czerwone Czarne Drzewa są rodzajem zrównoważone drzewo wyszukiwania binarnego które wykorzystują zestaw reguł do utrzymania równowagi, zapewniając logarytmiczną złożoność czasową dla operacji takich jak wstawianie, usuwanie i wyszukiwanie niezależnie od początkowego kształtu drzewa. Czerwone Czarne Drzewa są samorównoważące, przy użyciu prostego schematu kodowania kolorami w celu dostosowania drzewa po każdej modyfikacji.

Czerwono-Czarne Drzewo



Spis treści

Co to jest czerwono-czarne drzewo?

A Czerwono-Czarne Drzewo jest samorównoważeniem drzewo wyszukiwania binarnego gdzie każdy węzeł ma dodatkowy atrybut: kolor, którym może być dowolny czerwony Lub czarny . Podstawowym celem tych drzew jest utrzymanie równowagi podczas wstawiania i usuwania danych, zapewniając efektywne pobieranie i manipulację danymi.

Właściwości drzew czerwono-czarnych

A Czerwono-Czarne Drzewo mają następujące właściwości:



  1. Kolor węzła : Każdy węzeł jest albo czerwony, albo czarny .
  2. Właściwość korzenia : Korzeń drzewa jest zawsze czarny .
  3. Czerwona Nieruchomość : Węzły czerwone nie mogą mieć czerwonych dzieci (nie ma dwóch kolejnych czerwonych węzłów na żadnej ścieżce).
  4. Czarna własność : Każda ścieżka od węzła do jego potomnych węzłów zerowych (liście) ma tę samą liczbę czarny węzły.
  5. Własność liścia : Wszystkie liście (węzły NIL) są czarny .

Te właściwości zapewniają, że najdłuższa droga od korzenia do dowolnego liścia nie jest dłuższa niż dwa razy dłuższa od najkrótszej ścieżki, zachowując równowagę drzewa i wydajną pracę.

Przykład czerwono-czarnego drzewa

ciąg znaków Java

The Prawidłowe czerwono-czarne drzewo na powyższym obrazku zapewnia, że ​​każda ścieżka od korzenia do węzła liścia ma tę samą liczbę czarnych węzłów. W tym przypadku jest jeden (z wyłączeniem węzła głównego).



The Nieprawidłowe czerwone czarne drzewo nie podąża za właściwościami czerwono-czarnymi jak dwa czerwone węzły sąsiadują ze sobą. Innym problemem jest to, że jedna ze ścieżek do węzła liścia nie ma żadnych czarnych węzłów, podczas gdy pozostałe dwie zawierają czarny węzeł.

przeciążanie metody

Dlaczego czerwono-czarne drzewa?

Większość operacji BST (np. wyszukiwanie, maks., min., wstawianie, usuwanie.. itp.) jest wykonywana Oh) czas, gdzie h jest wysokością BST . Koszt tych operacji może stać się NA) dla przekrzywionego Drzewo binarne. Jeśli upewnimy się, że wysokość drzewa pozostanie O(log n) po każdym dodaniu i usunięciu możemy zagwarantować górną granicę O(log n) za wszystkie te operacje. Wysokość czerwono-czarnego drzewa jest zawsze O(log n) gdzie n jest liczbą węzłów w drzewie.

Pan Nie.AlgorytmZłożoność czasu
1.SzukajO(log n)
2.WstawićO(log n)
3.UsuwaćO(log n)

Porównanie z Drzewo AVL :

Drzewa AVL są bardziej zrównoważone w porównaniu do drzew czerwono-czarnych, ale mogą powodować więcej rotacji podczas wstawiania i usuwania. Jeśli więc Twoja aplikacja wymaga częstego wstawiania i usuwania, preferowane powinny być drzewa czerwono-czarne. A jeśli wstawienia i usunięcia są rzadsze, a wyszukiwanie jest częstszą operacją, to wtedy Drzewo AVL powinno być preferowane zamiast czerwono-czarnego drzewa.

W jaki sposób czerwono-czarne drzewo zapewnia równowagę?

Prostym przykładem zrozumienia równoważenia jest to, że w drzewie czerwono-czarnym nie jest możliwy łańcuch 3 węzłów. Możemy wypróbować dowolną kombinację kolorów i sprawdzić, czy wszystkie naruszają właściwość drzewa czerwono-czarnego.

Właściwa struktura trójwęzłowego drzewa czerwono-czarnego

Interesujące punkty na temat czerwono-czarnego drzewa:

  • The czarny wysokość czerwono-czarnego drzewa to liczba czarnych węzłów na ścieżce od węzła głównego do węzła liścia. Węzły liści są również liczone jako czarny węzły. A więc czerwono-czarne drzewo wysokości H ma wysokość czerni>= h/2 .
  • Wysokość czerwono-czarnego drzewa z N węzły są h<= 2 log 2 (n + 1) .
  • Wszystkie liście (NIL) są czarny .
  • The czarny głębokość węzła definiuje się jako liczbę czarnych węzłów od korzenia do tego węzła, tj. liczbę czarnych przodków.

Podstawowe operacje na drzewie czerwono-czarnym:

Podstawowe operacje na drzewie czerwono-czarnym obejmują:

  1. Wprowadzenie
  2. Szukaj
  3. Usunięcie
  4. Obrót

1. Wprowadzenie

Wstawianie nowego węzła w czerwono-czarnym drzewie obejmuje proces dwuetapowy: wykonanie standardu wstawienie drzewa wyszukiwania binarnego (BST). , a następnie naprawienie wszelkich naruszeń właściwości czerwono-czarnych.

stany zjednoczone, ile miast

Kroki wstawiania

  1. Wkładka BST : Wstaw nowy węzeł jak w standardowym BST.
  2. Napraw naruszenia :
    • Jeśli rodzicem nowego węzła jest czarny , żadne właściwości nie są naruszane.
    • Jeśli rodzic jest czerwony , drzewo może naruszyć właściwość Red i wymagać poprawek.

Naprawianie naruszeń podczas wstawiania

Po wstawieniu nowego węzła jako a czerwony węzła, możemy spotkać się z kilkoma przypadkami, w zależności od kolorów rodzica i wujka węzła (rodzeństwa rodzica):

  • Przypadek 1: Wujek jest czerwony : Zmień kolor rodzica i wujka czarny , a dziadek czerwony . Następnie wejdź na drzewo, aby sprawdzić dalsze naruszenia.
  • Przypadek 2: Wujek jest czarny :
    • Podprzypadek 2.1: Węzeł jest właściwym dzieckiem : Wykonaj obrót w lewo na rodzicu.
    • Podprzypadek 2.2: Węzeł jest lewym dzieckiem : Wykonaj obrót w prawo na dziadku i odpowiednio zmień kolor.

2. Poszukiwanie

Wyszukiwanie węzła w drzewie czerwono-czarnym jest podobne do wyszukiwania w standardzie Drzewo wyszukiwania binarnego (BST) . Operacja wyszukiwania przebiega prostą ścieżką z pliku źródło do liść , porównując wartość docelową z wartością bieżącego węzła i odpowiednio przesuwając się w lewo lub w prawo.

Kroki wyszukiwania

  1. Zacznij od korzenia : Rozpocznij wyszukiwanie od węzła głównego.
  2. Przejdź przez drzewo :
    • Jeśli wartość docelowa jest równa wartości bieżącego węzła, węzeł zostanie znaleziony.
    • Jeśli wartość docelowa jest mniejsza niż wartość bieżącego węzła, przejdź do lewego elementu podrzędnego.
    • Jeśli wartość docelowa jest większa niż wartość bieżącego węzła, przejdź do prawego elementu podrzędnego.
  3. Powtarzać : Kontynuuj ten proces, aż zostanie znaleziona wartość docelowa lub osiągnięty zostanie węzeł NIL (wskazujący, że wartość nie jest obecna w drzewie).

3. Usunięcie

Usuwanie węzła z czerwono-czarnego drzewa również obejmuje dwuetapowy proces: usunięcie BST, a następnie naprawienie wszelkich powstałych naruszeń.

Kroki usuwania

  1. Usunięcie BST : Usuń węzeł, korzystając ze standardowych reguł BST.
  2. Napraw podwójną czerń :
    • Jeśli czarny węzeł zostanie usunięty, może wystąpić stan podwójnej czerni, który wymaga określonych poprawek.

Naprawianie naruszeń podczas usuwania

Po usunięciu czarnego węzła rozwiązujemy problem podwójnej czerni w oparciu o kolor rodzeństwa i kolory jego dzieci:

  • Przypadek 1: Rodzeństwo jest czerwone : Obróć rodzica i zmień kolor rodzeństwa i rodzica.
  • Przypadek 2: Rodzeństwo jest czarne :
    • Podprzypadek 2.1: Dzieci rodzeństwa są czarne : Zmień kolor rodzeństwa i propaguj podwójną czerń w górę.
    • Podprzypadek 2.2: Co najmniej jedno z dzieci rodzeństwa jest czerwone :
      • Jeśli dalekie dziecko rodzeństwa jest czerwone : Wykonaj obrót rodzica i rodzeństwa, a następnie odpowiednio zmień kolor.
      • Jeśli najbliższe dziecko rodzeństwa jest czerwone : Obróć rodzeństwo i jego dziecko, a następnie postępuj jak powyżej.

4. Obrót

Rotacje są podstawową operacją utrzymującą zrównoważoną strukturę czerwono-czarnego drzewa (RBT). Pomagają zachować właściwości drzewa, zapewniając, że najdłuższa droga od korzenia do dowolnego liścia nie jest dłuższa niż dwukrotność najkrótszej ścieżki. Rotacje występują w dwóch rodzajach: lewe obroty I prawe obroty.

1. Obrót w lewo

Obrót w lewo w węźle 𝑥 X porusza się 𝑥 X w dół w lewo i jego prawe dziecko 𝑦 I do wzięcia 𝑥 X miejsce.

Wizualizacja lewego obrotu 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Kroki obrotu w lewo:

  1. Ustawić I być właściwym dzieckiem X .
  2. Przenosić I lewe poddrzewo do X prawe poddrzewo.
  3. Zaktualizuj element nadrzędny X I I .
  4. Aktualizacja X rodzica, na którego można wskazać I zamiast X .
  5. Ustawić I pozostawione dziecku X .
  6. Aktualizacja X rodzic do I .

Pseudokod obrotu w lewo:

Obrót w lewo 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->Prawidłowy;  x->prawo = y->lewo;  if (y->lewy != NIL) { y->lewy->rodzic = x;  } y->nadrzędny = x->nadrzędny;  if (x->parent == nullptr) { root = y;  } else if (x == x->nadrzędny->lewy) { x->nadrzędny->lewy = y;  } else { x->rodzic->prawo = y;  } y->lewo = x;  x->rodzic = y; }>

2. Prawy obrót

Obrót w prawo w węźle 𝑥 X porusza się 𝑥 X w dół w prawo i jego lewe dziecko 𝑦 I do wzięcia 𝑥 X miejsce.

Wizualizacja prawego obrotu: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Kroki obrotu w prawo:

  1. Ustawić I być lewym dzieckiem X .
  2. Przenosić I prawe poddrzewo do X lewe poddrzewo.
  3. Zaktualizuj element nadrzędny X I I .
  4. Aktualizacja X rodzica, na którego można wskazać I zamiast X .
  5. Ustawić I właściwe dziecko X .
  6. Aktualizacja X rodzic do I .

Pseudokod obrotu w prawo:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->lewy;  x->lewo = y->prawo;  if (y->right != NIL) { y->right->parent = x;  } y->nadrzędny = x->nadrzędny;  if (x->parent == nullptr) { root = y;  } else if (x == x->nadrzędny->prawy) { x->nadrzędny->prawy = y;  } else { x->nadrzędny->lewy = y;  } y->prawo = x;  x->rodzic = y; }>

Kiedy wykonywać rotacje?

Obroty w drzewach czerwono-czarnych są zwykle wykonywane podczas wstawiania i usuwania, aby zachować właściwości drzewa. Poniżej znajdują się scenariusze rotacji:

lista połączona Java

1. Naprawianie naruszeń po wstawieniu

Kiedy wstawiany jest nowy węzeł, jest on zawsze wyświetlany w kolorze czerwonym. Może to spowodować naruszenie właściwości drzewa czerwono-czarnego, w szczególności:

  • Korzeń musi być czarny .
  • Czerwony węzły nie mogą mieć czerwony dzieci.

Analiza przypadku dotycząca mocowania wstawek:

  • Przypadek 1: Przebarwianie i rozmnażanie w górę
    • Jeśli rodzicem i wujkiem nowego węzła są oboje czerwony , pokoloruj rodzica i wujka na czarny , a dziadek czerwony . Następnie rekurencyjnie zastosuj poprawkę do elementu nadrzędnego.
  • Przypadek 2: Obrót i ponowne kolorowanie
    • Jeśli wujek nowego węzła jest czarny a nowy węzeł jest prawym dzieckiem lewego (lub odwrotnie), wykonaj obrót, aby przesunąć nowy węzeł w górę i wyrównać go.
    • Jeśli wujek nowego węzła jest czarny a nowy węzeł jest lewym dzieckiem lewego dziecka (lub prawym prawym), wykonaj obrót i zmień kolor elementu nadrzędnego i dziadka, aby naprawić naruszenie.

2. Naprawianie naruszeń po usunięciu

Po usunięciu drzewo może wymagać naprawy w celu przywrócenia właściwości:

  • Kiedy czarny węzeł zostanie usunięty lub czerwony węzeł zostanie zastąpiony czarnym węzłem, może wystąpić sytuacja podwójnej czerni.

Analiza przypadków dla naprawienia usunięć:

  • Przypadek 1: Rodzeństwo jest czerwone
    • Pokoloruj ponownie rodzeństwo i rodzica, a następnie wykonaj obrót.
  • Przypadek 2: Rodzeństwo jest czarne i ma czarne dzieci
    • Pokoloruj rodzeństwo na czerwono i przekaż problem rodzicowi.
  • Przypadek 3: Rodzeństwo jest czarne i ma co najmniej jedno czerwone dziecko
    • Obróć i pokoloruj ponownie, aby rozwiązać problem podwójnej czerni.

Implementacja drzewa czerwono-czarnego:

Oto szczegółowa implementacja drzewa czerwono-czarnego, w tym funkcje wstawiania, wyszukiwania i obracania:

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->Prawidłowy;  x->prawo = y->lewo;  if (y->lewy != NIL) { y->lewy->rodzic = x;  } y->nadrzędny = x->nadrzędny;  if (x->parent == nullptr) { root = y;  } else if (x == x->nadrzędny->lewy) { x->nadrzędny->lewy = y;  } else { x->rodzic->prawo = y;  } y->lewo = x;  x->rodzic = y;  } // Funkcja narzędziowa umożliwiająca wykonanie obrotu w prawo void RightRotate(Node* x) { Node* y = x->left;  x->lewo = y->prawo;  if (y->right != NIL) { y->right->parent = x;  } y->nadrzędny = x->nadrzędny;  if (x->parent == nullptr) { root = y;  } else if (x == x->nadrzędny->prawy) { x->nadrzędny->prawy = y;  } else { x->nadrzędny->lewy = y;  } y->prawo = x;  x->rodzic = y;  } // Funkcja naprawiająca właściwości czerwono-czarnego drzewa po // wstawieniu void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->parent == k->parent->parent->left) { Węzeł* u = k->parent->parent->right; // wujek if (u->color == 'RED') { k->parent->color = 'BLACK';  u->kolor = 'CZARNY';  k->nadrzędny->nadrzędny->kolor = 'CZERWONY';  k = k->rodzic->rodzic;  } else { if (k == k->nadrzędny->prawo) { k = k->nadrzędny;  w lewoObróć(k);  } k->rodzic->kolor = 'CZARNY';  k->nadrzędny->nadrzędny->kolor = 'CZERWONY';  rightRotate(k->nadrzędny->nadrzędny);  } } else { Węzeł* u = k->nadrzędny->nadrzędny->lewy; // wujek if (u->color == 'RED') { k->parent->color = 'BLACK';  u->kolor = 'CZARNY';  k->nadrzędny->nadrzędny->kolor = 'CZERWONY';  k = k->rodzic->rodzic;  } else { if (k == k->nadrzędny->lewy) { k = k->nadrzędny;  prawoObróć (k);  } k->rodzic->kolor = 'CZARNY';  k->nadrzędny->nadrzędny->kolor = 'CZERWONY';  leftRotate(k->nadrzędny->nadrzędny);  } } } root->kolor = 'CZARNY';  } // Funkcja pomocnicza przejścia w kolejności void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->left);  cout<< node->dane<< ' ';  inorderHelper(node->Prawidłowy);  } } // Funkcja pomocnicza wyszukiwania Węzeł* searchHelper(Węzeł* węzeł, int dane) { if (węzeł == NIL || dane == węzeł->dane) { return węzeł;  } jeśli (dane< node->dane) { return searchHelper(węzeł->lewo, dane);  } return searchHelper(węzeł->prawo, dane);  } public: // Konstruktor RedBlackTree() { NIL = nowy węzeł (0);  NIL->kolor = 'CZARNY';  NIL->lewy = NIL->prawy = NIL;  pierwiastek = NIL;  } // Wstaw funkcję void wstaw(int dane) { Węzeł* nowy_węzeł = nowy Węzeł(dane);  nowy_węzeł->lewy = NIL;  nowy_węzeł->prawy = NIL;  Węzeł* rodzic = nullptr;  Węzeł* bieżący = korzeń;  // BST wstaw póki (bieżący != NIL) { nadrzędny = bieżący;  if (nowy_węzeł->dane< current->dane) { bieżący = bieżący-> lewy;  } else { bieżący = bieżący->prawy;  } } nowy_węzeł->parent = rodzic;  if (parent == nullptr) { root = nowy_węzeł;  } else if (new_node->data< parent->dane) { nadrzędny->lewy = nowy_węzeł;  } else { nadrzędny->prawy = nowy_węzeł;  } if (nowy_węzeł->parent == nullptr) { nowy_węzeł->kolor = 'CZARNY';  powrót;  } if (nowy_węzeł->nadrzędny->nadrzędny == nullptr) { return;  } fixInsert(nowy_węzeł);  } // Przechodzenie przez Inorder void inorder() { inorderHelper(root); } // Funkcja wyszukiwania Węzeł* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Wstawianie elementów rbt.insert(10);  rbt.wstaw(20);  rbt.wstaw(30);  rbt.wstaw(15);  // Przejście wewnętrzne 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; }>

Zalety czerwono-czarnych drzew:

  • Zrównoważony: Drzewa czerwono-czarne są samorównoważące, co oznacza, że ​​automatycznie utrzymują równowagę pomiędzy wysokościami lewego i prawego poddrzewa. Dzięki temu w najgorszym przypadku operacje wyszukiwania, wstawiania i usuwania zajmą czas O(log n).
  • Efektywne wyszukiwanie, wstawianie i usuwanie: Dzięki zrównoważonej strukturze drzewa czerwono-czarne zapewniają wydajne działanie. Wyszukiwanie, wstawianie i usuwanie w najgorszym przypadku zajmuje czas O(log n).
  • Proste w wykonaniu: Zasady zachowania właściwości Drzewa Czerwono-Czarnego są stosunkowo proste i łatwe do wdrożenia.
  • Popularne: Drzewa czerwono-czarne są popularnym wyborem przy wdrażaniu różnych struktur danych, takich jak mapy, zestawy i kolejki priorytetowe.

Wady czerwono-czarnych drzew:

  • Bardziej złożone niż inne zrównoważone drzewa: W porównaniu do prostszych zrównoważonych drzew, takich jak drzewa AVL, drzewa czerwono-czarne mają bardziej złożone zasady wstawiania i usuwania.
  • Stałe obciążenie: Utrzymanie właściwości drzewa czerwono-czarnego powoduje niewielki narzut przy każdej operacji wstawiania i usuwania.
  • Nieoptymalne dla wszystkich przypadków użycia: Chociaż drzewa czerwono-czarne są wydajne w przypadku większości operacji, mogą nie być najlepszym wyborem w zastosowaniach, w których wymagane jest częste wstawianie i usuwanie, ponieważ stały narzut może stać się znaczny.

Zastosowania czerwono-czarnych drzew:

  • Implementacja map i zestawów: Drzewa czerwono-czarne są często używane do implementacji map i zbiorów, gdzie kluczowe znaczenie ma wydajne wyszukiwanie, wstawianie i usuwanie.
  • Kolejki priorytetowe: Drzewa czerwono-czarne można wykorzystać do implementacji kolejek priorytetowych, w których elementy są uporządkowane na podstawie ich priorytetu.
  • Systemy plików: Drzewa czerwono-czarne są używane w niektórych systemach plików do zarządzania strukturami plików i katalogów.
  • Bazy danych w pamięci: Drzewa czerwono-czarne są czasami używane w bazach danych w pamięci do wydajnego przechowywania i pobierania danych.
  • Tworzenie grafiki i gier: Drzewa czerwono-czarne można wykorzystać w grafice i grach rozwój do zadań takich jak wykrywanie kolizji i znajdowanie ścieżki.

Często zadawane pytania (FAQ) dotyczące drzewa czerwono-czarnego:

1. Co to jest czerwono-czarne drzewo?

Drzewo czerwono-czarne to samobalansujące drzewo poszukiwań binarnych, które utrzymuje równowagę pomiędzy wysokościami lewego i prawego poddrzewa. Dzięki temu w najgorszym przypadku operacje wyszukiwania, wstawiania i usuwania zajmą czas O(log n). Drzewa czerwono-czarne są szeroko stosowane w różnych zastosowaniach, w których wymagane są wydajne struktury danych.

2. W jaki sposób czerwono-czarne drzewo utrzymuje równowagę?

Czerwono-Czarne Drzewa utrzymują równowagę poprzez egzekwowanie określonych zasad dotyczących kolorów węzłów (CZERWONY lub CZARNY) i relacji między nimi. Reguły te zapewniają, że drzewo pozostaje zrównoważone i że różnica wysokości pomiędzy lewym i prawym poddrzewem wynosi co najwyżej 1.

3. Jakie są zalety korzystania z czerwono-czarnego drzewa?

  • Zrównoważony: Drzewa czerwono-czarne są samobalansujące, zapewniając wydajne operacje wyszukiwania, wstawiania i usuwania.
  • Wydajny: Oferują złożoność czasową O(log n) dla większości operacji.
  • Proste w wykonaniu: Zasady utrzymywania właściwości czerwono-czarnego drzewa są stosunkowo proste.
  • Popularne: Są popularnym wyborem przy wdrażaniu różnych struktur danych i algorytmów.

4. Jakie są wady korzystania z czerwono-czarnego drzewa?

  • W porównaniu do prostszych zrównoważonych drzew, takich jak drzewa AVL, drzewa czerwono-czarne mają bardziej złożone zasady wstawiania i usuwania.
  • Utrzymanie właściwości drzewa czerwono-czarnego powoduje niewielki narzut przy każdej operacji wstawiania i usuwania.
  • W przypadku zastosowań z częstym dodawaniem i usuwaniem bardziej odpowiednie mogą być inne zrównoważone struktury drzewiaste.

5. Jakie są typowe zastosowania czerwono-czarnych drzew?

  • Implementacja map i zestawów
  • Kolejki priorytetowe
  • Systemy plików
  • Bazy danych w pamięci
  • Tworzenie grafiki i gier (wykrywanie kolizji, znajdowanie ścieżki)
  • Definicja i znaczenie drzewa czerwono-czarnego w DSA
  • Samobalansujące się binarne drzewa wyszukiwania
  • Czerwone Czarne Drzewo kontra Drzewo AVL
  • Jaka jest różnica między stertą a czerwono-czarnym drzewem?
  • Wstawienie w czerwono-czarne drzewo
  • Usunięcie w drzewie czerwono-czarnym
  • Drzewa czerwono-czarne | Wstawianie z góry na dół