Zur Themenübersicht

Binäre Suchbäume

Programmtechnische Umsetzung (Borland Delphi^®)

Download des Delphi-Projektes (12kb). Bitte Readme.txt lesen!

Die Knoten des Baums

Die Knoten können auf verschiedene Art und Weise umgesetzt werden. Die hier vorgestellte Realisierung beruht auf einer Klasse, welche von TTreeNode abgeleitet wurde und den Namen TSTreeNode trägt.

Klassendefinition

TSTreeNode = Class(TTreeNode) Private Function MaxValue : TSTreeNode; Function ReadValue : TSortable; Procedure DeleteRoot; Public Function Delete(PSortable : TSortable) : Boolean; Function Search(PSortable : TSortable) : TSTreeNode; Function IsBalanced : Boolean; Procedure Insert(PSortable : TSortable); Property Value : TSortable Read ReadValue; End;

Einfügen eines Knotens

Das Einfügen eines neuen Knotens geschieht mit der Funktion Insert. Als Parameter muß ein sortierbares Element (Typ TSortable) übergeben werden. Ein Knoten, der neu eingefügt wird, ist automatisch ein Blatt.

Wenn der Knoten, welcher den `Insert`-Befehl keinen Wert enthält (also leer ist), so wird ihm der Wert des `Insert` übergebenen Parameters zugewiesen. Danach werden zwei neue (leere) Knoten erzeugt, die der aktuelle Knoten als Outdegree erhält. Dieses dient nur der Vereinfachung der Programmierung; der Outdegree des aktuellen Knotens beträgt also immer noch 0 (Blatt), obwohl er auf zwei (leere) Knoten zeigt.	`If IsEmpty Then Begin IValue := PSortable; LeftNode := TSTreeNode.Create; RightNode := TSTreeNode.Create; End`
Falls der Inhalt des übergebenen Elements kleiner als der des aktuellen Knotens ist, so wird dem Knoten links vom Aktuellen der `Insert`-Befehl erteilt.	`Else If PSortable.LT(TSortable(Value)) Then Begin TSTreeNode(LeftNode).Insert(PSortable); End`
Andernfalls (der Inhalt ist also größer als oder gleich dem Inhalt des aktuellen Knotens) wird dem Knoten rechts vom Aktuellen der `Insert`-Befehl erteilt.	`Else Begin TSTreeNode(RightNode).Insert(PSortable); End;`

Dadurch, daß jeder Knoten in Wirklichkeit den Outdegree 2 besitzt indem er auf leere Knoten zeigt, ist der rekursive Aufruf der Prozedur Insert möglich. Andernfalls müßte vor jedem rekursiven Aufruf überprüft werden, ob TSTreeNode(LeftNode) oder TSTreeNode(RightNode) auf Nil zeigt und gegebenenfalls neue Knoten erstellt werden.

Löschen eines Knotens

Die Methode, mit welcher ein Knoten gelöscht wird, hängt von seinem Outdegree ab. Das Löschen eines Knotens mit dem Outdegree 0 ist einfach, auch das Löschen eines Knotens mit dem Outdegree 1 stellt kein großes Problem dar. Wenn jedoch ein Knoten mit dem Outdegree 2 gelöscht werden soll, so gibt es zwei verschiedene Ersatzknoten. Dabei ist es also erforderlich, sich für einen von zwei Ersatzknoten zu entscheiden. Substituent kann entweder der Knoten mit dem größten Wert des linken Teilbaums oder der Knoten mit dem kleinsten Wert des rechten Teilbaums sein.

Das Löschen eines Knotens geschieht mit der öffentlichen Methode Function Delete(PSortable : TSortable) : Boolean;. Diese Methode überprüft, ob ein Knoten mit dem Wert PSortable in dem Baum vorhanden ist, ruft gegebenenfalls die private Löschmethode DeleteRoot dieses Knotens auf, und gibt zurück, ob der Knoten erfolgreich gelöscht werden konnte. Die Methode Procedure DeleteRoot; ist in vier Teile aufgeteilt.

Der Knoten ist ein Blatt (Outdegree = 0) Sicherheitshalber wird abgefragt, ob sich links sowie rechts vom Knoten Teilbäume befinden, bevor sie aus dem Speicher entfernt werden. Danach wird dem Knoten als `LeftNode`, `RightNode` und als `IValue`, welches den Inhalt des Knotens bezeichnet, `Nil` zugewiesen. Das Objekt, das den Inhalt des Knotens darstellt, wird hierbei nicht gelöscht, verbleibt also im Speicher.	`If Self.IsLeaf Then Begin If LeftNode <> Nil Then LeftNode.Remove; If RightNode <> Nil Then RightNode.Remove; Self.SetNil; End`
Der Knoten hat den Outdegree 1, der linke Teilbaum ist leer Hierbei wird zuerst der linke (leere) Teilbaum aus dem Speicher gelöscht, danach erhält der Knoten den Wert des rechten Knotens. Außerdem erhält er `LeftNode` und `RightNode` des rechten Knotens, bevor dieser ebenfalls gelöscht wird.	`Else If LeftNode.IsEmpty Then Begin LeftNode.Remove; TmpLeft := RightNode.LeftNode; TmpRight := RightNode.RightNode; IValue := RightNode.Value; LeftNode := TmpLeft; RightNode := TmpRight; RightNode.Remove; End`
Der Knoten hat den Outdegree 1, der rechte Teilbaum ist leer Diese Löschmethode unterscheidet sich prinzipiell nicht von der Vorherigen; es wird nur zuerst der rechte Teilbaum gelöscht, der Knoten erhält `LeftNode` und `RightNode` des linken Knotens und abschließend wird der linke Knoten gelöscht.	`Else If RightNode.IsEmpty Then Begin RightNode.Remove; TmpLeft := LeftNode.LeftNode; TmpRight := LeftNode.RightNode; IValue := LeftNode.Value; LeftNode := TmpLeft; RightNode := TmpRight; LeftNode.Remove; End`
Der Knoten hat den Outdegree 2 Falls der Knoten nicht in eine der obigen Bedingungen paßt, also den Outdegree 2 hat, so wird nach dem Ersatzknoten `Substitute` gesucht, welcher bei dieser Realisierung der Knoten mit dem größten Wert im linken Teilbaum ist. Nachdem dieser Knoten gefunden wurde, erhält der aktuelle Knoten den Wert des Ersatzknotens, abschließend ruft sich die Methode `DeleteRoot` rekursiv auf. Da der rechte Teilbaum des Ersatzknotens leer sein muß (sonst wäre er nicht der größte im Teilbaum), ist hierdurch die Anzahl der rekursiven Aufrufe dieser Prozedur auf 1 beschränkt. Der linke Teilbaum des Ersatzknotens muß freilich nicht zwingend leer sein.	`Else Begin Substitute := TSTreeNode(LeftNode).MaxValue; IValue := Substitute.Value; Substitute.DeleteRoot; End;`

Suchen eines Knotens im Baum

Das Suchen eines Knotens im Baum geschieht mit der Funktion Function Search(PSortable : TSortable) : TSTreeNode;. Falls ein Knoten mit dem Wert von PSortable gefunden werden konnte, so wird er zurückgegeben, andernfalls Nil.

Der aktuelle Knoten ist leer

Wenn der aktuelle Knoten leer ist, so konnte ein Knoten mit dem Inhalt von PSortable nicht gefunden werden; es wird also Nil als Ergebnis zurückgeliefert. Die Suche ist hiermit beendet.

If IsEmpty Then Begin Result := Nil; End

Der aktuelle Knoten ist nicht leer

In diesem Fall findet eine Reihe von Überprüfungen statt. Wenn der Inhalt von PSortable gleich dem des aktuellen Knotens ist, so wird der aktuelle Knoten als Ergebnis zurückgeliefert. Die Suche ist auch hiermit beendent.

Andernfalls wird überprüft, ob der Inhalt von PSortable kleiner als der des aktuellen Knoten ist. Da diese Überprüfungen ebenso wie beim Einfügen auf Textebene stattfinden, ist 100 zum Beispiel kleiner als 50. Wenn dies der Fall ist, findet ein rekursiver Aufruf der Funktion Search statt, das zurückgelieferte Ergebnis ist das Ergebnis von TSTreeNode(LeftNode).Search(PSortable), also das Ergebnis des Suchvorgangs im linken Teilbaum. Ist der Inhalt größer als der des aktuellen Knotens, so ist das Ergebnis das Resultat des Suchvorgangs im rechten Teilbaum.

Else Begin If PSortable.Equal(TSortable(Value)) Then Begin Result := Self; End Else Begin If PSortable.LT(TSortable(Value)) Then Begin Result := TSTreeNode(LeftNode).Search(PSortable); End Else Begin Result := TSTreeNode(RightNode).Search(PSortable); End; End; End;

Der eigentliche Baum

Nachdem die Knoten definiert wurden stellt man fest, daß der eigentliche Baum nur eine Klasse ist, die Knoten verwaltet und auf die Methoden ebendieser zurückgreift. Deshalb ist es nicht überraschend, daß die meisten Methoden in diesem Fall nur dem Zeichnen des Baums auf einer Zeichenfläche (Typ TCanvas) dienen.

TSTreeNodes = Class(TObject) Private ICanvas : TCanvas; ICanvasWidth : Word; ICanvasHeight : Word; IRoot : TSTreeNode; ICurrent : TSTreeNode; Function ReadCanvas : TCanvas; Function ReadCanvasWidth : Word; Function ReadCanvasHeight : Word; Procedure WriteCanvas(PCanvas : TCanvas); Procedure WriteCanvasWidth(PWidth : Word); Procedure WriteCanvasHeight(PHeight : Word); Function ReadRoot : TSTreeNode; Function ReadCurrent : TSTreeNode; Public Constructor Create; Function Delete(PSortable : TSortable) : Boolean; Function Search(PSortable : TSortable) : TSTreeNode; Procedure Left; Procedure Right; Procedure Reset; Procedure Insert(PSortable : TSortable); Procedure Draw(PNode : TSTreeNode; ShowBalance : Boolean = False; Redraw : Boolean = True; PDepth : Integer = 0; PXPos : Integer = -1; DifX : Integer = -1); Procedure DestroyNodes; Property Canvas : TCanvas Read ReadCanvas Write WriteCanvas; Property CanvasWidth : Word Read ReadCanvasWidth Write WriteCanvasWidth; Property CanvasHeight : Word Read ReadCanvasHeight Write WriteCanvasHeight; Property Root : TSTreeNode Read ReadRoot; Property Current : TSTreeNode Read ReadCurrent; End;