Gegeben: B-Baum mit minimalem Branchingfaktor t

Alternative 1 (Vorlesung): 

Lösche key k:

0. Suche Knoten x mit key k
1. Wenn k in *Blatt* x: lösche k aus x.
 1.1 kein Unterlauf: fertig.
 1.2 Unterlauf: Rekursion zu 3.
2. Wenn k in *innerem Knoten* x:
   - lösche k aus x und 
   - ersetze k durch direkten(!) Vorgänger oder Nachfolger k' im linken
     oder rechten Teilbaum, d.h. k' ist der rechteste Key im rechtesten
     Blatt im linken Teilbaum bzw. umgekehrt (vgl. Binärbaum).
   - lösche k' (=> Rekursion zu 1.)
3. Unterlauf in Knoten x:
 3.1 der rechte Bruder von x, Knoten z, ist *nicht* minimal besetzt:
     - Füge den Seperator-Key k' aus dem gemeinsamen Vaterknoten v in x
       ganz rechts ein.
     - Füge linken Teilbaum von k'' rechts an k' in x, wobei k'' Key in z
       ganz links.
     - Ersetze k' in v durch Key k'' aus z.
     - Lösche k'' in z.
 3.2 der linke Bruder von x, Blatt y, ist *nicht* minimal besetzt:
     spiegelverkehrt.
 3.3 beide Brüder y und z sind minimal, haben also nur t-1 keys:
     - Verschmelze x (bzw. y), den Seperatorkey k' aus v und z (bzw. x)
       zu neuem Knoten x, dieser hat dadurch 2*(t-1)+1 = 2t-1 keys,
       gehorcht also der B-Baum-Bedingung.
     - Lösche k' und dessen rechten (bzw. linken) Teilbaum z (bzw. y) aus
       v. Dadurch kann Knoten v unterlaufen (=> Rekursion zu 3.)


Alternative 2 (nicht Vorlesungsstoff! vgl. "Introduction to Algorithms"):

Der Algorithmus aus Alternative 1 muß den ganzen Baum runterlaufen, um in
einem Blatt einen Key zu löschen, und im schlechtesten Fall den ganzen
Baum wieder hochlaufen, um den Unterlauf bis zur Wurzel zu propagieren.
Man kann aber Schritt 0 und Schritt 3 aus Alternative 1 kombinieren:

0. Suche Key k. Dies ist eine Rekursion durch den Baum. Prüfe für jeden
   Rekursionsschritt, ob der gerade betrachtete Knoten x minimal ist.
   Wenn ja, führe Ausgleich wie in Punkt 3 aus Alternative 1 durch.
   Bemerkungen:
   a) der Ausgleich setzt sich nicht nach oben fort, weil wir ja von oben
      kommen und schon dafür gesorgt haben, dass es dort keine minimalen
      Knoten mehr gibt.
   b) der Vaterknoten v ist Knoten x' aus dem vorangehenden
      Rekursionschritt, kann also noch im Hauptspeicher gehalten werden.
1. Wenn k in *Blatt* x: lösche k aus x. (Kein Unterlauf wegen Schritt 0.)
2. Wenn k in *innerem Knoten* x:
   - lösche k aus x und 
   - suche direkten(!) Vorgänger k' von k im linken oder rechten Teilbaum
     (=> Rekursion zu 0.).
   - ersetze k durch k'.
   - lösche k' (=> Rekursion zu 1.)