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ý

                           Případ 2a - lib. otec, syn černočerný a černý,
                                      jeho první syn (f) bílý

                           Případ 2b - lib. otec, syn černočerný a černý,
                                      jeho druhý syn (h) bílý

                           Případ 2c - lib. otec, syn černočerný a černý,
                                     jehož žádný syn není bílý

                                       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!