Implementation eines Binärbaumes ◦ Zusammenfassung ◦ ?

Binärbäume vereinen die Vorteile verketteter Strukturen mit der Möglichkeit einer effizienten Suche. Dafür sind die Algorithmen, insbesondere jene für das Durchlaufen der Elemente, komplizierter. Wir illustrieren die Implementation eines Binärbaumes und eines Einfügealgorithmus in VBA anhand des Wörterbuchbeispiels.

Die Knoten eines Binärbaumes werden wie die Zellen einer verketteten Liste in einem Klassenmodul beschrieben, jedoch mit zwei Objektvariablen für die Verweise auf das linke und das rechte Kind. Ein Knotenobjekt des Wörterbuchbeispiels benötigt zudem zwei Variablen für den Inhalt. Die eine Variable speichert den deutschen Begriff, die andere die englische Definition.

Klassenmodul cEintrag

    Public Begriff As String         			'Inhalt
    Public Definition As String      			'Inhalt
    Public KindLinks As cEintrag     			'Verweis auf linkes Kind
    Public KindRechts As cEintrag    			'Verweis auf rechtes Kind

Wir erweitern die Implementation noch um eine fünfte Eigenschaft, die einen Verweis auf das Elternobjekt speichert.

    Public Vater As cEintrag         'Rückwärtsverweis auf Vaterknoten

Strukturen, die auch Rückwärtsverweise verwalten, bezeichnet man als doppelt verkettet. In doppelt verketteten Listen und Bäumen kann man sich freier bewegen als in einfach verketteten Strukturen. Die Neuverkettung bei den Einfüge- und Löschoperationen ist jedoch aufwändiger.

Die Klasse für die Wörterbucheinträge ist damit definiert. Instanzen davon zu erstellen und zu einem Baum zu verketten, ist Aufgabe des Wörterbuchs, das wir ebenfalls in einem Klassenmodul beschreiben. Die Klasse cWörterbuch vereinbart hierfür zunächst eine Objektvariable Wurzel für den Verweis auf den Wurzelknoten. Dieser Verweis bildet quasi den "Keim", von dem aus der Baum aufgebaut wird, und den Startpunkt für jede Suche im Baum.

Klassenmodul cWörterbuch

    Private Wurzel As cEintrag

Der Wurzelknoten wird erstellt, wenn dem Wörterbuch zum ersten Mal ein Begriffs/Definitions-Paar hinzugefügt wird. Der Baum besitzt in diesem Fall noch keine Wurzel, und die Objektvariable Wurzel verweist ins Nichts. Der folgende Programmausschnitt aus der Methode fügeHinzu prüft, ob der Baum noch leer ist, erstellt gegebenenfalls das Wurzelobjekt und füllt das Begriffspaar ein (vgl. Entwurfscode in sortierter Binärbaum). Die Wurzel hat als einziger Knoten keinen Vorgänger und muss deshalb nicht rückwärts auf einen Vater verweisen. Begriff und Definition sind die Argumente der Prozedur fügeHinzu.

    If Wurzel Is Nothing Then        			'der Baum ist noch leer
      Set Wurzel = New cEintrag      			'neuer Wurzelknoten
      Wurzel.Begriff = Begriff       			'Inhalt
      Wurzel.Definition = Definition 			'Inhalt
    ...

Zur Erzeugung der restlichen Knoten definiert die Klasse cWörterbuch zwei Unterprogramme. Die Prozedur erzeugeKindLinks erstellt einen neuen Knoten und hängt ihn an einen bestehenden Knoten als linkes Kind an. In der zweiten Zeile setzt die Prozedur einen Rückwärtsverweis auf das Vaterobjekt.

    Private Sub erzeugeKindLinks(Knoten As cEintrag, _
                              Begriff As String, _
                              Definition As String)
      Set Knoten.KindLinks = New cEintrag       	'neuer Knoten
      Set Knoten.KindLinks.Vater = Knoten       	'Rückwärtsverweis
      Knoten.KindLinks.Begriff = Begriff        	'Inhalt
      Knoten.KindLinks.Definition = Definition  	'Inhalt
    End Sub

Die Prozedur erzeugeKindRechts erzeugt auf analoge Weise ein rechtes Kind. Die folgende Testprozedur erzeugt mit den beiden Prozeduren einen kleinen Baum. Das nächste Bild zeigt das Ergebnis, das entsteht, wenn man ein Wörterbuchobjekt erstellt und die Testprozedur ausführt:

Klassenmodul cWörterbuch (nur zum Testen):

    Public Sub Test()
      Set Wurzel = New cEintrag                   	'Wurzel
      Wurzel.Begriff = "kind"
      Wurzel.Definition = "child"
      erzeugeKindLinks Wurzel, "ast", "branch"    	'linkes Kind
      erzeugeKindRechts Wurzel, "wurzel", "root"  	'rechtes Kind
    End Sub

Wir implementieren nun die Methode fügeHinzu, die einen sortierten Baum aus gegebenen Begriffspaaren aufbaut und die in sortierter Binärbaum als Entwurfscode formuliert wird:

Klassenmodul cWörterbuch

    Public Sub FügeHinzu(Begriff As String,
                         Definition As String)
      Dim Knoten As cEintrag
      If Wurzel Is Nothing Then
        Set Wurzel = New cEintrag
        Wurzel.Begriff = Begriff
        Wurzel.Definition = Definition
      Else
        Set Knoten = Wurzel
        Do Until Begriff = Knoten.Begriff
          If Begriff < Knoten.Begriff Then
            If Knoten.KindLinks Is Nothing Then erzeugeKindLinks Knoten, Begriff, Definition
            Set Knoten = Knoten.KindLinks
          Else
            If Knoten.KindRechts Is Nothing Then erzeugeKindRechts Knoten, Begriff, Definition
            Set Knoten = Knoten.KindRechts
          End If
        Loop
      End If
    End Sub

©abo