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 zle 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
Wyszukiwarka
Podobne podstrony:
nw asd w12w12House M D [4x11] Frozen (XviD asd)nw asd w3W12 zad transpasd 2033sPrivate Practice [1x09] In Which Dell Finds His Fight (XviD asd)asdasd 1041trGhost Whisperer [1x04] Mended Hearts (XviD asd)asd 1013rASD Przykład Stal 2010The L Word [1x12] Locked Up (XviD asd)asd 1012dmrw12w12(1)House M D [4x14] Living The Dream (XviD asd)więcej podobnych podstron