Drzewa czerwono-czarne: równowaga bez liczenia

Pięć niezmienionych wartości ograniczających wysokość

Drzewo czerwono-czarne jest drzewem binarnym poszukiwanym, w którym każdy node jest kolorowany w czerwony lub czarny, a ponadto są zachowywane cztery dodatkowe zasady — na topie normy drzewa poszukiwanego BST — na wszystkich czasach:

1. Każdy node jest czerwony lub czarny. 2. Wierzchołek korzeniowy jest czarny. 3. Każda liść (NIL / null) jest rozpatrywana jako czarny. 4. Nie istnieje czerwony node, który nie ma czarnych dzieci (dwa czerwone w rzędzie na dowolnym ścieżce). 5. Dla każdego nodego i jego wszystkich potomnych liści NIL, ścieżka przechodząca przez niego przeprowadza się przez taką samą liczbę czarnych nodeów — wysokość czarna nodego. Nie żadna z tych zasad nie odnosi się bezpośrednio do wysokości, co jest kluczem: zamiast śledzić i balansować na dokładnej liczbie wysokości (jako robią to drzewa AVL), drzewo czerwono-czarne obowiązuje lokalną koncepcję koloryzacji, która jest ekonomiczna do sprawdzenia i naprawienia po pojedynczej wstawce lub usunięciu, a ta koncepcja okazuje się implikować globalny ograniczenie wysokości.

1. Every node is red or black.
2. The root is black.
3. Every leaf (NIL / null) is considered black.
4. A red node never has a red child (no two reds in a row on any path).
5. Every path from a given node to any of its descendant NIL leaves
   passes through the same number of black nodes — the node's "black-height".

Dlaczego wysokość pozostaje O(log n)

Zasada 4 mówi, że nie można mieć dwóch węzłów czerwonych pod rząd, więc na dowolnym ścieżce od korzenia do liścia, co najwyżej co drugi węzeł jest czerwony. To oznacza, że cała długość tej ścieżki wynosi co najwyżej dwukrotnie jej black-height. Zasada 5 mówi, że każda ścieżka od korzenia do liścia ma tą samą black-height bh. Podstawa zasady zawiera przynajmniej 2^bh - 1 węzłów wewnętrznego (prosta indukcja: podwójenie black-height co najmniej podwójuje liczbę węzłów, ponieważ oba dziecięta węzła czarnego mają black-height bh−1 lub bh). W sumie:

n >= 2^bh - 1 (n = liczba węzłów wewnętrznych) => bh <= log2(n + 1) => wysokość <= 2 * bh <= 2 * log2(n + 1) Stąd wynika, że niezależnie od kolejności wprowadzania lub usuwania kluczy, najdłuższa możliwa ścieżka od korzenia do liścia nigdy nie jest dłuższa niż około dwukrotnie krótsza, a obie są O(log n). Wyszukiwanie, wstawianie i usuwanie przechodzą co najwyżej przez jedną ścieżkę od korzenia do liścia, więc wszystkie trzy operacje mają złożoność O(log n) w najgorszym przypadku — taki sam asymptotyczny obniżenie jak u idealnie równych drzew, ale za małą koszt rebalansowania.

n >= 2^bh - 1        (n = number of internal nodes)
=> bh <= log2(n + 1)
=> height <= 2 * bh <= 2 * log2(n + 1)

Rotacje i zmiana koloru podczas wstawiania

Nowo wstawiony węzeł zawsze jest najpierw kolorowany na czerwony (ta operacja nigdy nie narusza reguły wysokości czarnych, ponieważ nie dodaje żadnych czarnych węzłów do żadnej ścieżki) i potem procedura naprawcza przesuwa się w górę naprawiając każdą naruszenie czerwono-czerwone, które spowodował. Procedura naprawcza ma dwa bardzo różne zachowania w zależności od koloru strzelaka nowego węzła (brata rodzica nowego węzła):

strzelak jest CZERWONY: rodzic i strzelak są kolorowane na czarne, a dziadek na czerwony, a następnie kontynuowanie naprawy od dziadka (może spowodować cascade do korzenia) strzelak jest CZARNY (lub brakuje go): 1-2 rotacje drzewa (LL, LR, RL lub RR przypadki) plus zmiana koloru, która naprawia naruszenie lokalnie w O(1) rotacjach — dalsze cascade nie są potrzebne demo interaktywny · wstawianie kluczy i obserwacja rotacji, aby utrzymać drzewo zbalansowane● LIVE W przypadku zmiany koloru tylko, te naruszenia mogą przeważyć do korzenia, ale każda z rotacji kończy naprawę natychmiast, co jest powodem dla tego, że wstawianie kosztuje O(1) amortyzowanych rotacji, nawet jeśliłała łańcuch zmian koloru to O(log n) w najgorszym przypadku.

uncle is RED:
  recolour parent and uncle black, grandparent red,
  then continue fixing up from the grandparent (may cascade to the root)

uncle is BLACK (or missing):
  1-2 tree rotations (LL, LR, RL or RR case) plus a recolour,
  which fixes the violation locally in O(1) rotations — no further
  cascading is needed

Usunięcie to trudniejsza część

Usuwanie węzła okaże się być czarne może spowodować, że wysokość czarna jednego poddrzewa poniży się poniżej jego braci, tworząc deficyt "podwójnie czarnego", który musi zostać przesunięty w górę i rozwiązany poprzez dłuższy analizy przypadków niż wstawianie wymaga — klasyczne rozwiązanie ma cztery różne przypadki koloryzacji braci, każdy z własną rotacją i receptą zmieniania koloru. Jest to jedynym powodem, dla którego implementacje drzew czerwono-czarnej są znane za trudność w poprawnym zrozumieniu od podstaw, a dlatego większość kodu produkcyjnego korzysta z dobrze przetestowanej implementacji bibliotecznej zamiast pisania własnych z pamięci.

Gdzie rzeczywiście stosuje się drzewa czerwono-czarne

Drzewa czerwono-czarne są używane w standardowych bibliotekach standardowych C++'a, gdzie std::map i std::set implementowane są jako drzewa czerwono-czarne. Analogicznie TreeMap i TreeSet w Javie również wykorzystują drzewa czerwono-czarne. Linuxowy jądro używa drzewa czerwono-czarne do przechowywania procesów uruchomionych w completely fair schedulerze, posortowanych według wirtualnej czasu wykonania. Dzieje się tak, że wybor i ponowne wprowadzenie procesu po jego uruchomieniu są operacjami O(log n) na drzewie zachowującym równowagę pod wpływem nieprzewidzianego strumienia wysokofreqencji dodawania i usuwania — dokładnie to, dla czego są skierowane drzewa czerwono-czarne.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Red-Black Tree — Self-Balancing BST i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.