Wörterbuchoperationen (4) Entfernen eines Schlüssels
Das Entfernen eines Schlüssels x gelingt nach folgendem Schema:
Suche nach x. Falls x nicht gefunden STOP. Ansonsten gibt es (genau) einen Knoten k mit
Knoten k hat nur Blätter: Entferne diese und mache Knoten k zu Blatt.
Knoten k hat ein Blatt und einen Teilbaum: Entferne das Blatt, entferne x aus Knoten k und mache diesen zur Wurzel des Teilbaumes.
Knoten k hat zwei Teilbäume: Suche nach kleinstem Schlüssel im rechten Teilbaum B_r. Dieser liege im Knoten q mit Wert y. q muss links ein Blatt haben. Ersetze den Schlüssel x des Knotens k durch y und entferne den Schlüssel y aus B_r.