6.4. Naív törlés

Function KÖVETKEZő(x) 
Input: x a fa gyökerének a címe 
Output: a következő elemet tartalmazó csúcs címe, illetve Nil 
1  if x.jobb != Nil then 
2     return MINIMUM(x.jobb)
3  else 
4     y = x.apa // y legyen x szülője 
5     while y != Nil and x = y.jobb do 
6        x = y 
7        y = y.apa 
8     endw 
9     return y
10 endif

Új elemet a fa leveleként szúrtuk be. Ennek megfelelően levelet könnyű törölni.

Nem nehéz a törlés akkor sem, ha a törlendő csúcsnak csak egy utódja van. Ekkor az elemet a megfelelő részfával kell helyettesíteni.

Ha viszont egyik részfa sem üres, akkor kicsit bonyolultabb a helyzet. Lyuk nem maradhat a fában, s a beszúrandó elemnek nagyobbnak kell lennie, mint a megmaradó bal részfa összes elemének, s kisebbnek mint a megmaradó jobb részfa összes elemének. Két lehetséges megoldás lehet: a bal részfa maximális, vagy a jobb részfa minimális eleme. Ezen elemek egyikét törölni kell a régi helyéről, s a törlendő elem helyére rakni. Az előbbi ábrákon és a következő programban y jelzi, hogy mely csúcs törlődik valóban.

Az x az y utódát jelzi, s az y-ra mutató mutatónak ezután az x-re kell mutatnia. A beszúrás és a törlés bonyolultsága a keresett elem magasságának lineáris függvénye O(h), hasonlóan a kereséshez, vagy a minimum, maximum meghatározásához. A bin-fa.htm állomány tartalmazza azt a programot, amellyel egy bináris fába lehet elemeket beszúrni, illetve onnan törölni.

Function TÖRÖL(T,z) 
Input: T a fa, z a törlendő csúcs 
Eredmény: A T fából törli a z csúcsot 
1  if z.bal = Nil or z.jobb = Nil 
2  then 
3     y = z 
4  else 
5     y = KÖVETKEZŐ(z)
6  endif 
7  if y.bal != Nil then 
8     x = y.bal 
9  else 
10    x = y.jobb
11 endif 
12 if x != Nil then 
13    x.apa = y.apa 
14 endif
15 if y.apa == Nil then 
16    T.gyökér = x 
17 else 
18    if y == y.apa.bal then 
19       y.apa.bal = x 
20    else 
21       y.apa.jobb = x 
22    endif
23 endif 
24 if y != z then 
25     z.kulcs = y.kulcs 
26     // és át kell másolni a további mezőket is 
27 endif 
28 return y