plik


ÿþNotatki do wykladów 10 i 11 28 kwiecieD, 5 maj 2011 Konstruowanie drzewa BST z listy  jako korzeD drzewa wez pierwszy element listy  wstaw kolejno ka|dy element listy jako nowy li[ (procedura TREE-INSERT)  dla nowego elementu miejsce na li[ w drzewie znajduje sie poprzez wielokrotne porównanie go z wezlami, do których dochodzimy poruszaja c sie w lewo lub w prawo zale|nie od wyniku porównania Przechodzenie drzewa metoda inorder INORDRE-TREE-WALK(x) if x =NIL 8 then INORDER-TREE-WALK(left[x]) wypisz key[x] INORDRE-TREE-WALK(right[x]) Wywolanie INORDER-TREE-WALK(root[T ]) powoduje wypisanie wszystkich elementów drzewa wyszukiwaD binarnych Typeset by AMS-TEX 1 2 Wyszukiwanie Wyszukujemy w drzewie BST we zla, który zawiera dany klucz. Dane: wskaznik do korzenia oraz klucz k Wynik: wskaznik do wezla zawieraja cego klucz k lub NIL, gdy taki we zel nie istnieje. Algorytm:  rozpocznij wyszukiwanie w korzeniu i schodz po [cie|ce w dól drzewa  dla ka|dego wezla x porównaj klucz k z warto[cia key[x]  je|eli warto[ci sa równe, to wyszukiwanie zakoDczylo sie sukcesem, je|eli x = NIL, to wezel o takim kluczu nie istnieje  je|eli k < key[x], to przeszukuj lewe poddrzewo we zla x, je|eli natomiast k > key[x], to przeszukuj prawe poddrzewo TREE-SEARCH(x, k) if x =NIL or key[x] = k then return x if k < key[x] then TREE-SEARCH(left[x], k) else TREE-SEARCH(right[x], k) ITERATIVE-TREE-SEARCH(x, k) while x =NIL and k = key[x] 8 8 do if k < key[x] then x ! left[x] else x ! right[x] return x 3 Minimum i maksimum Procedura TREE-MINIMUM wyznacza wskaznik do wezla o najmniejszym kluczu w poddrzewie o korzeniu w wezle x TREE-MINIMUM(x) while left[x] =NIL 8 do x ! left[x] return x Procedura TREE-MAXIMUM wyznacza wskaznik do maksymalnego elementu poddrzewa o korzeniu w we zle x TREE-MAXIMUM(x) while right[x] =NIL 8 do x ! right[x] return x Nastepnik  procedura TREE-SUCCESSOR wyznacza nastepnika danego wezla w drzewie BST, tj. naste pnego we zla odwiedzanego w czasie przechodzenia drzewa w porza dku inorder  je|eli wszystkie klucze sa ró|ne, to nastepnikiem wezla x jest wezel o najmniejszym kluczu wie kszym ni| key[x]  je|eli x ma najwie kszy klucz w drzewie, to zostaje wyznaczona warto[ NIL 4 Algorytm:  je|eli prawe poddrzewo wezla x jest niepuste, to nastepnikiem x jest najbardziej na lewo polo|ony wezel w prawym poddrzewie (we zel o najmniejszym kluczu w tym poddrzewie); zastosuj procedure TREE-MINIMUM(right[x])  je|eli we zel x nie ma prawego poddrzewa, to wykorzystujemy nastepuja ca wlasno[ drzewa BST: Wlasno[: Niech T be dzie drzewem wyszukiwaD binarnych, w którym wszystkie klucze sa ró|ne. Je|eli prawe poddrzewo we zla x z T jest puste i y jest jego nastepnikiem, to y jest najni|szym przodkiem x, którego lewy syn jest tak|e przodkiem x Zatem nale|y przej[ w góre drzewa a| do napotkania wezla, który jest lewym synem swego ojca; ten ojciec jest naste pnikiem we zla x TREE-SUCCESSOR(x) if right[x] =NIL 8 then return TREE-MINIMUM(right[x]) y ! p[x] while y =NIL and x = right[y] 8 do x ! y y ! p[y] return y 5 Wstawianie Nowa warto[ v wstawiamy do drzewa T za pomoca procedury TREE-INSERT. Do procedury przekazujemy jako argument we zel z, w którym key[z] = v, left[z] =NIL i right[z] =NIL Algorytm:  rozpocznij od korzenia przechodza c po [cie|ce w dól drzewa; wskaznik x przebiega po [cie|ce, a zmienna y zawiera wskazanie na ojca x  przesuwaj sie w dól a| x przyjmie warto[ NIL  wstaw z do drzewa, przypisuja c wla[ciwe warto[ci odpowiednim wskaznikom TREE-INSERT(T, z) y ! NIL x ! root[T ] while x = NIL 8 do y ! x if key[z] < key[x] then x ! left[x] else x ! right[x] p[z] ! y if y = NIL then root[T ] ! z else if key[z] < key[y] then left[y] ! z else right[y] ! z 6 Usuwanie Procedura TREE-DELETE usuwa zadany wezel z. Argumentem procedury jest wskaznik do z. To, który wezel zostanie faktycznie usuniety z BST zale|y od tego ilu synów ma z. Algorytm:  je|eli z nie ma synów, to zasta p wskaznik do z w jego ojcu p[z] warto[cia NIL  je|eli z ma jednego syna, to ustal wskaznik miedzy jego ojcem a tym synem  je|eli z ma dwóch synów, to usuD nastepnik y wezla z i zasta p zawarto[ z zawarto[cia y TREE-DELETE(T, z) if left[z]=NIL or right[z]=NIL then y ! z else y ! TREE-SUCCESSOR(z) if left[y] =NIL 8 then x ! left[y] else x ! right[y] if x = NIL 8 then p[x] ! p[y] if p[y] =NIL then root[T ] ! x else if y = left[p[y]] then left[p[y]] ! x else right[p[y]] ! x if y = z 8 then key[z] ! key[y] skopiuj zawarto[ pozostalych pól z y do z

Wyszukiwarka

Podobne podstrony:
nw asd w10
nw asd w11
wprowadz w11
Metody numeryczne w11
w11 uwaga swiadomosc?z
w11 3
House M D [4x11] Frozen (XviD asd)
nw asd w3
w10 PSYCH
wprowadz w10 (2)
asd 2033s
Private Practice [1x09] In Which Dell Finds His Fight (XviD asd)
WNUM W11
asd
W10 AI
asd 1041tr

więcej podobnych podstron