Úvod

Vkladanie a vymazávanie vrcholov v binárnom strome sú operácie, ktoré menia túto dynamickú množinu. Preto treba zabezpečiť, aby sa aj po ich vykonaní zachovali vlastnosti binárneho prehľadávacieho stromu. Časová zložitosť oboch operácií je O(h), kde h je hĺbka stromu.

^ TOP

Vkladanie

Procedúra Tree-Insert vloží do binárneho stromu T novú hodnotu v. Procedúre je odovzdaný uzol z, pre ktorý platí key[z]=v, left[z]=nil, right[z]=nil. Táto procedúra modifikuje T a niektoré časti T tak, že je možné vložiť z na príslušnú pozíciu v strome.

Procedúra Tree-Insert začína v koreni a sleduje cestu nadol. Ukazovateľ x postupne prechádza túto cestu a zároveň je y stále nastavený na jeho otca. V cykle while sa ide nadol a od porovnania kľúčov key[y] a key[x] závisí výber ľavého alebo pravého syna. Keď sa algoritmus dostane na spodok stromu, bude mať x hodnotu nil. Vtedy sa jednoduchým nastavením smerníkov vloží prvok z do stromu.

    Tree-Insert(T,x)
    y := nil
    x := root[T]
    while (x!= nil) do
      y := x
      if (key[z] < key[x])
      then x := left[x]
      else x := right[x]
    p[z] := y
    if (y = nil)
      then root[T] := z
      else if (key[z] < key[y])
             then left[y] := z
             else right[y] := z        
      

^ TOP

Vymazávanie

Procedúra pre vymazávanie uzla z z binárneho prehľadávacieho stromu má ako parameter ukazovateľ na z. Táto procedúra uvažuje tri prípady:  a) Ak z nemá potomkov, tak jeho rodičovi zmeníme smerík na nil a vymažeme uzol v.  b) Ak má z iba jedného potomka, tak daný uzol odstránime vytvorením spojenia medzi jeho rodičom a jeho synom.  c) Ak má z dvoch potomkov, odstránime nasledovníka (successor) y uzla z, ktorý určite nemá ľavého syna (bol by ním z) a nahradíme obsah z obsahom uzla y.

    Tree-Delete(T,z)
    if (left[z] = nil) or (right[z] = nil)
      then y := z
      else y := Tree-Successor(z)
    if (left[y] != nil)
      then z := left[y]
      else x := right[y]
    if (x != nil)
      then p[x] := p[y]
    if (p[y] = nil)
      then root[T] := x
      else if (y = left[p[y]]) 
             then left[p[y]] := x
             else right[p[y]] := x
    if (y != z) then 
      key[z] := key[y]
      //skopíruj aj ostatné satelitné dáta
    return y
      

^ TOP

Vizualizácia mazania, prípad 1

Ak z nemá potomkov.

^ TOP

Vizualizácia mazania, prípad 2

Ak z má iba jedného potomka.

^ TOP

Vizualizácia mazania, prípad 3

Ak z má dvoch potomkov.

^ TOP