Dlaczego std :: map jest implementowany jako czerwono-czarne drzewo?

194

Dlaczego jest std::mapimplementowany jako czerwono-czarne drzewo ?

Istnieje kilka zrównoważonych drzew binarnych (BST). Jakie były kompromisy w wyborze czerwono-czarnego drzewa?

c++ dictionary data-structures stl binary-search-tree Denis Gorodetskiy
źródło
26
Chociaż wszystkie implementacje, które widziałem, używają drzewa RB, zauważ, że nadal jest to zależne od implementacji.
Thomas
3
@Tomasz. Jest zależny od implementacji, więc dlaczego wszystkie implementacje używają drzew RB?
Denis Gorodetskiy
1
Naprawdę chciałbym wiedzieć, czy jakikolwiek implementator STL pomyślał o użyciu listy pomijania.
Matthieu M.
2
Mapa i zestaw C ++ są w rzeczywistości uporządkowaną mapą i uporządkowanym zestawem. Nie są implementowane za pomocą funkcji skrótu. Każde zapytanie zajmie O(logn)i nie O(1), ale wartości będą zawsze sortowane. Począwszy od C ++ 11 (myślę), istnieją unordered_mapi unordered_set, które są implementowane za pomocą funkcji skrótu i ​​chociaż nie są sortowane, większość zapytań i operacji jest możliwa O(1)(średnio)
SomethingSomething
@Thomas to prawda, ale nie taka interesująca w praktyce. Norma gwarantuje złożoność z uwzględnieniem konkretnego algorytmu lub zestawu algorytmów.
Justin Meiners,

Odpowiedzi:

126

Prawdopodobnie dwa najczęstsze algorytmy drzew samobalansujących to drzewa czerwono-czarne i drzewa AVL . Aby zrównoważyć drzewo po wstawieniu / aktualizacji, oba algorytmy używają pojęcia obrotu, w którym obracane są węzły drzewa w celu przeprowadzenia ponownego równoważenia.

Podczas gdy w obu algorytmach operacjami wstawiania / usuwania są O (log n), w przypadku czerwono-czarnego drzewa rotacja ponownego równoważenia jest operacją O (1) , podczas gdy w AVL jest to operacja O (log n) , co powoduje, że Czerwono-czarne drzewo bardziej wydajne w tym aspekcie etapu ponownego równoważenia i jeden z możliwych powodów, że jest częściej używany.

Drzewa czerwono-czarne są używane w większości bibliotek kolekcji, w tym w ofertach Java i Microsoft .NET Framework.

Chris Taylor
źródło
54
brzmi to tak, jakby czerwono-czarne drzewa mogły modyfikować drzewa w czasie O (1), co nie jest prawdą. modyfikacje drzew to O (log n) zarówno dla drzew czerwono-czarnych, jak i drzew AVL. sprawia to, że sporne jest, czy równoważącą częścią modyfikacji drzewa jest O (1) czy O (log n), ponieważ główna operacja to już O (log n). nawet po odrobinie dodatkowej pracy, jaką wykonują drzewa AVL, powstaje ściślej zbalansowane drzewo, które prowadzi do nieco szybszego wyszukiwania. jest to więc całkowicie poprawny kompromis i nie powoduje, że drzewa AVL są gorsze od drzew czerwono-czarnych.
nekromanta,
35
Trzeba spojrzeć poza złożoność do rzeczywistego środowiska wykonawczego, aby zobaczyć różnicę - drzewa AVL mają ogólnie niższy całkowity czas działania, gdy jest o wiele więcej wyszukiwań niż wstawień / usunięć. Drzewa RB mają niższy całkowity czas działania, gdy jest o wiele więcej wstawień / usunięć. Dokładna proporcja, w której następuje przerwa, zależy oczywiście od wielu szczegółów implementacji, sprzętu i dokładnego użycia, ale ponieważ autorzy bibliotek muszą obsługiwać szeroki zakres wzorców użytkowania, muszą zgadywać. AVL jest również nieco trudniejszy do wdrożenia, więc możesz chcieć skorzystać ze sprawdzonej korzyści.
Steve Jessop,
6
Drzewo RB nie jest „domyślną implementacją”. Każdy realizator wybiera implementację. O ile nam wiadomo, wszyscy wybrali drzewa RB, więc przypuszczalnie dotyczy to wydajności lub łatwości wdrożenia / konserwacji. Jak powiedziałem, punkt przerwania dla wydajności nie może sugerować, że uważają, że jest więcej wstawień / usunięć niż wyszukiwań, tylko że stosunek między nimi jest powyżej poziomu, w którym ich zdaniem RB prawdopodobnie przewyższa AVL.
Steve Jessop,
9
@Denis: niestety jedynym sposobem na uzyskanie liczb jest sporządzenie listy std::mapwdrożeń, wyśledzenie programistów i zapytanie ich, jakie kryteria zastosowali przy podejmowaniu decyzji, więc pozostaje to spekulacja.
Steve Jessop
4
Brakuje w tym wszystkim kosztu przypadającego na węzeł przechowywania informacji pomocniczych wymaganych do podjęcia decyzji dotyczących równowagi. Drzewa czerwono-czarne wymagają koloru 1-bitowego. Drzewa AVL wymagają co najmniej 2 bitów (reprezentujących -1, 0 lub 1).
SJHowe
47

To zależy od sposobu użytkowania. Drzewo AVL zwykle ma więcej rotacji ponownego równoważenia. Więc jeśli twoja aplikacja nie ma zbyt wielu operacji wstawiania i usuwania, ale ma duże znaczenie przy wyszukiwaniu, drzewo AVL prawdopodobnie jest dobrym wyborem.

std::map używa drzewa czerwono-czarnego, ponieważ uzyskuje rozsądny kompromis między szybkością wstawiania / usuwania węzłów a wyszukiwaniem.

webbertiger
źródło
1
Czy jesteś tego pewien??? Osobiście uważam, że czerwono-czarne drzewo jest złożone lub bardziej złożone, nigdy prostsze. Jedyne, co jest w drzewie Rd-Black, ponowne równoważenie występuje rzadziej niż AVL.
Eric Ouellet
1
@Eric Teoretycznie zarówno drzewo R / B, jak i drzewo AVL ma złożoność O (log n)) do wstawiania i usuwania. Ale jedną dużą częścią kosztów operacji jest rotacja, która jest różna dla tych dwóch drzew. Proszę odnieść się do dyskusji.fogcreek.com/joelonsoftware /... sprawdź węzły O (log n), aby zdecydować, gdzie konieczne są rotacje). ” Zredagowałem odpowiednio moje komentarze.
webbertiger
27

Drzewa AVL mają maksymalną wysokość 1,44 logn, a drzewa RB maksymalnie 2 logn. Wstawienie elementu do AVL może oznaczać ponowne zrównoważenie w jednym punkcie drzewa. Ponowne równoważenie kończy wstawianie. Po wstawieniu nowego liścia należy wykonać aktualizację przodków tego liścia aż do korzenia lub do punktu, w którym dwa poddrzewa mają jednakową głębokość. Prawdopodobieństwo aktualizacji k węzłów wynosi 1/3 ^ k. Ponowne równoważenie to O (1). Usunięcie elementu może oznaczać więcej niż jedno ponowne zrównoważenie (do połowy głębokości drzewa).

Drzewa RB są drzewami B rzędu 4 reprezentowanymi jako drzewa wyszukiwania binarnego. 4-węzeł w drzewie B daje dwa poziomy w równoważnym BST. W najgorszym przypadku wszystkie węzły drzewa to 2-węzły, z tylko jednym łańcuchem 3-węzłów aż do liścia. Ten liść będzie w odległości 2koli od korzenia.

Przechodząc od korzenia do punktu wstawiania, należy zmienić 4-węzły na 2-węzły, aby upewnić się, że żadne wstawienie nie nasyci liścia. Wracając od wstawienia, wszystkie te węzły muszą zostać przeanalizowane, aby upewnić się, że poprawnie reprezentują 4-węzły. Można to również zrobić, schodząc w dół drzewa. Globalny koszt będzie taki sam. Nie ma darmowego lunchu! Usuwanie elementu z drzewa odbywa się w tej samej kolejności.

Wszystkie te drzewa wymagają, aby węzły niosły informacje o wysokości, wadze, kolorze itp. Tylko drzewa Splay są wolne od takich dodatkowych informacji. Ale większość ludzi boi się drzew Splay, z powodu rozpadu ich struktury!

Wreszcie, drzewa mogą również przenosić informacje o wadze w węzłach, umożliwiając równoważenie wagi. Można zastosować różne schematy. Należy ponownie zrównoważyć, gdy poddrzewo zawiera ponad 3 razy więcej elementów niż inne poddrzewo. Ponowne równoważenie jest ponownie wykonywane przez pojedynczy lub podwójny obrót. To najgorszy przypadek 2.4. Można uciec z 2 razy zamiast 3, znacznie lepszym współczynnikiem, ale może to oznaczać pozostawienie nieco mniej niż 1% subtrees niezrównoważonych tu i tam. Zdradliwy!

Który rodzaj drzewa jest najlepszy? AVL na pewno. Są najprostsze do kodowania, a ich najgorsza wysokość jest najbliższa logn. Dla drzewa zawierającego 1000000 elementów AVL będzie mieć najwyżej wysokość 29, RB 40, a waga wyważona 36 lub 50 w zależności od stosunku.

Istnieje wiele innych zmiennych: losowość, współczynnik dodawania, usuwania, wyszukiwania itp.

użytkownik847376
źródło
2
Dobra odpowiedź. Ale jeśli AVL są najlepsze, to dlaczego standardowa biblioteka implementuje std :: map jako drzewo RB?
Denis Gorodetskiy
14
Nie zgadzam się, że drzewa AVL są bez wątpienia najlepsze. Chociaż mają niską wysokość, wymagają (ogółem) więcej pracy, aby wykonać ponowne równoważenie niż drzewa czerwone / czarne (praca ponownego równoważenia O (log n) w porównaniu z amortyzacją O (1) zamortyzowaną). Splay drzewa mogą być znacznie, znacznie lepsze, a twoje twierdzenie, że ludzie się ich boją, jest bezpodstawne. Nie ma jednego uniwersalnego „najlepszego” systemu równoważenia drzew.
templatetypedef
Prawie idealna odpowiedź. Dlaczego powiedziałeś, że AVL jest najlepszy. To po prostu źle i dlatego większość ogólnych implementacji używa drzewa czerwono-czarnego. Aby wybrać AVL, musisz mieć znacznie wyższy współczynnik odczytu nad manipulacją. Ponadto AVL ma trochę mniej pamięci niż RB.
Eric Ouellet
Zgadzam się, że AVL jest w większości przypadków lepszy, ponieważ zwykle drzewa są przeszukiwane częściej niż są wstawiane. Dlaczego drzewo RB jest tak powszechnie uważane za lepsze, gdy ma ono niewielką przewagę w przypadku zapisu głównie, a co ważniejsze, niewielką wadę w przypadku odczytu głównie? Czy naprawdę uważa się, że wstawisz więcej, niż znajdziesz?
doug65536,
25

Poprzednie odpowiedzi dotyczyły tylko alternatyw drzewa, a czerwony czarny prawdopodobnie pozostaje tylko z powodów historycznych.

Dlaczego nie tablica skrótów?

Typ wymaga tylko <operatora (porównania) do użycia jako klucza w drzewie. Jednak tabele skrótów wymagają, aby każdy typ klucza miał hashzdefiniowaną funkcję. Ograniczenie wymagań dotyczących typu do minimum jest bardzo ważne dla programowania ogólnego, dzięki czemu można go używać z szeroką gamą typów i algorytmów.

Projektowanie dobrej tabeli skrótów wymaga dogłębnej znajomości kontekstu, w którym będzie używana. Czy powinien używać otwartego adresowania, czy łączenia łańcuchowego? Jakie poziomy obciążenia powinien zaakceptować przed zmianą rozmiaru? Czy powinien używać drogiego skrótu, który pozwala uniknąć kolizji, czy takiego, który jest szorstki i szybki?

Ponieważ STL nie może przewidzieć, który jest najlepszy wybór dla Twojej aplikacji, domyślna musi być bardziej elastyczna. Drzewa „po prostu działają” i dobrze się skalują.

(C ++ 11 dodał tabele skrótów unordered_map. Z dokumentacji wynika, że wymaga to ustawienia zasad, aby skonfigurować wiele z tych opcji).

Co z innymi drzewami?

Drzewa Red Black oferują szybkie wyszukiwanie i same się równoważą, w przeciwieństwie do BST. Inny użytkownik zwrócił uwagę na jego zalety w stosunku do samowyważącego się drzewa AVL.

Alexander Stepanov (twórca STL) powiedział, że użyłby drzewa B * zamiast drzewa czerwono-czarnego, gdyby napisał std::mapponownie, ponieważ jest bardziej przyjazny dla nowoczesnych pamięci podręcznych.

Jedną z największych zmian od tego czasu był wzrost pamięci podręcznych. Błędy w pamięci podręcznej są bardzo kosztowne, więc lokalizacja odniesienia jest teraz o wiele ważniejsza. Struktury danych oparte na węzłach, które mają małą lokalizację odniesienia, mają znacznie mniej sensu. Gdybym dzisiaj projektował STL, miałbym inny zestaw pojemników. Na przykład drzewo B * w pamięci jest znacznie lepszym wyborem niż drzewo czerwono-czarne do implementacji kontenera asocjacyjnego. - Alexander Stepanov

Czy mapy powinny zawsze używać drzew?

Inną możliwą implementacją map byłby posortowany wektor (sortowanie wstawiane) i wyszukiwanie binarne. Działa to dobrze w przypadku kontenerów, które nie są często modyfikowane, ale są często pytane. Często robię to w C qsorti bsearchsą wbudowane.

Czy muszę nawet korzystać z mapy?

Rozważania cache oznacza, że rzadko ma sens użycie std::listlub std::dequenad std:vectornawet dla tych sytuacjach, uczono nas w szkole (takie jak usunięcie elementu ze środka listy). Stosując to samo rozumowanie, użycie pętli for do wyszukiwania liniowego listy jest często bardziej wydajne i czystsze niż budowanie mapy dla kilku wyszukiwań.

Oczywiście wybór czytelnego pojemnika jest zwykle ważniejszy niż wydajność.

Justin Meiners
źródło
3

Aktualizacja 2017-06-14: webbertiger edytuje swoją odpowiedź po tym, jak skomentowałem. Powinienem zauważyć, że jego odpowiedź jest teraz o wiele lepsza dla mnie. Ale zachowałem swoją odpowiedź jako dodatkową informację ...

Z uwagi na to, że uważam, że pierwsza odpowiedź jest zła (poprawka: już nie obie), a trzecia ma błędną afirmację. Czuję, że musiałem wyjaśnić ...

2 najbardziej popularne drzewa to AVL i Red Black (RB). Główna różnica polega na wykorzystaniu:

  • AVL: Lepiej, jeśli stosunek konsultacji (odczytu) jest większy niż manipulacja (modyfikacja). Stopa pamięci jest nieco mniejsza niż RB (ze względu na bit wymagany do kolorowania).
  • RB: Lepiej w ogólnych przypadkach, gdy istnieje równowaga między konsultacją (odczyt) a manipulacją (modyfikacją) lub większą modyfikacją w porównaniu do konsultacji. Nieco większy ślad pamięci dzięki przechowywaniu czerwono-czarnej flagi.

Główną różnicą jest kolorystyka. W drzewku RB masz mniej akcji ponownego równoważenia niż AVL, ponieważ kolorowanie pozwala czasami pomijać lub skracać akcje ponownego równoważenia, które mają względny koszt hi. Z powodu kolorowania drzewo RB ma również wyższy poziom węzłów, ponieważ może akceptować czerwone węzły między czarnymi (mając możliwości ~ 2x więcej poziomów), co sprawia, że ​​wyszukiwanie (odczyt) jest nieco mniej wydajne ... ale ponieważ jest to stała (2x), pozostaje w O (log n).

Jeśli weźmiesz pod uwagę wydajność w przypadku modyfikacji drzewa (istotna) w porównaniu do wydajności w wyniku konsultacji z drzewem (prawie nieistotna), naturalne jest, że w ogólnym przypadku wolisz RB niż AVL.

Eric Ouellet
źródło
2

To tylko wybór twojej implementacji - mogą być implementowane jako dowolne zrównoważone drzewo. Różne opcje są porównywalne z niewielkimi różnicami. Dlatego każdy jest tak dobry jak każdy.

nekromanta
źródło