Natürliche binäre Suchbäume

Definition: Ein natürlicher binärer Suchbaum über einem durch $\leq$ geordneten Universum U ist ein interner Binärbaum (Schlüssel an den internen Knoten).

Sortierungsbedingung:

(Alle Schlüssel im l. UB von v) $\leq$ Key(v) $\leq$ (Alle Schlüssel im r. UB von v)

Lemma: Die In-Order-Linialisierung eines binären Suchbaumes mit obigen Suchwegbedingungen ergibt eine aufsteigende Folge von Schlüsselwertern.

Operationen:

• IsElement(K,T) :
  
  

  
  		 v ist Wurzel;
  		 while ($v \neq$ Blatt) do
  		 		 if Key(v) = K then return (Val(K));
  		 		 elseif Key(v) $\le K$ then v:=rechtes Kind von v;
  		 		 else v:=linkes Kind von v;
  		 		 fi
  		 od 
  

• Insert(K,T) :
  
  

  
  
  Führe    IsElement(K,T) aus;
  		 Sei K nicht enthalten, dann führt    IsElement zu Blatt w (NIL-Pointer);
  		 Füge man Knoten v mit Key(v)=K an Blatt w ein;
  

• Delete(K,T) :
  
  

  
  
  Führe    IsElement(K,T) aus.
  		 Sei K enthalten, dann führt    IsElement zu Knoten w (i.a. interne Knoten).
  		 Ersetze w durch seinen in-order-Vorgänger oder -Nachfolger.
  

$\parbox{65mm}{\textbf{Problem:} Lineare Entartung von nat\uml {u}rlic... ...ich sind $\Rightarrow$\space $\vert$\space E($h$) - $\theta(\sqrt{n}) \vert$.}$