Różnica między czerwono-czarnymi drzewami a drzewami AVL

Czy ktoś mógłby wyjaśnić, jakie są główne różnice między tymi dwiema strukturami danych? Próbowałem znaleźć w Internecie źródło, które podkreśla różnice / podobieństwa, ale nie znalazłem nic zbyt pouczającego. W jakich przypadkach jeden byłby preferowany nad drugim? Jakie praktyczne sytuacje sprawiają, że jeden jest „lepszy” w użyciu niż drugi?

Drzewa AVL zachowują bardziej sztywną równowagę niż drzewa czerwono-czarne. Droga od korzenia do najgłębszego liścia w drzewie AVL wynosi co najwyżej ~ 1,44 lg (n + 2), podczas gdy w czerwono-czarnych drzewach to najwyżej ~ 2 lg (n + 1).

W rezultacie wyszukiwanie w drzewie AVL jest zwykle szybsze, ale odbywa się to kosztem wolniejszego wstawiania i usuwania z powodu większej liczby operacji obracania. Więc użyj drzewa AVL, jeśli spodziewasz się, że liczba wyszukiwań będzie dominować w liczbie aktualizacji drzewa.

W przypadku małych danych :

insert : drzewo RB i drzewo avl mają stałą liczbę maksymalnych obrotów, ale drzewo RB będzie szybsze, ponieważ średnio drzewo RB zużywa mniej obrotów.

lookup : drzewo AVL jest szybsze, ponieważ drzewo AVL ma mniejszą głębokość.

usuń : drzewo RB ma stałą liczbę maksymalnych obrotów, ale drzewo AVL może mieć O (log N) razy obrotu jako najgorsze. i średnio drzewo RB ma również mniejszą liczbę obrotów, więc drzewo RB jest szybsze.

dla dużych danych :

insert : drzewo AVL jest szybsze. ponieważ musisz wyszukać konkretny węzeł przed wstawieniem. gdy masz więcej danych, różnica czasu przy wyszukiwaniu konkretnego węzła rośnie proporcjonalnie do O (log N). ale drzewo AVL i drzewo RB nadal wymagają tylko stałej liczby obrotów w najgorszym przypadku. W ten sposób szyjka butelki stanie się czasem wyszukiwania tego konkretnego węzła.

lookup : drzewo AVL jest szybsze. (tak samo jak w przypadku małych danych)

usuń : drzewo AVL jest średnio szybsze, ale w najgorszym przypadku drzewo RB jest szybsze. ponieważ musisz również wyszukać bardzo głęboki węzeł, aby zamienić go przed usunięciem (podobnie jak przyczyna wstawienia). średnio oba drzewa mają stałą liczbę rotacji. ale drzewo RB ma stałą górną granicę obrotu.

Cytując z tego: Różnica między drzewami AVL i czerwono-czarnymi

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.

z definicji każdy AVL jest zatem podzbiorem czerwieni i czerni. Każde drzewo AVL powinno być w stanie pokolorować, bez restrukturyzacji lub rotacji, aby przekształcić je w czerwono-czarne drzewo.

Drzewa AVL są często porównywane z czerwono-czarnymi drzewami, ponieważ oba obsługują ten sam zestaw operacji, a O(log n)podstawowe operacje wymagają czasu. W przypadku aplikacji wymagających intensywnego wyszukiwania, drzewa AVL są szybsze niż drzewa czerwono-czarne, ponieważ są bardziej sztywno zrównoważone. Podobnie jak czerwono-czarne drzewa, drzewa AVL mają zrównoważoną wysokość. Oba nie są na ogół zrównoważone wagowo ani zrównoważone μ dla dowolnego μ ≤ ½; oznacza to, że węzły rodzeństwa mogą mieć bardzo różną liczbę potomków.

Z artykułu Wikipedii na temat drzew AVL

Maksymalna wysokość drzew jest najważniejsza dla zachowania równowagi. Prawie równa się 1.44 * log(n)AVL, ale w przypadku drzewa RB tak jest 2 * log(n). Możemy więc wyciągnąć wniosek, że lepiej jest używać AVL, gdy problemem jest zachęta do wyszukiwania. Liczy się kolejne pytanie dotyczące drzewa AVL i RB. Drzewo RB jest lepsze niż AVL w obliczu przypadkowego wstawienia przy niższym koszcie rotacji, ale AVL, które jest dobre do wstawiania rosnących lub malejących danych. Więc jeśli problemem jest zachęta do wstawiania, możemy użyć drzewa RB.

Aby dowiedzieć się, jak działa drzewo AVL, ta interaktywna wizualizacja pomaga.

AVL oraz RedBlack Trees są Strukturami Drzewa Drzewa o zrównoważonej wysokości. Są dość podobne, a prawdziwa różnica polega na liczbie operacji rotacji wykonywanych po każdej operacji dodawania / usuwania - wyższa w przypadku AVL, aby zachować ogólnie bardziej jednorodne wyważenie.

Obie implementacje są skalowane jako a O(lg N), gdzie N to liczba liści, ale w praktyce drzewo AVL jest szybsze w zadaniach wymagających intensywnego wyszukiwania: korzystając z lepszego równoważenia, przejścia drzewa są średnio krótsze. Z drugiej strony, jeśli chodzi o wstawianie i usuwanie, drzewo AVL jest wolniejsze: wymagana jest większa liczba obrotów, aby prawidłowo zrównoważyć strukturę danych po modyfikacji.

W przypadku implementacji ogólnego przeznaczenia (tj. A-priori nie jest jasne, czy wyszukiwania są przeważające w operacjach) preferowane są drzewa RedBlack: są one łatwiejsze do wdrożenia i szybsze w typowych przypadkach - wszędzie tam, gdzie struktura danych jest modyfikowana tak często, jak przeszukiwane . Przykładem, TreeMapa TreeSetw Javie wykorzystują podkładzie RedBlack drzewa.

Fakt, że drzewa RedBlack mają mniej rotacji, może jednak przyspieszyć ich wstawianie / usuwanie .... Ponieważ są one zwykle nieco głębsze, mogą być również wolniejsze przy wstawianiu i usuwaniu. Za każdym razem, gdy przechodzisz z jednego poziomu w drzewie do następnego, następuje duża zmiana polegająca na tym, że żądane informacje nie znajdują się w pamięci podręcznej i muszą zostać pobrane z pamięci RAM. W ten sposób czas uzyskany na mniejszej liczbie obrotów może już zostać stracony, ponieważ musi nawigować głębiej, a tym samym częściej aktualizować pamięć podręczną. Możliwość działania z pamięci podręcznej lub bez niej robi dużą różnicę. Jeśli odpowiednie informacje znajdują się w pamięci podręcznej, możesz wykonać wiele operacji rotacji w czasie potrzebnym do przejścia na kolejny poziom, a informacje o następnym poziomie nie znajdują się w pamięci podręcznej. Tak więc w przypadkach, gdy RedBlack jest teoretycznie szybszy, patrząc tylko na potrzebne operacje, w praktyce może być wolniejszy,

Z tego, co widziałem, wydaje się, że drzewa AVL wykonują tyle obrotów (czasami rekurencyjnie w górę drzewa), ile potrzeba, aby uzyskać żądaną wysokość drzewa AVL (log n). To sprawia, że ​​jest bardziej sztywno wyważony.

W przypadku czerwonych czarnych drzew istnieje 5 zestawów zasad, których należy przestrzegać podczas wstawiania i usuwania, które można znaleźć tutaj http://en.wikipedia.org/wiki/Red-black_tree .

Główną rzeczą, która może ci pomóc w przypadku czerwono-czarnych drzew, jest fakt, że w zależności od tych pięciu reguł możesz rekurencyjnie pokolorować drzewo aż do korzenia, jeśli wujek jest czerwony. Jeśli wujek jest czarny, będziesz musiał wykonać maksymalnie dwa obroty, aby naprawić wszelkie problemy, ale po tych jednym lub dwóch obrotach ZROBISZ. Spakuj to i powiedz dobranoc, bo to koniec manipulacji, którą musisz zrobić.

Zasada Big to numer 5 ... „Każda prosta ścieżka z danego węzła do dowolnego z jego liści potomnych zawiera taką samą liczbę czarnych węzłów”.

Spowoduje to większość obrotów, których będziesz potrzebować, aby drzewo działało, a to powoduje, że drzewo nie traci równowagi.

Podsumowując: AvlTrees są nieco lepiej zbalansowane niż RedBlackTrees. Oba drzewa zajmują łącznie O (log n) czasu dla wyszukiwań, wstawień i usuwania, ale dla wstawienia i usunięcia pierwsze wymaga O (log n) obrotów, podczas gdy drugie zajmuje tylko O ​​(1) obrotów.

Ponieważ rotacje oznaczają zapisywanie w pamięci, a zapisywanie w pamięci jest kosztowne, aktualizacja RedBlackTrees jest w praktyce szybsza niż AvlTrees