Dlaczego drzewa czerwono-czarne są tak popularne?

Wygląda na to, że gdziekolwiek spojrzę, struktury danych są wdrażane przy użyciu czerwono-czarnych drzew ( std::setw C ++, SortedDictionaryw C # itp.)

Właśnie omawiając (a, b), czerwono-czarne i drzewa AVL w mojej klasie algorytmów, oto co wyciągnąłem (również z pytania po profesorach, przeglądania kilku książek i przeglądania go trochę):

• Drzewa AVL mają mniejszą średnią głębokość niż drzewa czerwono-czarne, dlatego wyszukiwanie wartości w drzewie AVL jest konsekwentnie szybsze.
• Drzewa czerwono-czarne wprowadzają mniej zmian strukturalnych w celu zrównoważenia się niż drzewa AVL, co może potencjalnie przyspieszyć ich wstawianie / usuwanie. Mówię potencjalnie, ponieważ będzie to zależeć od kosztu zmiany strukturalnej drzewa, ponieważ będzie to w dużej mierze zależeć od środowiska wykonawczego i implementacji (może być zupełnie inaczej w funkcjonalnym języku, gdy drzewo jest niezmienne?)

Istnieje wiele testów porównawczych online, które porównują drzewa AVL i czerwono-czarne, ale uderzyło mnie to, że mój profesor w zasadzie powiedział, że zwykle zrobiłbyś jedną z dwóch rzeczy:

• Albo tak naprawdę nie zależy ci na wydajności, w takim przypadku różnica 10-20% AVL w porównaniu z czerwono-czarną w większości przypadków nie będzie miała żadnego znaczenia.
• Lub naprawdę zależy Ci na wydajności, w którym to przypadku porzucisz zarówno drzewa AVL, jak i czerwono-czarne, i wybierzesz drzewa B, które można dostosować, aby działały znacznie lepiej (lub (a, b) -tree, ja ” włożę wszystkie do jednego koszyka.)

Powodem tego jest to, że B-drzewo przechowuje dane bardziej zwięźle w pamięci (jeden węzeł zawiera wiele wartości), będzie znacznie mniej braków pamięci podręcznej. Możesz również dostosować implementację w zależności od przypadku użycia i uzależnić kolejność B-drzewa od wielkości pamięci podręcznej procesora itp.

Problem polega na tym, że nie mogę znaleźć prawie żadnego źródła, które analizowałoby rzeczywiste użycie różnych implementacji drzew wyszukiwania na prawdziwym nowoczesnym sprzęcie. Przejrzałem wiele książek na temat algorytmów i nie znalazłem niczego, co porównywałoby różne warianty drzew, oprócz pokazania, że ​​jedna ma mniejszą średnią głębokość niż druga (co tak naprawdę nie mówi zbyt wiele o zachowaniu drzewa w prawdziwych programach).

Biorąc to pod uwagę, czy jest jakiś szczególny powód, dla którego wszędzie stosuje się czerwono-czarne drzewa, gdy w oparciu o to, co powiedziano powyżej, B-drzewa powinny być lepsze od nich? (jako jedyny test, jaki mogłem znaleźć, pokazuje również http://lh3lh3.users.sourceforge.net/udb.shtml , ale może to być tylko kwestia konkretnej implementacji). A może powód, dla którego wszyscy używają czerwono-czarnych drzew, ponieważ są one dość łatwe do wdrożenia lub, innymi słowy, trudne do wdrożenia źle?

Jak to się zmieni, gdy przejdziemy do dziedziny języków funkcjonalnych? Wygląda na to, że zarówno Clojure, jak i Scala używają mapowanych tablic Hash , w których Clojure stosuje współczynnik rozgałęzienia wynoszący 32.

Cytując odpowiedź na pytanie „ Przemieszczanie z korzenia w drzewach AVL i czerwonych czarnych drzewach ”

W przypadku niektórych rodzajów drzew wyszukiwania binarnego, w tym drzew czerwono-czarnych, ale nie drzew AVL, „poprawki” do drzewa można dość łatwo przewidzieć po drodze w dół i wykonać podczas jednego przejścia z góry na dół, dzięki czemu drugie przejście nie jest konieczne. Takie algorytmy wstawiania są zazwyczaj realizowane za pomocą pętli zamiast rekurencji i często działają nieco szybciej w praktyce niż ich odpowiedniki dwuprzebiegowe.

Tak więc wstawkę drzewa RedBlack można wdrożyć bez rekurencji, w niektórych procesorach rekursja jest bardzo kosztowna, jeśli przekroczysz pamięć podręczną wywołań funkcji (np. SPARC z powodu użycia okna Rejestru )

(Widziałem oprogramowanie działające ponad 10 razy szybciej na Sparcu poprzez usunięcie jednego wywołania funkcji, co spowodowało, że często nazywana ścieżka kodu była zbyt głęboka dla okna rejestru. Ponieważ nie wiesz, jak głęboko okno rejestru będzie włączone system klienta i nie wiesz, jak daleko na stosie wywołań znajdujesz się na „ścieżce kodu”, nieużywanie rekurencji czyni bardziej przewidywalnym.)

Korzyścią jest również brak ryzyka wyczerpania stosu.

Ostatnio badam ten temat, więc oto moje ustalenia, ale pamiętaj, że nie jestem ekspertem w zakresie struktur danych!

W niektórych przypadkach nie można w ogóle użyć B-drzew.

Jednym z wybitnych przypadków jest std::mapC ++ STL. Standard wymaga, aby insertnie unieważniać istniejących iteratorów

Żadne iteratory lub odwołania nie są unieważniane.

http://en.cppreference.com/w/cpp/container/map/insert

Wyklucza to B-drzewo jako implementację, ponieważ wstawianie poruszałoby się wokół istniejących elementów.

Innym podobnym przypadkiem użycia są natrętne struktury danych. Oznacza to, że zamiast przechowywać dane w węźle drzewa, przechowujesz wskaźniki dla dzieci / rodziców w swojej strukturze:

// non intrusive
struct Node<T> {
    T value;
    Node<T> *left;
    Node<T> *right;
};
using WalrusList = Node<Walrus>;

// intrusive
struct Walrus {
    // Tree part
    Walrus *left;
    Walrus *right;

    // Object part
    int age;
    Food[4] stomach;
};

Po prostu nie można uczynić B-drzewa inwazyjnym, ponieważ nie jest to struktura danych zawierająca tylko wskaźnik.

Natrętne czerwono-czarne drzewa są używane na przykład w jemalloc do zarządzania wolnymi blokami pamięci. Jest to również popularna struktura danych w jądrze Linuksa.

Uważam również, że implementacja rekurencyjnego „pojedynczego przejścia ogona” nie jest przyczyną popularności czerwonego czarnego drzewa jako zmiennej struktury danych.

Po pierwsze, głębokość stosu jest tutaj nieistotna, ponieważ (biorąc pod uwagę wysokość) zabrakłoby pamięci głównej, zanim zabraknie miejsca na stosie. Jemalloc jest zadowolony z prealokacji najgorszej głębokości skrzynki na stosie.$\log{n}$

Istnieje wiele smaków implementacji czerwono-czarnego drzewa. Słynne są pozostawione pochylone czerwone czarne drzewa przez Roberta Sedgewicka ( UWAGA! Istnieją inne warianty, które są również nazywane „pochylonymi w lewo”, ale używają innego algorytmu). Ten wariant rzeczywiście pozwala wykonywać rotacje po drodze w dół drzewa, ale brakuje mu ważnej właściwości zamortyzowanej liczby poprawek , co powoduje, że jest on wolniejszy ( mierzony przez autora jemalloc ). Lub, jak to ujmuje opendatastrutures$O(1)$

Wariant czerwono-czarnych drzew Anderssona, wariant czerwono-czarnych drzew Sedgewick i drzewa AVL są łatwiejsze do wdrożenia niż zdefiniowana tutaj struktura RedBlackTree. Niestety żaden z nich nie może zagwarantować, że zamortyzowany czas ponownego równoważenia wynosi na aktualizację.$O(1)$

Wariant opisany w opendatastructures używa wskaźników nadrzędnych, rekurencyjnego przejścia w dół w celu wstawienia i iteracyjnego przejścia w górę w celu naprawy. Wywołania rekurencyjne znajdują się na końcowych pozycjach, a kompilatory optymalizują to do pętli (sprawdziłem to w Rust).

Oznacza to, że można uzyskać stałą implementację pętli pamięci modyfikowalnego drzewa wyszukiwania bez czerwono-czarnej magii, jeśli użyje się wskaźników nadrzędnych. Działa to również w przypadku B-drzew. Potrzebujesz magii do rekurencyjnego niezmiennego wariantu z pojedynczym przejściem na ogon, a i tak przerwie to naprawę .$O(1)$

Cóż, to nie jest wiarygodna odpowiedź, ale ilekroć muszę kodować zrównoważone drzewo wyszukiwania binarnego, jest to drzewo czerwono-czarne. Jest kilka powodów:

1) Średni koszt wstawiania jest stały dla drzew czerwono-czarnych (jeśli nie musisz szukać), podczas gdy jest logarytmiczny dla drzew AVL. Ponadto wiąże się z co najwyżej jedną skomplikowaną restrukturyzacją. W najgorszym przypadku wciąż jest to O (log N), ale to tylko proste przebarwienia.

2) Wymagają tylko 1 bit dodatkowych informacji na węzeł i często można znaleźć sposób na ich uzyskanie za darmo.

3) Nie muszę tego robić zbyt często, więc za każdym razem, gdy to robię, muszę wymyślić, jak to zrobić od nowa. Proste zasady i korespondencja z 2-4 drzewami sprawiają, że wydaje się to łatwe za każdym razem , nawet jeśli kod okazuje się skomplikowany za każdym razem . Nadal mam nadzieję, że któregoś dnia kod okaże się prosty.

4) Sposób, w jaki czerwono-czarne drzewo dzieli odpowiedni węzeł drzewa 2-4 i wstawia środkowy klucz do nadrzędnego węzła 2-4 tylko przez ponowne kolorowanie, jest bardzo elegancki. Po prostu uwielbiam to robić.

Drzewa czerwono-czarne lub AVL mają przewagę nad drzewkami B i tym podobne, gdy klucz jest długi lub z innego powodu przeniesienie klucza jest drogie.

Z std::setwielu powodów związanych z wydajnością stworzyłem własną alternatywę dla dużego projektu. Wybrałem AVL zamiast czerwono-czarnego ze względów wydajnościowych (ale to małe ulepszenie wydajności nie było uzasadnieniem dla mojego własnego zamiast std :: set). „Klucz” był skomplikowany i trudny do przeniesienia był znaczącym czynnikiem. Czy (a, b) drzewa nadal mają sens, jeśli potrzebujesz innego poziomu pośrednictwa przed kluczami? AVL i czerwono-czarne drzewa można zrestrukturyzować bez przenoszenia kluczy, więc mają tę zaletę, gdy klucze są kosztowne w przenoszeniu.