Vyvážení Č-B stromu po zrušení
uzlu
Tomáš Pitner
jaro 2004
Rušení uzlu v Č-B stromu
ˇ Probíhá nejprve jako v normálním binárním
vyhledávacím stromě - tj. převede se na
rušení listu; byl-li bílý, nemusíme už dělat
nic; byl-li černý, musíme ,,se černé zbavit"
úpravami naznačenými na dalších slidech;
ˇ celý algoritmus rušení uzlu je na hlavních
slidech IB002;
ˇ zde ukazujeme pouze jednotlivé 1-2c
případy úprav stromu (přebarvení, rotace)
po odebrání uzlu.
Případ 1 - černý otec, syn
černočerný a bílý
d
tb h
tf
tj
h
d
tf
tj
tb
Případ 2a - lib. otec, syn
černočerný a černý,
jeho první syn (f) bílý
d
tb h
tg
te
f ti
f
d h
tb te
tg
ti
Případ 2b - lib. otec, syn
černočerný a černý,
jeho druhý syn (h) bílý
d
tb f
te
ti
tg
h
f
d h
tb te
tg
ti
Případ 2c - lib. otec, syn
černočerný a černý,
jehož žádný syn není bílý
d
tb h
tj
dd
tf
tb h
tjtf
Nemůže se to zacyklit?
ˇ Případ 1 vede k tomu, že se černočerný uzel
dostane hlouběji, což by mohlo vést k zdání,
že se ČeČe barvy nezbavíme.
ˇ V následujícím kroku ale již máme vedle
sebe ČeČe (tb) a Če uzel (tf) -> odbarvíme!