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(logn) (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);  // two aux. variables
  while  x != nil          // find the right leaf
  do
    y := x;                // y to remember the father
    if   key(z) < key(x)
    then x := left(x) 
    else x := right(x)
  od;                     
  p(z) := y;               // => x is nil, y its predecessor
  if   y = nil             // special case: y = root
  then root(T) := z
  else if   key(z) < key(y)// insert z at the appropriate
       then  left(y) := z  // place as new leaf
       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: node to delete
  if   left(z) = nil or right(z) = nil
    then y := z              // y replaces  x
    else y := Successor(z);  // where: y has <= 1 child!

  if left(y) != nil          // determine the child x
     then x :=  left(y)      // of  y (might be empty)
     else x := right(y);
                                 // change the pointers
  if x != nil then p(x) = p(y);  // remove y  => x has
                                 // new parent
  if p(y) = nil                  // special case: root
    then root(t) = x
    else if  y = left(p(y))
           then  left(p(y)) := x
           else right(p(y)) := x  // y ist now removed from
                                  // its orig. place

  if y != z then key(z) := key(y);// replace z by y

  return y;                      // and that's it