Notatki do wyk ladu 12

12 maj 2011

Drzewa czerwono-czarne

Operacje rotacji

Rotacja jest operacja

,

lokalna

,

na drzewie wyszukiwa´

n binarnych,

zachowuja

,

ca

,

uporza

,

dkownie inorder kluczy w drzewie. Lewa

,

rotacje

,

na we

,

´

zle x wykonujemy tylko wtedy, gdy jego prawy syn y nie

jest r´

owny nil[T ]. W wyniku rotacji y staje sie

,

nowym korze-

niem poddrzewa, x zostaje jego lewym synem, a lewy syn we

,

z la

y zostaje prawym synem we

,

z la x. W procedurze LEFT-ROTATE

zak ladamy, ˙ze right[x]

̸= nil[T ] oraz ˙ze ojcem korzenia jest nil[T ].

LEFT-ROTATE (T, x)

y

← right[x]

right[x]

← left[y]

p[lef t[y]]

← x

p[y]

← p[x]

if p[x] = nil[T ]

then root[T ]

← y

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

then lef t[p[x]]

← y

else right[p[x]]

← y

lef t[y]

← x

p[x]

← y

Typeset by

AMS-TEX

1

2

Wstawianie

– wstawiamy we

,

ze l z do drzewa T stosuja

,

c modyfikacje

,

BST

– kolorujemy z na czerwono

– aby zachowa´

c w lasno´

sci czerwono-czarne wywo lujemy procedure

,

RB-INSERT-FIXUP, kt´

orej zadaniem jest przekolorowanie

we

,

z l´

ow i wykonanie rotacji.

RB-INSERT(T, z)

y

← nil[T ]

x

← root[T ]

while x

̸= nil[T ]

do y

← x

if key[z] < key[x]

then x

← left[x]

else x

← right[x]

p[z]

← y

if y = nil[T ]

then root[T ]

← z

else if key[z] < key[y]

then lef t[y]

← z

else right[y]

← z

lef t[z]

← nil[T ]

right[z]

← nil[T ]

color[z]

← RED

RB-INSERT-FIXUP (T, z)

3

Usuwanie

– usu´

n we

,

ze l z tak jak w BST

– je˙zeli usunie

,

ty we

,

ze l jest czarny to wywo laj procedure

,

RB-DELETE-FIXUP

RB-DELETE(T, z)

if lef t[z] = nil[T ] or right[z] = nil[T ]

then y

← z

else y

← TREE-SUCCESSOR(z)

if lef t[y]

̸= nil[T ]

then x

← left[y]

else x

← right[y]

p[x]

← p[y]

if p[y] = nil[T ]

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

if color[y] = BLACK

then RB-DELETE-FIXUP (T, x)

return y