Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


14. Elementare Suchmethoden



Löschen

Die oben angegebenen Implementationen für die grundlegenden Funktionen search, insert und sort unter Verwendung binärer Baumstrukturen sind sehr unkompliziert. Binäre Bäume liefern jedoch auch ein gutes Beispiel für ein rekurrentes Problem bei Suchalgorithmen: Die Funktion delete läßt sich oft nur mit viel Mühe implementieren.

Betrachten wir den in Abbildung 14.12 links dargestellten Baum: Das Löschen eines Knotens ist einfach, wenn der Knoten keine Nachfolger hat, wie L oder P (man trenne ihn ab, indem man die entsprechende Verkettung in seinem Vorgänger löscht), oder wenn er nur einen Nachfolger hat, wie A, H oder R (man ändere die Verkettung im Nachfolger in die entsprechende Verkettung des Vorgängers), oder selbst dann, wenn einer seiner beiden direkten Nachfolger keine Nachfolger hat, wie N (man benutze jenen Knoten, um den Vorgänger zu ersetzen); doch wie steht es mit Knoten weiter oben im Baum, wie etwa E?

Abbildung 14.12
Abbildung 14.12 Löschen (von E) aus einem binären Suchbaum.

Abbildung 14.12 zeigt einen Weg, wie der Knoten E gelöscht werden kann: Ersetze ihn durch den Knoten mit dem nächstgrößeren Schlüssel (in diesem Falle H). Dieser Knoten hat garantiert höchstens einen Nachfolger (da es keine Knoten zwischen ihm und dem zu löschenden Knoten gibt, muß seine linke Verkettung Null sein) und kann leicht entfernt werden. Um das E aus dem Baum auf der linken Seite von Abbildung 14.12 zu entfernen, sorgen wir dann dafür, daß die linke Verkettung von R auf die rechte Verkettung (N) von H zeigt, kopieren die Verkettungen aus dem Knoten, der E enthält, auf den Knoten, der H enthält, und lassen head^.r auf H zeigen. Dies liefert den Baum auf der rechten Seite der Abbildung.

Das Programmsegment, das benötigt wird, um alle diese Fälle zu erfassen, ist etwas komplizierter als die einfachen Routinen für Suchen und Einfügen, doch es verdient eine sorgfältige Untersuchung als Vorbereitung auf die komplizierteren Operationen mit Bäumen, die wir im nächsten Kapitel ausführen werden. Die folgende Prozedur löscht den Knoten, auf den t zeigt, aus dem Baum mit der Wurzel bei x. Demzufolge kann ein Knoten mit dem Schlüssel v mit Hilfe des Aufrufs treedelete(treesearch(v, head),head) gelöscht werden. Die Variable p wird benutzt, um den Vorgänger von x im Baum zu verfolgen, und die Variable c wird verwendet, um den Knoten zu finden, der den zu löschenden Knoten ersetzen soll. Nach dem Löschen ist x der Nachfolger von p. Das eigentliche Beseitigen des Knotens, auf den t zeigt, wird der aufrufenden Routine überlassen (oder vielleicht soll der Knoten einer bestimmten anderen Datenstruktur zugefügt werden).

    procedure treedelete(t,x: link);
      var p,c: link;
      begin
        repeat
          p:=x;
          if t^.key<x^.key then x:=x^.l else x:=x^.r
        until x=t;
        if t^.r=z then x:=x^.l
        else if t^.r^.l=z then
          begin x:=x^.r; x^.l:=t^.l end
        else
          begin
          c:=x^.r; while c^.l^.l<>z do c:=c^.l;
          x:=c^.l; c^.l:=x^.r;
          x^.l:=t^.l; x^.r:=t^.r
          end;
        if t^.key<p^.key then p^.l:=x else p^.r:=x;
        end;

Das Programm durchsucht den Baum zuerst in der üblichen Weise, um die Position von t im Baum zu ermitteln. (In Wirklichkeit besteht der Hauptzweck dieser Suche darin, p zu setzen, so daß ein anderer Knoten eingegliedert werden kann, nachdem t verschwunden ist.) Danach überprüft das Programm drei Fälle: Wenn t keinen rechten Nachfolger hat, so wird der linke Nachfolger von t nach dem Löschen zum Nachfolger von p (dies würde in Abbildung 14.12 für C, L, M, P und R der Fall sein); wenn t einen rechten Nachfolger ohne linken Nachfolger hat, so wird dieser rechte Nachfolger nach dem Löschen zum Nachfolger von p, wobei seine linke Verkettung von t übernommen wird (dies würde in Abbildung 14.12 für A und N der Fall sein); in den übrigen Fällen wird x auf den Knoten mit dem kleinsten Schlüssel im Unterbaum rechts von t gesetzt; die linke Verkettung seines Vorgängers wird auf die rechte Verkettung dieses Knotens gesetzt, und seine beiden Verkettungen werden von t übernommen (dies würde in der Abbildung 14.12 für H und E der Fall sein). Um die Anzahl der Fälle klein zu halten, löscht dieses Programm stets, indem es sich nach rechts orientiert, auch wenn es in manchen Fällen einfacher sein könnte, sich nach links zu orientieren (zum Beispiel um H in Abbildung 14.12 zu löschen).

Diese Vorgehensweise scheint asymmetrisch und recht willkürlich zu sein: Warum sollte man zum Beispiel nicht den Schlüssel unmittelbar vor dem zu löschenden Schlüssel benutzen, anstelle des Schlüssels nach ihm? Verschiedene ähnliche Modifikationen wurden vorgeschlagen, doch Unterschiede dürften in praktischen Anwendungen kaum zu bemerken sein, obwohl gezeigt worden ist, daß der obige Algorithmus zu einem leicht unausgeglichenen Baum führen kann (durchschnittliche Höhe proportional zu sqrtN), wenn eine sehr große Anzahl von »Löschen-Einfügen« Paaren ausgeführt wird.

Es ist tatsächlich sehr typisch für Suchalgorithmen, daß sie für das Löschen wesentlich kompliziertere Implementationen erfordern: Die Schlüssel selbst sind meist untrennbare Bestandteile der Struktur, und das Entfernen eines Schlüssels kann komplizierte Reparaturen erforderlich machen. Ein Ausweg, der oft zweckmäßig ist, ist das sogenannte späte Löschen (lazy deletion), wobei ein Knoten in der Datenstruktur belassen wird, jedoch für Suchzwecke als »gelöscht« markiert wird. Im obigen Programm kann dies implementiert werden, indem eine weitere Prüfung auf solche Knoten hinzugefügt wird, bevor die Suche abgebrochen wird. Man muß gewährleisten, daß eine große Anzahl »gelöschter« Knoten nicht zu einer übermäßigen Vergeudung von Zeit oder Speicherplatz führt, doch es zeigt sich, daß diese Frage für viele Anwendungen ohne Bedeutung ist. Eine Alternative wäre, die gesamte Datenstruktur periodisch neu aufzubauen und dabei die »gelöschten« Knoten auszulassen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]