PROCEDURE delete(k: keytype, VAR b, p: stree);
BEGIN IF b = NIL THEN p := NIL
ELSIF k < b^.key THEN delete(k, b^.left, p)
ELSIF k > b^.key THEN delete(k, b^.right, p)
ELSE (* k = b^.key *) unlink(b, p)
END;
END delete;
Mittels unlink(b, p) hängen wir die Wurzel
eines über b zugänglichen Teilbaumes nach p um
und reorganisieren ihn; dabei brauchen wir eine neue Wurzel,
falls er zwei Unterbäume hatte, sonst fällt er auseinander.
Wir verwenden dafür den "infix-ersten"
Knoten des rechten Unterbaumes, so bleibt der Baum ein Suchbaum
(rechts und links vertauscht ginge auch):
PROCEDURE unlink(VAR b, p);
BEGIN p := b;
IF p^.left = NIL THEN b := p^.right
ELSIF p^.right = NIL THEN b := p^.left
ELSE unlinkfirst(p^.right, b);
b^.left := p^.left; b^.right := p^.right;
END;
END unlink;