Czerwone Czarne obroty drzewa i odwrócenia kolorów

Thamindu Dilshan Jayawickrama
Thamindu Dilshan Jayawickrama

śledź

lip 11, 2020 · 6 min przeczytaj

typowe drzewo wyszukiwania, takie jak binarne drzewo wyszukiwania (BST), może mieć wysokość O(N), co może spowodować najgorszą złożoność czasową O(N) dla podstawowe operacje, takie jak wyszukiwanie, wstawianie, usuwanie itp. To całkowicie zależy od kolejności elementów, które są wstawiane do BST. Ale są pewne sytuacje, w których nie mamy całego zestawu elementów, gdy zaczynamy konstruować drzewo. W tym miejscu pojawiają się zrównoważone drzewa poszukiwań. W zrównoważonym drzewie wyszukiwania, przy implementacji dynamicznego zestawu N pozycji Gwarantowana jest wysokość O(log N). Czerwono-czarne drzewa, drzewa AVL, 2-3 drzewa i B-drzewa to tylko niektóre przykłady zrównoważonych implementacji drzewa wyszukiwania. Ten artykuł dotyczy operacji modyfikacji drzew związanych z czerwono-czarnymi drzewami.

czerwono-czarne drzewo (RB-Tree) jest Samobalansującym się binarnym drzewem wyszukiwania, w którym każdy węzeł podąża za zestawem reguł. Każdy węzeł w drzewie RB ma jeden dodatkowy atrybut; kolor, który może być czerwony lub czarny. W typowej implementacji RB-Tree, będzie zestaw węzłów wartowniczych do oznaczania, że węzeł leaf został osiągnięty. Węzły te są określane jako NULLs (lub NILs) i uważane za węzły liści w tym artykule. Poniżej znajduje się zbiór reguł lub właściwości, których powinien przestrzegać każdy węzeł.

  1. każdy węzeł jest czerwony lub czarny.

2. Korzeń i liście są czarne.

3. Jeśli węzeł jest czerwony, to jego rodzic jest czarny.

4. Wszystkie proste ścieżki od dowolnego węzła do liścia potomnego mają taką samą liczbę czarnych węzłów (black-height).

wysokość drzewa RB pozostaje na o(log n) po każdej operacji modyfikacji drzewa, która skutkowała gwarantowaną górną granicą o(log n) dla tych operacji. Operacje Insert i Delete powodują modyfikacje drzewa RB. Po każdej operacji modyfikacji drzewa, drzewo będzie samo-zrównoważone poprzez zmiany kolorów i rotacje. Zanim przejdziemy do tych operacji, powinniśmy zapoznać się z następującą notacją.

rotacja jest specjalną operacją przeznaczoną do samobalansowania binarnych drzew wyszukiwania, które można wykonać w czasie o(1). Ciekawą właściwością na obrotach jest to, że zachowuje kolejność przejazdu kluczy (kolejność kluczy).

decyzja o wykonaniu rotacji lub zmianie koloru zależy od ciotki danego węzła (aktualnego węzła). Jeśli węzeł ma czarną ciotkę, robimy rotację. Jeśli węzeł ma czerwoną ciotkę, robimy odwrócenie koloru. Po wykonaniu rotacji, powinniśmy kolor naprawić drzewo. Po wykonaniu tych operacji drzewo powinno zostać zakończone jak poniżej.

Jeśli bieżący węzeł jest lewym potomkiem lewego potomka dziadka, to w prawo obracamy dziadka wokół rodzica. Jeśli bieżący węzeł jest Prawym potomkiem prawego potomka dziadka, po lewej stronie obracamy dziadka wokół rodzica. Jeśli obecny węzeł jest Prawym dzieckiem lewego dziecka dziadka, wykonujemy obrót w lewo-prawo, gdzie obracamy dziadka i dziecko wokół rodzica. Jeśli obecny węzeł jest lewym dzieckiem prawego dziecka dziadka, wykonujemy obrót w prawo-lewo, gdzie obracamy dziadka i dziecko wokół rodzica. Wszystkie obroty można podsumować zgodnie z poniższym diagramem.

jednym z ważnych faktów do zapamiętania jest to, że po wykonaniu jakiejkolwiek operacji modyfikacji drzewa, powinieneś zweryfikować drzewo zgodnie z zestawem reguł, aby dowiedzieć się, czy istnieją jakiekolwiek naruszenia. Jeśli istnieje naruszenie (np. root jest czerwony), powinieneś to poprawić. Teraz zbudujmy proste drzewo RB wstawiając poniżej Zestaw Kluczy. Zauważ, że dla uproszczenia, węzły liści (NULL) są ignorowane na poniższych diagramach.

5, 8, 1, 10, 9, 15, 20

każdy klucz powinniśmy wstawić jako czerwony węzeł. Dlatego wstawiamy 5 jako czerwony węzeł i natychmiast barwimy go z powrotem na czarny, ponieważ jest to węzeł główny. Następnie wstawiamy 8 jako prawe dziecko węzła 5. podczas wstawiania kluczy postępujemy zgodnie z podstawową właściwością BST. Wstawienie 1 jest takie samo jak wstawienie 8.

następnie powinniśmy wstawić 10 jako właściwe dziecko 8. Wstawiamy go jako czerwony węzeł i sprawdzamy naruszenia. Zarówno 8, jak i 10 są czerwonymi węzłami i naruszają trzecią własność. Powinniśmy sprawdzić ciotkę i jest czerwona. Więc wykonujemy odwrócenie koloru. Po odwróceniu koloru widzimy, że węzeł główny jest czerwony i narusza właściwość 2. Naprawiamy to zmieniając kolor węzła głównego.

następnie powinniśmy wstawić klucz 9. Po wstawieniu widzimy, że zarówno 9, jak i 10 węzłów są czerwone i narusza to właściwość 2. Sprawdzamy czy ciotka jest czarna (NULL są czarne), wykonujemy obrót w prawo-lewo (naruszenie jest w lewym podkładzie prawego dziecka). Po rotacji powinniśmy zrobić korektę koloru.

teraz wstawmy klucz 15. Po wstawieniu widzimy, że są tam dwa kolejne czerwone węzły, a ciotka 15 jest czerwonym węzłem. Powinniśmy zmienić kolor. Następnie sprawdzamy wszelkie naruszenia i możemy dowiedzieć się, że nie ma żadnych naruszeń.

teraz wstawmy klucz 20 do drzewa. Po wstawieniu widzimy, że ciotka jest czarna i dlatego powinniśmy wykonać obrót w lewo (naruszenie jest w prawym podkładzie dziecka). Po rotacji powinniśmy zrobić korektę koloru.

w tym artykule przyjrzeliśmy się konkretnemu samobalansującemu binarnemu drzewu wyszukiwania; czerwono-czarnemu drzewu. Są one gwarantowane, że mają wysokość O (log N), dlatego mają najgorszą złożoność czasową O (log N) dla podstawowych operacji na drzewie. Czerwono-czarne drzewa są szczególnie przydatne w wielu zastosowaniach informatycznych. C++ Standard Template Library (STL) ma set, multiset, map i multimap oparte na drzewach RB. Ponadto mapa drzewa w języku Java jest implementacją NavigableMap opartą na drzewie RB.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.