Drzewce

03.10.2010 - Michał Karpiński
TrudnośćTrudnośćTrudność

Rotacje na drzewie binarnym

Ratocję w najprostszy sposób można opisać jako zamianę węzła $ x $ z jego ojcem $ y $ oraz przekierowaniu kilku wskaźników zgodnie z poniższym rysunkiem:

Gdybyśmy przeczytali od lewej do prawej etykiety wszystkich wierzchołków i ich poddrzew przedstawionych na rysunku przed i po wykonaniu rotacji, to powstałby następujący ciąg: $ \{A,x,B,y,C\} $. Prowadzi to do prostego i bardzo ważnego wniosku, że „rotacja zachowuje porządek inorder” i właśnie o to nam chodziło.

Uwaga: niezwykle ważne przy implementacji procedury $ rotate{-}left $ i $ rotate{-}right $ jest pamiętanie o wszystkich wskaźnikach, które są wykorzystywane przy rotacji. Nie tylko przekierowujemy synów $ x $-a i $ y $-a, lecz także pamiętamy o tym, że każdy węzeł ma pole $ parent $ i na to należy zwrócić szczególną uwagę. Nie zapomnijmy też, że podczas rotacji korzeń drzewa może ulec zmianie!

Wróćmy do przykładu z poprzedniej strony i zastosujmy rotacje do przywrócenia własności kopca po wstawieniu elementu do drzewa:

Po dojściu do korzenia kończymy algorytm wstawiania. Klucze zachowały porządek inorder i priorytety zachowały własność kopca. Warto zauważyć, że nie zawsze dochodzimy z nowym elementem aż do korzenia. Sprawdź ile rotacji należało by wykonać w naszym przykładzie, gdyby nowy węzeł miał inny priorytet, np. 0.60. A co jeśli wynosił by 0.10?

Gotowa procedura „Insert”

Poniżej zapisany jest algorytm wstawiania nowego elementu do drzewca w postaci pseudokodu:

Procedura $ INSERT{-}TREAP(k,p,T) $ wstawia nowy element o kluczu $ k $ i priorytecie $ p $ do drzewca $ T $.

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com