Suchbäume (4)

Wir wollen den infix-ersten Knoten eines Suchbaumes abhängen. Das ist entweder seine Wurzel, falls der linke Unterbaum leer ist, oder der erste Knoten dieses Unterbaumes. Der Baum ist vorher und auch nachher über b zugänglich, auch wenn sich dabei seine Wurzel ändert; nach p kommt ein Verweis auf den abgehängten Knoten: 
PROCEDURE unlinkfirst(VAR b, p);
BEGIN IF b^.left = NIL THEN p := b; b := p^.right;
      ELSE unlinkfirst(b^.left, p)
      END;
END unlinkfirst;
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!

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.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36