Czerwony czarny drzewo nad drzewem avl

109

AVL i czerwono-czarne drzewa równoważą się samoczynnie, z wyjątkiem czerwonego i czarnego koloru w węzłach. Jaki jest główny powód wyboru czerwono-czarnych drzew zamiast drzew AVL? Jakie są zastosowania czerwonych czarnych drzew?

algorithm data-structures red-black-tree jasne
źródło
2
możliwy duplikat Dlaczego std :: map jest zaimplementowany jako czerwono-czarne drzewo?
Lior Kogan
1
Nawiasem mówiąc, programiści Rusta zdecydowali się na użycie B-drzewa zamiast jednego z nich do standardowej uporządkowanej mapy.
Tom Anderson

Odpowiedzi:

124

Jaki jest główny powód wyboru czerwono-czarnych drzew zamiast drzew AVL?

Zarówno drzewa czerwono-czarne, jak i drzewa AVL są najczęściej używanymi zrównoważonymi drzewami wyszukiwania binarnego i obsługują wstawianie, usuwanie i wyszukiwanie w gwarantowanych O(logN) time. Istnieją jednak następujące punkty porównania między nimi:

  • Drzewa AVL są bardziej sztywno wyważone, dzięki czemu zapewniają szybsze wyszukiwania. Dlatego w przypadku zadań wymagających intensywnego wyszukiwania użyj drzewa AVL.
  • W przypadku zadań wymagających intensywnego wstawiania użyj czerwono-czarnego drzewa.
  • Drzewa AVL przechowują współczynnik równowagi w każdym węźle. Zajmuje to O(N)dodatkową przestrzeń. Jeśli jednak wiemy, że klucze, które zostaną wstawione do drzewa, będą zawsze większe od zera, możemy użyć bitu znaku kluczy do przechowywania informacji o kolorze czerwono-czarnego drzewa. Zatem w takich przypadkach czerwono-czarne drzewo nie zajmuje dodatkowej przestrzeni.

Jakie jest zastosowanie czerwonego czarnego drzewa?

Drzewa czerwono-czarne są bardziej ogólnego przeznaczenia. Działają stosunkowo dobrze przy dodawaniu, usuwaniu i wyszukiwaniu, ale drzewa AVL mają szybsze wyszukiwania kosztem wolniejszego dodawania / usuwania. Drzewko czerwono-czarne wykorzystywane jest w:

  • Java: java.util.TreeMap,java.util.TreeSet
  • C ++ STL (w większości implementacji): map, multimap, multiset
  • Jądro Linuksa: całkowicie uczciwy harmonogram, linux / rbtree.h
Nikunj Banka
źródło
43
In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.to nie jest prawda.
Jingguo Yao
9
Mówiąc pedantycznie, standard C ++ nie narzuca tego, std:: mapa przyjaciele używają żadnej określonej struktury. Pozostało to do implementacji, chociaż libstdc ++ i Dinkumware używają przynajmniej czerwono-czarnych drzew i wydaje się, że masz rację w praktyce.
mbozzi,
25
Współczynnik równowagi przechowywany w każdym węźle drzewa AVL wynosi dwa bity (-1 / 0 / +1). Czerwono-czarne drzewo przechowuje jeden bit informacji o kolorze w każdym węźle. Zatem w sumie oba drzewa wymagają pamięci O (N) dla dodatkowych informacji.
Seppo Enarvi
5
„W przypadku zadań wymagających intensywnych wstawek użyj drzewa czerwono-czarnego”. Czemu? Wstawienie drzewa AVL w najgorszym przypadku zajmuje tylko jeden obrót, podczas gdy drzewo Czerwono-Czarnego może zająć dwa.
Daniel
3
Powinno to zostać zaktualizowane zgodnie z analizą wydajności BST przeprowadzoną przez Bena Pfaffa z 2003 r. - drzewa AVL są bardziej ogólnego przeznaczenia i działają lepiej. Dokładne historyczne powody, dla których Java, C ++ i jądro Linuksa wybrały wolniejszą implementację, byłyby interesujące do wyśledzenia.
David McManamon
16

Spróbuj przeczytać ten artykuł

Zapewnia dobry wgląd w różnice, podobieństwa, wydajność itp.

Oto cytat z artykułu:

RB-Drzewa, podobnie jak drzewa AVL, równoważą się samoczynnie. Oba zapewniają wyszukiwanie O (log n) i wydajność wstawiania.

Różnica polega na tym, że RB-Drzewa gwarantują O (1) obrotów na operację wkładki. To właśnie kosztuje wydajność w rzeczywistych wdrożeniach.

Upraszczając, RB-Drzewa zyskują tę przewagę dzięki koncepcyjnemu byciu 2-3 drzewami bez przenoszenia narzutu dynamicznych struktur węzłów. Fizycznie RB-Drzewa są implementowane jako drzewa binarne, czerwone / czarne flagi symulują 2-3 zachowanie

O ile wiem, drzewa AVL i RB nie są zbyt odległe pod względem wydajności. Drzewo RB jest po prostu wariantem drzewa B, a równoważenie jest realizowane inaczej niż drzewo AVL.

Jordania
źródło
1
AFIAK, drzewo AVL ma również rotację O (1) na wstawienie. Dla drzewa RB i AVL - jedno wstawienie może mieć 1 lub 0 obrotów. Jeśli nastąpi rotacja, algorytmy zatrzymają się. Jeśli tak się nie stanie, zwykle algorytmy nadal sprawdzają / odświeżają węzły od dołu do korzenia drzewa. Dlatego czasami obrót O (1) może być lepszy, ponieważ eliminuje skanowanie pozostałych elementów O (log (n)). Ponieważ drzewo AVL średnio obraca się bardziej, drzewo AVL ma zwykle lepszą równowagę ~ 1,44 log (N) niż RB-drzewo 2 log (N).
Sergey Shandar
4

Nasze zrozumienie różnic w wydajności poprawiło się przez lata i teraz głównym powodem używania czerwono-czarnych drzew zamiast AVL byłby brak dostępu do dobrej implementacji AVL, ponieważ są one nieco mniej powszechne, być może, ponieważ nie są objęte CLRS.

Oba drzewa są obecnie uważane za formy drzew o zrównoważonej randze, ale czerwono-czarne drzewa są konsekwentnie wolniejsze o około 20% w rzeczywistych testach . Lub nawet o 30-40% wolniej po wstawieniu danych sekwencyjnych .

Dlatego ludzie, którzy badali czerwono-czarne drzewa, ale nie drzewa AVL, wybierają drzewa czerwono-czarne. Główne zastosowania czerwono-czarnych drzew są szczegółowo opisane we wpisie w Wikipedii .

David McManamon
źródło
1
Zabawny! w moim czytaniu artykuł o libavl zdaje się mówić, że AVL i RB są bezpośrednie i ogólnie żaden z nich nie jest wyraźnie lepszy od drugiego (który jest lepszy, zależy od obciążenia). Nigdzie nie widzę twierdzenia, że ​​AVL jest ogólnie szybszy o około 20%.
Stefan
3

Inne odpowiedzi tutaj dobrze podsumowują zalety i wady drzew RB i AVL, ale ta różnica była szczególnie interesująca:

Drzewa AVL nie obsługują stałego zamortyzowanego kosztu aktualizacji [ale drzewa czerwono-czarne tak]

Źródło: Mehlhorn & Sanders (2008) (sekcja 7.4)

Tak więc, podczas gdy zarówno RB i AVL drzew zagwarantować O (log (n)) czas najgorszym przypadku odnośników, wstawiania i usuwania, przywracając własność AVL / RB po włożeniu lub usunięcie węzła można zrobić w czasie O (1) zamortyzowany czas dla czerwono-czarne drzewa.

emanek
źródło
Uważam, że wstawienie drzewa AVL ma taki sam / podobny zamortyzowany koszt, ale daje lepiej zbilansowane drzewo (1,44 log (N) vs 2log (N)). Jednocześnie usunięcie w drzewie AVL może wymagać większej liczby obrotów. IMHO, to jest omówione w WAVL en.wikipedia.org/wiki/WAVL_tree
Sergey Shandar
1

Programiści na ogół nie lubią dynamicznie alokować pamięci. Problem z drzewem avl polega na tym, że dla "n" elementów potrzebujesz co najmniej log2 (log2 (n)) ... (height-> log2 (n)) bitów do przechowywania wysokości drzewa! Więc kiedy obsługujesz ogromne dane, nie możesz być pewien, ile bitów przeznaczyć na przechowywanie wysokości w każdym węźle.

Na przykład, jeśli używasz 4 bajtów int (32 bity) do przechowywania wysokości. Maksymalna wysokość może wynosić: 2 ^ 32, a więc maksymalna liczba elementów, które można przechowywać w drzewie to 2 ^ (2 ^ 32) - (wydaje się być bardzo duża, ale w obecnym wieku danych nic nie jest zbyt duże). Dlatego jeśli przekroczysz ten limit, musisz dynamicznie przydzielić więcej miejsca na przechowywanie wysokości.

To odpowiedź zasugerowana przez profesora z mojej uczelni, która wydała mi się rozsądna! Mam nadzieję, że mam sens.

Edycje: drzewa AVL są bardziej zrównoważone w porównaniu do czerwonych czarnych drzew, ale mogą powodować więcej obrotów podczas wstawiania i usuwania. Jeśli więc aplikacja wymaga wielu częstych wstawień i usunięcia, preferowane powinny być drzewa Red Black. A jeśli wstawienia i usunięcia są rzadsze, a wyszukiwanie jest częstszą operacją, to drzewo AVL powinno być preferowane przed drzewem Red Black. - Źródło GEEKSFORGEEKS.ORG

Prakhar Agrawal
źródło
1
Powiedziałbym, że jest to interesujące, ale niepraktyczne. Chociaż prawdą jest, że w najbardziej kompaktowym przypadku trudno byłoby wybrać najbardziej efektywną liczbę bitów do przydzielenia na wysokość, w praktyce każde pozostałe miejsce, które jest mniejsze niż jeden bajt, z pewnością będzie niewykorzystane, a wszystko, co zostanie, w przestrzeni 4 lub nawet 8 bajtów prawie na pewno pozostanie niewykorzystane. Pamięć nie jest przydzielana w sposób niewyrównany ze względu na wydajność, co znacznie przewyższa korzyści wynikające z odzyskania niewielkiej ilości miejsca. Wskaźniki do dzieci i wartość zajmują 24 bajty; 8 więcej prawdopodobnie nie będzie miało praktycznych kosztów.
Mumbleskates
4
you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] treeNie potrzebuję wysokości żadnego węzła w drzewie AVL, aby go zaimplementować. Potrzebujesz jednej dodatkowej informacji dla każdego węzła ( JESTEM NAJLEPSZY (rodzeństwo z najwyższym poddrzewem)); wygodniej i bardziej konwencjonalnie jest mieć dwa dodatkowe bity (dziecko jest wyższe dla lewego i prawego), jak przedstawiają AV i L.
siwobrody
4
2 ^ (2 ^ 32) pierwiastków to dużo ... tak jakbyś mógł przechowywać każdą pojedynczą cząsteczkę w całym wszechświecie i każdą możliwą parę tych cząsteczek i każdą możliwą potrójną, a mimo to nie zacząć nawet zbliżać się do mieszczą się w małym ułamku maleńkiego procentu pierwiastka sześciennego tej liczby podzielonego przez sto biliardów.
średnik
4
To jest bardzo mylące. Po pierwsze, nie musimy przechowywać wysokości w węźle drzewa AVL. Po drugie, nawet gdybyśmy to zrobili i nawet jeśli typowa ilość dostępnej pamięci podwaja się każdego roku, nadal mamy 4 miliardy lat, zanim wysokość naszych drzew przekroczy wielkość, którą można zapisać w 32 bitach.
Gassa
3
2 ^ (2 ^ 32) obiekty to absurdalnie, niesamowicie, absolutnie więcej niż jakikolwiek komputer, który możemy sobie wyobrazić, może pomieścić. Mamy około 2 ^ 40. Sprawdź ponownie, czy masz matematykę.
Stefan Reich
-1

Ponowne zbilansowanie drzewa AVL powinno spełniać poniższą właściwość. (Dokumentacja Wiki - Drzewo AVL )

W drzewie AVL wysokości dwóch poddrzew podrzędnych dowolnego węzła różnią się co najwyżej o jeden; jeśli w dowolnym momencie różnią się o więcej niż jeden, przeprowadzane jest równoważenie w celu przywrócenia tej właściwości.

Oznacza to, że całkowita wysokość drzewa AVL nie może zwariować, tj. Wyszukiwania będą lepsze z drzewami AVL. A ponieważ należy wykonać dodatkowe operacje (obroty), aby nie dopuścić do szaleństwa wysokości, operacje modyfikacji drzewa mogą być nieco kosztowne.

samshers
źródło
Wspomina się o wielu innych miejscach, ale powód, dla którego ta odpowiedź nie jest zbyt dobra, jest taki, że drzewa AVL i drzewa RB skutecznie zachowują bardzo podobne ograniczenia - drzewa RB nie będą więcej niż 2,0 razy większe niż wymagana wysokość, a dla drzew AVL współczynnik ten wynosi około 1,44. W rezultacie drzewa AVL obracają się nieco częściej, ale koszt jednej rotacji jest zasadniczo taki sam; to nie jest kosztowne.
Mumbleskates