Obrót binarnego drzewa wyszukiwania
W algorytmiczne The obrót poszukiwania binarnego drzewa umożliwia zmianę struktury binarne drzewo wyszukiwania lub ABR bez unieważniania kolejność elementów. Taki obrót polega w istocie na doprowadzeniu do wejścia w górę węzła drzewa i obaleniu kolejnego.
Operacja ta jest ogólnie szeroko stosowana w drzewach zrównoważonych, ponieważ umożliwia zmniejszenie wysokości drzewa poprzez obniżenie małych części drzew podrzędnych i podniesienie dużych, co umożliwia „zrównoważenie” drzew i przyspieszenie wielu. operacje na tych drzewach.
Rysunek
Operacja obracania w prawo, jak pokazano na powyższym obrazku, jest wykonywana przy użyciu Q jako podstawy. Jest to zatem prawy obrót na Q. Powoduje to obrót wału w kierunku zgodnym z ruchem wskazówek zegara. Operacja odwrotna to obrót w lewo, który powoduje ruch przeciwny do ruchu wskazówek zegara (obrót w lewo powyżej jest wykonywany na węźle P).
Zrozumienie rotacji wymaga zrozumienia jej ograniczeń. W szczególności kolejność liści drzewa (na przykład podczas czytania od lewej do prawej) nie może się zmienić (innymi słowy, podczas głębokiej podróży kolejność odwiedzania liści jest taka sama, jak przed operacją) . Drugim ograniczeniem jest główna właściwość drzewa wyszukiwania binarnego , to znaczy lewy syn jest mniejszy niż jego ojciec, a prawy syn jest wyższy niż jego ojciec.
Jak widać na schemacie, kolejność liści nie zmienia się. Operacja odwrotna również zachowuje porządek i jest drugim rodzajem rotacji.
Zakładając, że jest to drzewo wyszukiwania binarnego, pozycje należy interpretować jako zmienne, które można ze sobą porównać. Takimi zmiennymi są litery powyższego alfabetu.
Algorytm
Kiedy poddrzewo jest obracane, wysokość jednego z jego boków wzrasta, a drugiego maleje. To sprawia, że rotacje są przydatne do równoważenia drzewa.
Użyjemy terminologii Root dla węzła macierzystego poddrzewa, które podlega rotacji, Pivot dla węzła, który staje się nowym ojcem, Node → CR dla dziecka danego węzła po stronie obrotu i Node → CO dla syn po przeciwnej stronie. Rozróżniamy obrót w prawo i w lewo . W pierwszym CR oznacza prawe dziecko węzła, a CO lewe dziecko ; w drugim jest odwrotnie. Oś jest początkowym CO korzenia.
Na powyższym diagramie dla pierwiastka Q i obrotu w prawo CR to C, a CO to P. Pseudokod rotacji to:
Pivot = Racine→CO Racine→CO = Pivot→CR Pivot→CR = Racine Racine = PivotJest to praca ciągła.
Programista powinien upewnić się, że ojciec korzenia poddrzewa wskazuje na oś po obrocie (ostatnia linia w pseudokodzie powyżej).
Po odczytaniu tego pseudokodu rotacja wydaje się wyraźnie: czop wyznacza początkowe CO pierwiastka, a następnie zawiera początkową CR trzpienia, która następnie staje się początkowym pierwiastkiem, a ten ostatni ostatecznie staje się osią.
Przykłady
Drzewo
E / \ / \ / \ B F / \ / \ A D / Cmożna obrócić i przybrać następującą postać:
B / \ / \ / \ A E / \ D F / CJest to prawy obrót (korzenia E). Operacja odwrotna to obrót w lewo. Zauważ, że węzeł D, prawy syn B, zmienił ojca.
Możemy również otrzymać następującą alternatywną formę:
D / \ / \ B E / \ \ A C Fwykonując dwa kolejne obroty:
E E D / \ / \ / \ / \ / \ / \ / \ / \ / \ B F rotation gauche D F rotation droite B E / \ --------------> / --------------> / \ \ / \ de racine B / de racine E / \ \ A D B A C F / / \ C A CTutaj utworzyliśmy węzeł D, który „adoptował” jego ojca B (B adoptował C, lewego syna D), a następnie jego dziadka E (D nie miał prawego syna, w przeciwnym razie E adoptowałby).