Notatki do wyk lad´

ow 10 i 11

28 kwiecie´

n, 5 maj 2011

Konstruowanie drzewa BST

z listy

– jako korze´

n drzewa we´

z pierwszy element listy

– wstaw kolejno ka˙zdy element listy jako nowy li´

s´

c

(procedura TREE-INSERT)

– dla nowego elementu miejsce na li´

s´

c w drzewie znajduje

sie

,

poprzez wielokrotne por´

ownanie go z we

,

z lami, do kt´

orych

dochodzimy poruszaja

,

c sie

,

w lewo lub w prawo zale˙znie od

wyniku por´

ownania

Przechodzenie drzewa metoda

,

inorder

INORDRE-TREE-WALK(x)

if x

̸=NIL

then INORDER-TREE-WALK(lef t[x])

wypisz key[x]
INORDRE-TREE-WALK(right[x])

Wywo lanie INORDER-TREE-WALK(root[T ]) powoduje
wypisanie wszystkich element´

ow drzewa wyszukiwa´

n binarnych

Typeset by

AMS-TEX

1

2

Wyszukiwanie

Wyszukujemy w drzewie BST we

,

z la, kt´

ory zawiera dany klucz.

Dane: wska´

znik do korzenia oraz klucz k

Wynik: wska´

znik do we

,

z la zawieraja

,

cego klucz k lub NIL, gdy taki

we

,

ze l nie istnieje.

Algorytm:

– rozpocznij wyszukiwanie w korzeniu i schod´

z po ´

scie˙zce

w d´

o l drzewa

– dla ka˙zdego we

,

z la x por´

ownaj klucz k z warto´

scia

,

key[x]

– je˙zeli warto´

sci sa

,

r´

owne, to wyszukiwanie zako´

nczy lo sie

,

sukcesem, je˙zeli x = NIL, to we

,

ze l o takim kluczu nie istnieje

– je˙zeli k < key[x], to przeszukuj lewe poddrzewo we

,

z la x,

je˙zeli 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(lef t[x], k)
else TREE-SEARCH(right[x], k)

ITERATIVE-TREE-SEARCH(x, k)

while x

̸=NIL and k ̸= key[x]

do if k < key[x]

then x

← left[x]

else x

← right[x]

return x

3

Minimum i maksimum

Procedura TREE-MINIMUM wyznacza wska´

znik do we

,

z la

o najmniejszym kluczu w poddrzewie o korzeniu w we

,

´

zle x

TREE-MINIMUM(x)

while lef t[x]

̸=NIL

do x

← left[x]

return x

Procedura TREE-MAXIMUM wyznacza wska´

znik do

maksymalnego elementu poddrzewa o korzeniu w we

,

´

zle x

TREE-MAXIMUM(x)

while right[x]

̸=NIL

do x

← right[x]

return x

Naste

,

pnik

– procedura TREE-SUCCESSOR wyznacza naste

,

pnika danego

we

,

z la w drzewie BST, tj. naste

,

pnego we

,

z la odwiedzanego

w czasie przechodzenia drzewa w porza

,

dku inorder

– je˙zeli wszystkie klucze sa

,

r´

o ˙zne, to naste

,

pnikiem we

,

z la x

jest we

,

ze l o najmniejszym kluczu wie

,

kszym ni˙z key[x]

– je˙zeli x ma najwie

,

kszy klucz w drzewie, to zostaje wyznaczona

warto´

s´

c NIL

4

Algorytm:

– je˙zeli prawe poddrzewo we

,

z la x jest niepuste, to naste

,

pnikiem

x jest najbardziej na lewo po lo˙zony we

,

ze l w prawym

poddrzewie (we

,

ze l o najmniejszym kluczu w tym poddrzewie);

zastosuj procedure

,

TREE-MINIMUM(right[x])

– je˙zeli we

,

ze l x nie ma prawego poddrzewa, to wykorzystujemy

naste

,

puja

,

ca

,

w lasno´

s´

c drzewa BST:

W lasno´

s´

c: Niech T be

,

dzie drzewem wyszukiwa´

n binarnych,

w kt´

orym wszystkie klucze sa

,

r´

o˙zne. Je˙zeli prawe poddrzewo

we

,

z la x z T jest puste i y jest jego naste

,

pnikiem, to y jest

najni˙zszym przodkiem x, kt´

orego lewy syn jest tak˙ze przodkiem

x

Zatem nale˙zy przej´

s´

c w g´

ore

,

drzewa a˙z do napotkania we

,

z la,

kt´

ory jest lewym synem swego ojca; ten ojciec jest naste

,

pnikiem

we

,

z la x

TREE-SUCCESSOR(x)

if right[x]

̸=NIL

then return TREE-MINIMUM(right[x])

y

← p[x]

while y

̸=NIL and x = right[y]

do x

← y

y

← p[y]

return y

5

Wstawianie

Nowa

,

warto´

s´

c v wstawiamy do drzewa T za pomoca

,

procedury

TREE-INSERT. Do procedury przekazujemy jako argument
we

,

ze l z, w kt´

orym key[z] = v, lef t[z] =NIL i right[z] =NIL

Algorytm:

– rozpocznij od korzenia przechodza

,

c po ´

scie˙zce w d´

o l drzewa;

wska´

znik x przebiega po ´

scie˙zce, a zmienna y zawiera wskazanie

na ojca x

– przesuwaj sie

,

w d´

o l a˙z x przyjmie warto´

s´

c NIL

– wstaw z do drzewa, przypisuja

,

c w la´

sciwe warto´

sci

odpowiednim wska´

znikom

TREE-INSERT(T, z)

y

← NIL

x

← root[T ]

while x

̸= NIL

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 lef t[y]

← z

else right[y]

← z

6

Usuwanie

Procedura TREE-DELETE usuwa zadany we

,

ze l z.

Argumentem procedury jest wska´

znik do z.

To, kt´

ory we

,

ze l zostanie faktycznie usunie

,

ty z BST zale˙zy od

tego ilu syn´

ow ma z.

Algorytm:

– je˙zeli z nie ma syn´

ow, to zasta

,

p wska´

znik do z w jego ojcu

p[z] warto´

scia

,

NIL

– je˙zeli z ma jednego syna, to ustal wska´

znik mie

,

dzy jego ojcem

a tym synem

– je˙zeli z ma dw´

och syn´

ow, to usu´

n naste

,

pnik y we

,

z la z i zasta

,

p

zawarto´

s´

c z zawarto´

scia

,

y

TREE-DELETE(T, z)

if lef t[z]=NIL or right[z]=NIL

then y

← z

else y

← TREE-SUCCESSOR(z)

if lef t[y]

̸=NIL

then x

← left[y]

else x

← right[y]

if x

̸= NIL

then p[x]

← p[y]

if p[y] =NIL

then root[T ]

← x

else if y = lef t[p[y]]

then lef t[p[y]]

← x

else right[p[y]]

← x

if y

̸= z

then key[z]

← key[y]

skopiuj zawarto´

s´

c pozosta lych p´

ol z y do z