Notatki do wykladu 12
12 maj 2011
Drzewa czerwono-czarne
Operacje rotacji
Rotacja jest operacja lokalna na drzewie wyszukiwań binarnych,
zachowuja ca uporza dkownie inorder kluczy w drzewie. Lewa rotacje
na we z
le x wykonujemy tylko wtedy, gdy jego prawy syn y nie
jest równy nil[T ]. W wyniku rotacji y staje sie nowym korze-
niem poddrzewa, x zostaje jego lewym synem, a lewy syn we zla
y zostaje prawym synem we zla x. W procedurze LEFT-ROTATE
zakladamy, że right[x] = nil[T ] oraz że ojcem korzenia jest nil[T ].
8
LEFT-ROTATE (T, x)
y �! right[x]
right[x] �! left[y]
p[left[y]] �! x
p[y] �! p[x]
if p[x] = nil[T ]
then root[T ] �! y
else if x = left[p[x]]
then left[p[x]] �! y
else right[p[x]] �! y
left[y] �! x
p[x] �! y
Typeset by AMS-TEX
1
2
Wstawianie
 wstawiamy we zel z do drzewa T stosuja c modyfikacje BST
 kolorujemy z na czerwono
 aby zachować wlasności czerwono-czarne wywolujemy procedure
RB-INSERT-FIXUP, której zadaniem jest przekolorowanie
wezlów i wykonanie rotacji.
RB-INSERT(T, z)
y �! nil[T ]
x �! root[T ]
while x = nil[T ]
8
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 left[y] �! z
else right[y] �! z
left[z] �! nil[T ]
right[z] �! nil[T ]
color[z] �! RED
RB-INSERT-FIXUP (T, z)
3
Usuwanie
 usuń wezel z tak jak w BST
 jeżeli usuniety we zel jest czarny to wywolaj procedure
RB-DELETE-FIXUP
RB-DELETE(T, z)
if left[z] = nil[T ] or right[z] = nil[T ]
then y �! z
else y �! TREE-SUCCESSOR(z)
if left[y] = nil[T ]
8
then x �! left[y]
else x �! right[y]
p[x] �! p[y]
if p[y] = nil[T ]
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
if color[y] = BLACK
then RB-DELETE-FIXUP (T, x)
return y