Drzewce

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

Procedura "Delete"

Usuwanie elementu z drzewca można podzielić na trzy kroki:

  • znajdź element o kluczu $ k $
  • jeśli taki element istnieje, to używając rotacji sprowadź go do dołu aż stanie się liściem. Rotacje wykonuj tak, aby nie zaburzyć własności kopca.
  • usuń element z drzewa

Przy usuwaniu elementów - podobnie jak przy wstawianiu - dużą rolę odgrywają rotacje. Jednak zamiast wykonywać rotację na elemencie $ x $, (co sprawiłoby, że $ x $ przeskoczyłby o jeden stopień w górę) rotację będziemy wykonywali na jednym z jego synów.

Problemu nie ma, jeśli dany wierzchołek ma tylko jednego syna. Wtedy w zależności czy jest to prawy czy lewy syn wykonujemy odpowiednio lewą albo prawą rotację.

Syna $ x $-a, na którym wykonamy rotację nie możemy wybrać losowo, gdy usuwany wierzchołek ma dwóch synów. Należy pamiętać, że po usunięciu elementu wciąż musi być zachowana własność kopca dla każdego węzła. Sprawdzamy priorytety lewego i prawego syna $ x $-a i porównujemy je ze sobą. Wybieramy tego syna, który ma wyższy priorytet i na nim uruchamiamy procedurę rotacji wyprowadzając go w górę.

Aby wszystko było jasne, prześledźmy prosty przykład:

Poniżej przedstawiona jest procedura $ DELETE{-}TREAP(k,T) $, która usuwa element o kluczu $ k $ z drzewca $ T $

Podana procedura usuwania może na pierwszy rzut oka wydawać się skomplikowana. Jest tak dlatego, że podczas wykonywania pętli $ while $ - w której przechodzimy z danym węzłem w dół przy pomocy rotacji - należy sprawdzić dużo przypadków.

Pierwsza linijka procedury $ DELETE{-}TREAP $ reprezentuje pierwszy krok usuwania podany na początku tego rozdziału i jest prosta do rozszyfrowania: najpierw szukamy czy element, który chcemy usunąć w ogóle znajduje się w drzewcu. Resztę algorytmu wykonujemy tylko, jeśli szukany element istnieje.

Drugi krok przeprowadzamy w pętli $ while $: dopóki dany wierzchołek ma jakiegoś syna, wykonujemy rotacje w sposób nie niszczący własności kopca na priorytetach.

Usunięcie elementu polega jedynie na przestawieniu jednego wskaźnika i następuje po wyjściu z pętli, czyli gdy dany wierzchołek stał się liściem. Tutaj też musimy rozpatrzeć kilka przypadków. W szczególności trzeba pamiętać, że usuwany węzeł może być korzeniem. Uwaga: przy implementacji procedury usuwania za pomocą niskopoziomowego języka (np. C) należy pamiętać o zwolnieniu pamięci, w której zapisany był $ x $.

Najważniejsze: nie należy się zniechęcać. Wystarczy kilka minut przestudiować dokładnie powyższy pseudokod i wszystko stanie się jasne. Zachęcam do przetestowania procedur wstawiania i usuwania na własnych przykładach.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com