7   Binäre Bäume

Literatur: Kapitel 13 aus [CLR90]. Balancierte Bäume stammen aus [AVL62].

Inhalt Binäre Bäume ·Baumoperationen

• Unterstützung vieler Wörterbuchoperationen
• Baumstrukturen effizient
• Effizienz der Operationen proportional Höhe des Baumes = O(log n) (falls der Baum ``ausgeglichen'')
• Viele Varianten, abhängig von der Anwendung
  • Rot/Schwarz-Bäume [Bay72]
  • B-Bäume
  • AVL-Bäume [AVL62]
  • Splay-Trees
  • (a,b)-Bäume, z.B. (2,3)-Bäume (2-3-Bäume)
  • selbst-balancierende Bäume
  • ...

• Die Elemente des Baumes sind `` sortiert''
• Þ Ausgeben der sortierten Elemente = rekursives Durchlaufen des Baumes (in-order tree walk)⁵

InOrder-Tree-Walk(t) =
  if   t != nil
  then InOrder-Tree-Walk(left(t));
       print (key(t));
       InOrder-Tree-Walk(right(t));

• wichtige Operation auf Suchbäumen
• Komplexität: O(h), wobei h die Höhe
• Minimum/Maximum bestimmen: genauso einfach (der linkeste/rechteste Knoten im Baum)

Search(t,k) =                // t : tree, k : key
  if         t == nil    then raise error("Not found")
  else if    k == key(t) then return t
  else if    k <  key(t) 
       then Search( left(t),k)
       else Search(right(t),k)

Search(t,k) =                // t : tree, k : key
  while (t != nil) and (k != key(t))
  do
    if k < key(t)
       then t :=  left(t)
       else t := right(t)
  od;
  if   (t == nil) 
  then raise error("Not Found")
  else return t

• Einfügen immer an den Blättern
• Komplexität: O(h)

Insert(T,z) =              // T : tree, z : node to insert
  y := nil; x := root(T);  // zwei Hilfsvariablen
  while  x != nil          // finde das passende Blatt
  do
    y := x;                // y zum merken des Vaters
    if   key(z) < key(x)
    then x := left(x) 
    else x := right(x)
  od;                     
  p(z) := y;               // => x ist nil, y sein Vorgaenger
  if   y = nil             // Sonderfall: y = Wurzel;
  then root(T) := z
  else if   key(z) < key(y)// f"uge an der passenden Stelle
       then  left(y) := z  // z als neues Blatt ein.
       else right(y) := z 

• Problem (s. Bild):
  • Erhalt der Baumeigenschaft: innere Knoten müssen ersetzt werden
  • Erhalt der Sortierungseigenschaft: der Ersatz muß passen
• Baumnachfolger eines Knotens x: Nachfolger in der in-order-Baumordnung
  • falls Knoten mit rechtem Kind:
  • Þ Nachfolger = der ``linkeste'' Knoten im rechten Teilbaum.
  • Þ Nachfolger hat kein linkes Kind!
  • Þ key(left(x)) £ key(x) £ key(succ(x)) £ key(right(x))⁷
• Þ
  Nachfolger ersetzt zu löschenden inneren Knoten
• Komplexität: O(h)

Minimum(z) = // input: binary search tree, output: node with min. key
  while left(z) $\not=$ nil 
  do  z := left(z)
  od
  return z;

Sucessor(z) 
  if   right(z) $\not=$ nil
  then return Minimum(right(z))
  y:=parent(z);
  while y $\not=$ nil and z=right(y)
  do
 z := y;
 y := parent(y);
  od
  return y;

Delete(T,z)           // T = tree, z = zu loeschender Knoten
  if   left(z) = nil or right(z) = nil
    then y := z              // y tritt an die Stelle von x
    else y := Successor(z);  // wobei: y hat <= 1 Kind!

  if left(y) != nil          // Bestimmung des Kindes x
     then x :=  left(y)      // von y.
     else x := right(y);
                                 // Ver"andern der Verzeigerung
  if x != nil then p(x) = p(y);  // y herausgenommen => x mit 
                                 // neuem Vater
  if p(y) = nil                  // Spezialfall: wurzel
    then root(t) = x
    else if  y = left(p(y))
           then  left(p(y)) := x
           else right(p(y)) := x  // y ist nun  vom
                                  //  urspr. Platz entfernt

  if y != z then key(z) := key(y);// z durch y ersetzen

  return y;