Diese Routine ist überraschenderweise korrekt, obgleich das erst nicht so aussieht: sie reorganisiert den über ihren VAR-Parameter b adressierten Baum. Ist kein linker Unterbaum vorhanden, so bekommt der Baum eine andere Wurzel; beim rekursiven Aufruf bleibt aber die Wurzel erhalten, und der linke Unterbaum wird reorganisiert; dabei kann er eine neue Wurzel bekommen, die an der gleichen Stelle angekettet wird!PROCEDURE unlinkfirst(VAR b, p); BEGIN IF b^.left = NIL THEN p := b; b := p^.right; ELSE unlinkfirst(b^.left, p) END; END unlinkfirst;
Die Routinen delete und unlinkfirst und auch unsere oben angegebene Routine insert zum Einfügen neuer Elemente sind rekursiv, sogar rechtsrekursiv; aber ihre Ergebnisparameter werden nicht alle identisch durchgereicht. Sie in iterative Routinen umzuformen ist dennoch möglich, aber etwas mühsam, und das Ergebnis ist unübersichtlich. Wir sparen uns den Versuch deshalb, weil wir annehmen, daß in der Regel das Neueintragen und Austragen gegenüber dem Suchen und Modifizieren eher selten vorkommt, sodaß sich der Aufwand wohl nicht lohnt.
Eine interessante Beobachtung ist noch, daß eine Infix-Durchwanderung eines Suchbaums jedes Datenelement nach den Elementen mit kleinerem Schlüssel und vor den Elementen mit größerem Schlüssel bearbeitet, also genau in aufsteigend sortierter Reihenfolge; wir haben also gratis ein Sortierverfahren erhalten. Das Verfahren ist gar nicht schlecht, aber es gibt noch bessere mit geringerem Speicherbedarf, und daher wird man es nur anwenden, wenn der Suchbaum aus anderen Gründen ohnehin vorliegt.