Drzewce

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

Procedura "Split" i "Merge"

Omówiliśmy już najważniejsze algorytmy operowania na drzewcach. W zupełności wystarczy nam to do rozwiązywania prostych problemów, jednak czasami zachodzi potrzeba pójścia o jeden krok dalej. Załóżmy, że liczba drzewców, którymi będziemy operowali jest istotnie większa niż jeden. Oczywistym jest fakt, że potrzebujemy dodatkowych procedur, żeby w pełni móc zarządzać wszystkimi drzewcami.

Operacje, którymi będziemy zajmowali się w tym rozdziale to: rozdzielanie (split) drzewca na dwa osobne drzewce oraz scalanie (merge) dwóch różnych drzewców w jeden. Najpierw weźmiemy pod lupę prostszą z tych metod, czyli $ Split $.

Split

Zadanie brzmi następująco: dla danego drzewca $ T $ i wartości $ k $, podziel $ T $ na dwa drzewce $ T_1 $ i $ T_2 $, gdzie w $ T_1 $ znajdą się elementy drzewca $ T $, które są mniejsze od $ k $, a w $ T_2 $ takie, które są większe niż $ k $. Naszą metodę nazwiemy $ SPLIT{-}TREAP(k, T) $.

Procedura rozdzielania jest prosta, ponieważ stoi za nią prosty trik. Aby podzielić drzewiec na dwie części zgodnie z naszymi założeniami wystarczy wstawić do drzewca T element o kluczu k i maksymalnym priorytecie - większym niż wszystkie inne w drzewcu (element ten nazwijmy $ y $). Np. jeśli założyliśmy, że wartości priorytetów są z przedziału od 0 do 1, to dla $ y $ ustalmy priorytet 1.01 lub dowolnie większy.

Zobaczmy co się stanie: najpierw - według algorytmu wstawiania - $ y $ zostanie ustawiony w drzewcu zgodnie z porządkiem inorder i będzie liściem. W drugim kroku nastąpi naprawa własności kopca dla priorytetów. Skoro $ y $ ma największy priorytet, to po skończeniu serii rotacji $ y $ będzie korzeniem w drzewcu.

Przyjrzyjmy się teraz synom korzenia $ y $. Lewy syn jest korzeniem drzewca $ T_1 $, w którym wartości kluczy są mniejsze od $ k $, a prawy syn - korzeniem drzewca $ T_2 $, gdzie elementy są większe niż $ k $. Udało nam się podzielić drzewiec $ T $ zgodnie z założeniami.

Najlepsze w tej metodzie, to czas jego działania. Żeby podzielić drzewiec wystarczy wstawić do niego jeden element, czyli czas podziału jest równy czasowi jednokrotnego wykonania procedury $ INSERT{-}TREAP $.

Merge

Przy scalaniu dwóch drzewców nie zawsze możemy zastosować powyższy trik. W praktyce bardzo rzadko zdarza się taka sytuacja, bo aby scalić drzewce $ T_1 $ i $ T_2 $ w sposób prosty (jak przy podziale) warunkiem jest, aby wszystkie elementy w drzewcu $ T_1 $ były mniejsze od wszystkich elementów w $ T_2 $ (dzieje się tak np. zaraz po podzieleniu).

Można wtedy odwrócić proces podziału w następujący sposób: wiedząc, że największy element $ x $ w $ T_1 $ ma mniejszą wartość od najmniejszego elementu $ y $ w $ T_2 $, wybieramy wartość $ k $, która znajduje w przedziale $ \langle key[x],key[y] \rangle $ i nowemu elementowi $ z $ przypisujemy pola: $ key[z]=k $, $ left[z]=root[T_1] $, $ right[z]=root[T_2] $, $ priority[z]=1.01 $ (największy możliwy priorytet).

Teraz wystarczy usunąć z drzewca element $ z $ przy pomocy procedury $ DELETE{-}TREAP $. Były dwa drzewce, zrobił się jeden. Zobaczmy cały ten proces na przykładzie:

Czas wykonania powyższej metody jest równy czasowi jednokrotnego wywołania procedury $ DELETE{-}TREAP $.

Jak już wspomnieliśmy: nieczęsto zdarzają się tak sprzyjające warunki, jak w naszym przykładzie. Dla ogólnych przypadków trzeba się trochę bardziej namęczyć. Jednym ze sposobów połączenia drzewców $ T_1 $ i $ T_2 $ jest dodanie elementów z $ T_1 $ do $ T_2 $, jeden po drugim. W wyniku $ T_2 $ będzie scalonym drzewcem. Ta metoda sprawdza się dobrze, gdy liczba elementów $ n=|T_1| $ jest mała. Należy wtedy $ n $ razy wykonać procedurę $ INSERT{-}TREAP $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com