Zur Themenübersicht     

Wir beschäftigen uns nun mit der Methode TSearchTreeNode.delete (Elem: TSortElement). Diese Methode löscht einen Knoten mit dem Inhalt 'Elem'  aus dem Baum, dessen Wurzel der ausführende Knoten ist. (Bezug wieder das Delphi-Projekt:  5_Suchbaum_Node_Lsg )

Kurze Anmerkung zum Aufruf vom Hauptformular aus: das Hauptformular  des Projektes verwaltet nur einen einzigen Knoten, nämlich die Wurzel des gesamten Baumes. Die Variable heißt Suchbaum und ist von der Klasse TSearchTreeNode. Die Methode wird vom Hauptformular einfach durch den Befehl Suchbaum.delete ( Loeschknoten) aufgerufen.

procedure TSearchTreeNode.delete(Elem: TSortElement);
Var delNode : TSearchTreeNode;
begin
   delNode := Self.Search(Elem);
   if delNode.isempty
      then showmessage('Knoten nicht vorhanden')
      else delNode.deleteRoot
end;

Die Prozedur besteht aus zwei Teilen. Im ersten Teil muss der entsprechende Knoten gesucht werden:  delNode:=Self.Search(Elem)  Gibt es einen solchen Knoten, dann wird im zweiten Teil die (private) Methode deleteRoot auf den gefundenen Knoten angewendet. Ist kein solcher Knoten vorhanden, kann auch nichts gelöscht werden und die Prozedur endet ohne etwas zu tun.

Wir wenden uns nun der Methode deleteRoot zu: 
Hier sind je nach Anzahl der Teilbäume drei Fälle zu unterscheiden:

• Fall 1: kein Teilbaum vorhanden (Outrdegree = 0)
• Fall 2: nur ein Teilbaum vorhanden (Outdegree = 1)
• Fall 3: zwei Teilbäume vorhanden (Outdegree = 2)

Zu Fall 1: Outdegree = 0:

Beispiel: Wenn wir im folgenden Baum

den Knoten 51 löschen, geschieht dies ganz einfach durch self.makenil.

Zu Fall 2: Outdegree = 1:

Beispiel: Wenn wir im folgenden Baum 

den Knoten 58 löschen, ist dieses immer noch recht einfach:  Wir ersetzen den Baum (mit der Wurzel 58) einfach durch seinen linken (oder rechten) Teilbaum. In der Prozedur deleteRoot sind dies die Programmzeilen: 

Das ist in unserem Beispiel der Fall
    Erläuterung am Beispiel:
links   hat oben die Wurzel 13
rechts hat oben die Wurzel 51
58 wird durch 49 ersetzt
Dann werden die Teilbäume von 49
wieder passend angehängt.


Hier analog wenn der linke Teilbaum 
leer ist.

if Self.ReadRightNode.isempty then begin

   links := Self.ReadLeftNode.ReadLeftNode;
   rechts:= Self.ReadLeftNode.ReadRightNode;
   Self.WriteValue(Self.ReadLeftNode.ReadValue);
   Self.WriteLeftNode(links);
   Self.WriteRightNode(rechts)
   end
else
   if Self.ReadLeftNode.isempty then begin
      links := Self.ReadRightNode.ReadLeftNode;
      rechts:= Self.ReadRightNode.ReadRightNode;
      Self.WriteValue(Self.ReadRightNode.ReadValue);
      Self.WriteLeftNode(links);
      Self.WriteRightNode(rechts)
   end

Derselbe Vorgang graphisch dargestellt:

führt dann zu:

Zu Fall 3: Outdegree = 2:

Beispiel: Wenn wir im folgenden Baum 

den Knoten 49 löschen wollen, ist dies etwas schwieriger zu realisieren: 
Zuerst suchen wir einen passenden Ersatzknoten. Da dieser größer als alle Knoten im linken Teilbaum und kleiner als alle Knoten im rechten Teilbaum (von 49) sein muss wählen wir den größten Knoten des linken Teilbaumes.  Hierfür gibt es die private Methode max:

Nach dem Ersetzen ist der Ersatzknoten zweimal vorhanden,

so dass wir ihn aus dem linken Teilbaum herauslöschen müssen. Da dieses Maximum keinen rechten Teilbaum mehr besitzt, (denn es gibt ja keine größeren Knoten mehr) ist das Löschen des Ersatzknotens nach Fall 1 oder 2 zu bewerkstelligen.

Damit ergibt sich für den dritten Fall folgender Programmcode:

Ersatzknoten ist Maximum des linken Teilbaums

Hier wird nur ein anderer Inhalt in den Knoten geschrieben.
Wie bei verketten Listen ist das Objekt, auf das der Knoten
  vorher zeigte, immer noch vorhanden. Soll dieses auch
  gelöscht werden, muss dies vom aufrufenden Objekt
  gesondert durchgeführt werden

 
Löschen des Ersatzknotens. (Man beachte die etwas
   aufwändige Syntax)

ersatz := TSearchTreeNode(Self.ReadLeftNode).max;

self.WriteValue(ersatz.ReadValue);






TSearchTreeNode(Self.ReadLeftNode).
               delete(TSortElement(ersatz.ReadValue))

Wenn der rechte Teilbaum leer ist, ist der Ersatzknoten
   gefunden,

Sonst ist es das Maximum im rechten Teilbaum

function TSearchTreeNode.max:TSearchTreeNode;
begin
   if Self.ReadRightNode.isempty then
      result := Self
   else
      result := TSearchTreeNode(Self.readRightNode).max
end;

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite