Przed zrozumieniem Drzewo czerwono-czarne i drzewo AVL różnic, powinniśmy wiedzieć osobno o drzewie czerwono-czarnym i drzewie AVL.
Co to jest czerwono-czarne drzewo?
Czerwono-czarne drzewo jest samozrównoważone drzewo wyszukiwania binarnego w którym każdy węzeł zawiera jeden dodatkowy bit informacji oznaczający kolor węzła. Kolor węzła może być czerwony lub czarny, w zależności od informacji bitowych przechowywanych przez węzeł.
Nieruchomości
Poniżej znajdują się właściwości powiązane z drzewem czerwono-czarnym:
- Węzeł główny drzewa powinien być czarny.
- Węzeł czerwony może mieć tylko czarne dzieci. Lub możemy powiedzieć, że dwa sąsiednie węzły nie mogą być w kolorze czerwonym.
- Jeśli węzeł nie ma lewego ani prawego dziecka, wówczas nazywa się go węzłem liścia. Zatem umieściliśmy lewe i prawe dziecko poniżej węzła liścia zwanego zero
Głębię czerni lub wysokość czerni węzła liścia można zdefiniować jako liczbę czerni, którą napotykamy, przechodząc od węzła liścia do węzła głównego. Jedną z kluczowych właściwości drzewa czerwono-czarnego jest to, że każdy węzeł liścia powinien mieć tę samą głębię czerni.
Rozumiemy tę właściwość na przykładzie.
W powyższym drzewie znajduje się pięć węzłów, z których jeden jest czerwony, a pozostałe cztery węzły są czarne. Na powyższym drzewie znajdują się trzy węzły liściowe. Teraz obliczamy głębokość czerni każdego węzła liścia. Jak możemy zaobserwować, głębokość czerni wszystkich trzech węzłów liściowych wynosi 2; dlatego jest to drzewo czerwono-czarne.
Jeżeli drzewo nie spełnia żadnej z powyższych trzech właściwości, to nie jest drzewem czerwono-czarnym.
Wysokość czerwono-czarnego drzewa
Rozważ h jako wysokość drzewa mającego n węzłów. Jaka byłaby najmniejsza wartość n?. Wartość n jest najmniejsza, gdy wszystkie węzły są czarne. Jeśli drzewo zawiera wszystkie czarne węzły, wówczas drzewo byłoby kompletnym drzewem binarnym. Jeśli wysokość całego drzewa binarnego wynosi h, to liczba węzłów w drzewie wynosi:
n = 2h -1
Jaka byłaby największa wartość n?
częściowo pochodny lateks
Wartość n jest największa, gdy każdy czarny węzeł ma dwoje czerwonych dzieci, ale czerwony węzeł nie może mieć czerwonych dzieci, więc będzie miał czarne dzieci. W ten sposób powstają naprzemienne warstwy czarnych i czerwonych dzieci. Zatem jeśli liczba czarnych warstw wynosi h, to liczba czerwonych warstw również wynosi h; dlatego całkowita wysokość drzewa wynosi 2h. Całkowita liczba węzłów wynosi:
n = 2*2h-1
Co to jest drzewo AVL?
Jakiś Drzewo AVL jest samobalansującym się drzewem poszukiwań binarnych, jeśli zaobserwujemy poniższy przypadek, który jest drzewem poszukiwań binarnych i drzewem zrównoważonym.
W powyższym drzewie najgorszym przypadkiem złożoności czasowej wyszukiwania elementu jest O(h), czyli wysokość drzewa. W powyższym przypadku liczba porównań w celu przeszukania 17 elementów wynosi 4, a wysokość drzewa również wynosi 4.
Jeśli weźmiemy pod uwagę skośne drzewo binarne, jak pokazano poniżej:
W powyższym prawym drzewie skośnym liczba porównań dokonanych w celu przeszukania 17 elementów wynosi 5, a liczba elementów obecnych w drzewie również wynosi 5. Zatem możemy powiedzieć, że jeśli drzewo jest skośnym drzewem binarnym, to złożoność czasowa byłoby O(n).
Teraz musimy zrównoważyć te skośne drzewa, aby miały złożoność czasową O(h). Istnieje termin tzw czynnik równowagi , który służy do samodzielnego równoważenia drzewa wyszukiwania binarnego. Współczynnik równowagi można obliczyć jako:
Współczynnik równowagi = wysokość lewego poddrzewa – wysokość prawego poddrzewaWartość współczynnika równowagi może wynosić 1, 0 lub -1. Jeśli każdy węzeł drzewa binarnego ma wartość 1, 0 lub -1, wówczas mówimy, że drzewo to jest zrównoważone drzewo binarne lub drzewo AVL.
Drzewo jest znane jako drzewo doskonale zrównoważone, jeśli współczynnik równowagi każdego węzła wynosi 0. Drzewo AVL jest drzewem prawie zrównoważonym, ponieważ każdy węzeł w drzewie ma wartość współczynnika równowagi 1, 0 lub -1.
Różnice między drzewem czerwono-czarnym a drzewem AVL.
Poniżej przedstawiono różnice między drzewem czerwono-czarnym a drzewem AVL:
Drzewo czerwono-czarne jest drzewem wyszukiwania binarnego, a drzewo AVL jest również drzewem wyszukiwania binarnego.
W czerwono-czarnym drzewie stosowane są następujące zasady:
- Węzeł w drzewie czerwono-czarnym ma kolor czerwony lub czarny.
- Kolor węzła głównego powinien być czarny.
- Sąsiednie węzły nie powinny być czerwone. Innymi słowy, możemy powiedzieć, że czerwony węzeł nie może mieć czerwonych dzieci, ale czarny węzeł może mieć czarne dzieci.
- Na każdej ścieżce powinna znajdować się taka sama liczba czarnych węzłów; wówczas tylko drzewo można uznać za drzewo czerwono-czarne.
- Węzły zewnętrzne to węzły zerowe, które zawsze mają kolor czarny.
Reguła drzewa AVL:
Każdy węzeł powinien mieć współczynnik równowagi wynoszący -1, 0 lub 1.
Na powyższym rysunku musimy sprawdzić, czy drzewo jest drzewem czerwono-czarnym, czy nie. Aby to sprawdzić, najpierw musimy sprawdzić, czy drzewo jest drzewem wyszukiwania binarnego, czy nie. Jak widać na powyższym rysunku spełnia on wszystkie własności drzewa poszukiwań binarnych; dlatego jest to drzewo wyszukiwania binarnego. Po drugie, musimy sprawdzić, czy spełnia powyższe zasady, czy nie. Powyższe drzewo spełnia wszystkie powyższe pięć zasad; dlatego stwierdza, że powyższe drzewo jest drzewem czerwono-czarnym.
Na powyższym rysunku musimy sprawdzić, czy drzewo jest drzewem AVL, czy nie. Ponieważ każdy węzeł ma wartość współczynnika równowagi wynoszącą -1, 0 lub 1, jest to drzewo AVL.
W przypadku drzewa czerwono-czarnego, jeśli wszystkie powyższe reguły są spełnione, pod warunkiem, że drzewo jest drzewem poszukiwań binarnych, to drzewo nazywa się drzewem czerwono-czarnym.
W przypadku drzewa AVL, jeśli współczynnik równowagi wynosi -1, 0 lub 1, wówczas mówi się, że powyższe drzewo jest drzewem AVL.
Jeśli drzewo nie jest zrównoważone, wówczas do równoważenia drzewa w drzewie czerwono-czarnym stosuje się dwa narzędzia:
Jeśli drzewo nie jest zbilansowane, wówczas do równoważenia drzewa w drzewie AVL używa się jednego narzędzia:
W przypadku drzewa czerwono-czarnego operacje wstawiania i usuwania są sprawne. Jeśli drzewo zostanie zrównoważone poprzez ponowne kolorowanie, wówczas operacje wstawiania i usuwania będą skuteczne w drzewie czerwono-czarnym.
W przypadku drzewa AVL przeszukiwanie jest efektywne, gdyż do zbilansowania drzewa potrzebne jest tylko jedno narzędzie.
W przypadku drzewa czerwono-czarnego złożoność czasowa wszystkich operacji, tj. wstawiania, usuwania i wyszukiwania, wynosi O(logn).
W przypadku drzewa AVL złożoność czasowa wszystkich operacji, tj. wstawiania, usuwania i wyszukiwania, wynosi O(logn).
alfabet i cyfry
Rozumiemy różnice w formie tabelarycznej.
| Parametr | Czerwone Czarne Drzewo | Drzewo AVL |
|---|---|---|
| Badawczy | Drzewo Czerwone Czarne nie zapewnia wydajnego wyszukiwania, ponieważ Drzewa Czerwone Czarne są w przybliżeniu zrównoważone. | Drzewa AVL zapewniają efektywne wyszukiwanie, ponieważ są drzewami ściśle zrównoważonymi. |
| Wstawianie i usuwanie | Wstawianie i usuwanie jest łatwiejsze w drzewie Red Black, ponieważ wymaga mniej obrotów, aby zrównoważyć drzewo. | Wstawianie i usuwanie są złożone w drzewie AVL, ponieważ wymagają wielu rotacji, aby zrównoważyć drzewo. |
| Kolor węzła | W drzewie czerwono-czarnym kolor węzła jest czerwony lub czarny. | W przypadku drzew AVL nie ma koloru węzła. |
| Współczynnik równowagi | Nie zawiera żadnego czynnika równoważącego. Przechowuje tylko jeden bit informacji, który oznacza czerwony lub czarny kolor węzła. | Każdy węzeł ma współczynnik równowagi w drzewie AVL, którego wartość może wynosić 1, 0 lub -1. Wymaga dodatkowej przestrzeni do przechowywania współczynnika równowagi na węzeł. |
| Ściśle zbalansowane | Drzewa czerwono-czarne nie są ściśle zrównoważone. | Drzewa AVL są ściśle zrównoważone, tj. Wysokość lewego poddrzewa i wysokość prawego poddrzewa różnią się co najwyżej o 1. |