Drzewo czerwono-czarne
Drzewo czerwono-czarne to struktura danych, będąca specyficznym rodzajem samoorganizującego się binarnego drzewa poszukiwań, które jest wykorzystywane w informatyce, szczególnie do implementacji tablic asocjacyjnych. Zostało wynalezione przez Rudolfa Bayera w 1972 roku, a jego współczesna nazwa oraz szczegółowe właściwości zostały opisane przez Leo J. Guibasa i Roberta Sedgewicka w 1978 roku.
Problemy tradycyjnych drzew binarnych
Podstawowe binarne drzewo poszukiwań umożliwia szybkie wyszukiwanie danych, jednak nie posiada mechanizmów równoważenia, co może prowadzić do nieefektywnej struktury z dużą głębokością. W efekcie czas operacji może być zbliżony do działania na zwykłej liście.
Właściwości drzewa czerwono-czarnego
Każdy węzeł w drzewie czerwono-czarnym ma przypisany kolor – czerwony lub czarny. Kluczowe właściwości to:
- Każdy węzeł jest czerwony lub czarny.
- Korzeń jest czarny.
- Każdy liść (w tym nil) jest czarny.
- Jeśli węzeł jest czerwony, jego dzieci muszą być czarne.
- Każda ścieżka z węzła do liścia ma jednakową liczbę czarnych węzłów.
Te zasady zapewniają, że głębokość drzewa wynosi co najwyżej 2 log(n + 1), co sprawia, że operacje takie jak wstawianie, wyszukiwanie i usuwanie mają złożoność O(log n).
Operacje na drzewie
Podstawowe operacje reorganizacji drzewa to rotacje w lewo i w prawo, które są wykonywane w czasie O(1).
Wstawianie elementów
Wstawianie nowego elementu obejmuje trzy kroki:
- Umieszczenie elementu w drzewie zgodnie z algorytmem dla drzew binarnych.
- Pokolorowanie nowego węzła na czerwono.
- Przywrócenie właściwości czerwono-czarnych.
W procesie przywracania rozpatruje się różne przypadki w zależności od koloru węzłów sąsiadujących.
Usuwanie elementów
Usuwanie węzła w drzewie czerwono-czarnym opiera się na standardowym algorytmie usuwania z drzew binarnych, z dodatkową procedurą przywracania właściwości czerwono-czarnych, jeśli usuwany węzeł jest czarny.
Podobne struktury danych
Alternatywą dla drzew czerwono-czarnych są drzewa AVL, które są prostsze w implementacji i zapewniają lepsze zrównoważenie, jednak operacje usuwania w drzewach AVL mogą być bardziej kosztowne, gdyż wymagają przejścia całej ścieżki od liścia do korzenia.
