Operationen auf Suchbäumen

Search(p,x)

Die Suche eines Schlüsselwerts $x$ erfolgt durch den Funktionsaufruf $Search(p,x)$, wobei $p$ der Wurzelknoten ist¹. Wir verfahren nach folgender Methode:

• starte in der Wurzel
• sei $p$ der aktuelle Knoten
  • ist $key(p) > x$, dann suche $x$ im linken Teilbaum von $x$ (falls möglich $\Rightarrow p \neq NIL$)
  • ist $key(p) < x$, dann suche $x$ im rechten Teilbaum von $x$ (falls möglich $\Rightarrow p \neq NIL$)
  • ist $key(p) = x$, dann beende die Suche.

Der Algorithmus $Search(x,p)$ ist so formuliert, dass ein Knoten $z$ zurückgegeben wird:

• Für eine erfolgreiche Suche ist $key(z) = x$.
• Für eine erfolglose Suche zeigt $z$ auf NIL.

Die Rückgabe des Knotens $z$ wird für das Löschen bzw. Einfügen benötigt.

Insert(VAR p, x)

Um einen Schlüssel in einem Suchbaum einzufügen, suchen wir zunächst nach dem einzufügenden Schlüssel $x$ im gegebenen Baum. Der nichtgefundene Schlüssel $x$ wird dann an der erwartenden Position $p$ unter den Blättern eingefügt. D.h. wir ersetzen das Blatt durch einen inneren Knoten mit dem einzufügenden Schlüssel $x$ als Wert und zwei Blätter als Söhnen. So entsteht wieder ein Suchbaum. Abbildung 3 veranschaulicht dies.

Abbildung 3: Einfügen in einen Suchbaum

Delete(p,x)

Beim Löschen eines Schlüsselwerts $x$, der als Markierung eines Knotens $v$ gefunden wurde, sind drei Fälle zu unterscheiden:

• Ist $v$ ein Blatt, dann wird $v$ einfach gelöscht.
• Wenn $v$ genau einen Sohn $w$ hat, dann kann man wie folgt vorgehen:
  • ist $v$ die Wurzel, dann wird $v$ gelöscht und $w$ zur Wurzel gemacht.
  • ist $u$ der Vater von $v$, dann kann man $v$ löschen und die Kante $(u,v)$ durch die Kante $(u,w)$ ersetzen.
• Wir nehmen an, dass $v$ zwei Söhne hat. Wir bestimmen zunächst denjenigen Knoten $w$ im linken Teilbaum von $v$, der mit dem nächst kleineren Schlüsselwert markiert ist. Dieser ist der grösste Schlüsselwert im linken Teilbaum von $v$ und lässt sich durch die Suche des Schlüsselwertes $x = key(v)$ im linken Teilbaum von $v$ bestimmen. Die Markierung $key(w)$ wird dann zur Markierung von $v$ gemacht und der Knoten $w$ gelöscht. Zu beachten: Der Knoten $w$ hat keinen rechten Sohn, kann also gemäss Fall 1 oder 2 gelöscht werden. Tatsächlich gelöscht wird also stets nur solche Knoten, die höchstens einen Sohn haben.

Abbildung 4: Löschen von Knoten

Abbildung 5: Löschen von Knoten(2)

Im wesentlichen wird für alle drei Operationen der Suchbaum auf einem Pfad von der Wurzel bis zu einem Blatt durchlaufen. Damit ergeben sich folgende Kosten:

• Die Grundoperationen Suchen, Löschen und Einfügen in einen binären Suchbaum $T$ lassen sich in Zeit $\Theta(\textrm{H\uml ohe}(T)) = O(n)$ durchführen. Dabei ist $n$ die Anzahl der Schlüsselwerte (Knoten) in $T$.
• $[ \log n ] \leq \textrm{H\uml ohe}(T) \leq n-1$