Zeiger in VB - Seite 6

Ein Binärbaum  

Bäume

Eine Datenstruktur möchte ich noch vorstellen: den Binärbaum. Leider müssen wir uns hier schon wieder von unserer praktischen, da unifizierten Schnittstelle verabschieden, denn Bäume, obgleich Containerklassen, brauchen eine andere Schnittstelle.

Bäume sind im Prinzip immer gleich aufgebaut: sie bestehen aus Knoten ("Nodes"), wobei ein Knoten die Wurzel ("Root") darstellt. Jeder Knoten kann mehrere Kindesknoten ("Children") haben und jeder Knoten außer der Wurzel hat einen Elternknoten ("Parent"). Knoten, die den selben Elternknoten haben, werden Geschwister ("Siblings") genannt. Knoten, die sich ganz außen an einem Baum befinden, also keine Kinder haben. werden Blätter ("Leaves") genannt.

Wir haben jetzt also eine hierarchische Struktur definiert, die sich von einem Startpunkt aus verzweigen kann. Folgende Grafik soll helfen, dies zu verdeutlichen:

Jede Linie zwischen den Elementen stellt hierbei einen Zeiger dar - und zwar in beide Richtungen, was bedeutet, dass jedes Element einen Zeiger für seine Eltern und jeweils einen für seine Kinder braucht.

Binärbaum

Der oben dargestellte Baum ist ein besonderer Baum, ein so genannter Binärbaum. Binär deswegen, weil jeder Knoten maximal zwei Kinder hat. Ein Binärbaum hat verschiedene Einsatzgebiete. Eines davon ist die Sortierung von Feldern: Wenn Elemente bereits beim Einfügen in einen Container sortiert würden, würde das später eine Menge Arbeit ersparen. Genau hier hilft der Binärbaum: Wenn man ihm ein Element hinzufügt, überprüft die Baumklasse, ob das Element größer oder kleiner als das Wurzelelement ist. Ist es kleiner, so wird es dem linken Knoten hinzugefügt. Ist es größer, wird es dem rechten Knoten angehängt. Diese Abfrage geschieht bei jedem Knoten, bis sich irgendwann ein nicht definierter (= leerer) Knoten findet. Dieser wird nun mit dem Wert belegt.

Hierbei wird ein rekursiver Abstieg ("recursive descent") benötigt, der relativ zeitaufwendig ist, verglichen beispielsweise mit einem einfachen Anhängen ans Ende einer Kette aber dafür sind die Elemente bereits sortiert und, was später Zeit spart.

Die Knotenstruktur

Ein Knoten eines Baumes hat eine recht simple Struktur:

Public Type Node
    Data    As String
    Left    As Long
    Right   As Long
End Type

Listing 13

Den Verweis auf den Elternknoten haben wir uns hier gespart, da er in einem Binärbaum, anders als bei anderen Bäumen, nicht gebraucht wird. Left und Right sind Zeiger auf die beiden Kindesknoten.

Die Schnittstellen

Die Schnittstelle eines Binärbaums ist ein wenig komplizierter, jedoch kann man sich mit einem Trick das Leben leicht machen: Eigentlich bräuchte ein Binärbaum all die Mechanismen, die es einem ermöglichen, gezielt Elemente im Baum anzusprechen und zu modifizieren, wie eben in einem Feld.

Aber wieso dann nicht gleich ein Feld nehmen? Das einzige, was wir am Binärbaum brauchen, ist die Sortierung. Aus diesem Grund kann man sich Arbeit ersparen, indem man einfach eine Funktion zum Hinzufügen von Elementen implementiert und eine Funktion ToArray(), die aus dem Binärbaum ein sortiertes Feld erstellt und zurückgibt.

Damit bräuchten wir folgende Funktionen:

• Clear() zum Löschen des Baums,

• Push() um ein neues Element hinzuzufügen,

• Size um die Größe des Baumes zu erfahren,

• ToArray() um ein Feld aus dem Baum zu erstellen,

• FromArray() um aus einem Feld einen Binärbaum zu erstellen und

• Clone() um eine Kopie des Baumes zu erstellen.

Die Implementierung

Folgender Code stellt die vollständige Implementierung der obigen Schnittstelle mit Zeigern dar. Der Code ist etwas komplizierter als die beiden vorherigen Codes, da wir des öfteren mit Rekursion arbeiten müssen, um eine selbe Operation auf mehrere Knoten auszuführen. Funktionen, die dies tun, fangen mit Rec an und sind privat.

' BinTree.cls
Option Explicit

Option Compare Text

Private m_Root  As Long
Private m_Size  As Long
'----------------------------------------------------

Private Sub Class_Terminate()
    Call Clear
End Sub
'----------------------------------------------------

Public Sub Clear()
    If m_Root Then
        Call RecClear(m_Root)
        m_Size = 0
    End If
End Sub

Public Sub Push(Item As String)
    If m_Root Then
        Call RecPush(Item, m_Root)
    Else
        m_Root = Alloc()
        Heap(m_Root).Seg.Data = Item
    End If
    
    m_Size = m_Size + 1
End Sub

Public Property Get Size() As Long
    Size = m_Size
End Property

Public Function ToArray() As String()
    If m_Root = 0 Then _
        Exit Function
    ToArray = RecToArray(m_Root)
End Function

Public Sub FromArray(Values() As String)
    Dim I As Long
    
    Call Clear
    
    For I = LBound(Values) To UBound(Values)
        Call Push(Values(I))
    Next I
End Sub

Public Function Clone() As BinTree
    Set Clone = New BinTree
    
    ' einfacher, aber langsamer (!) Weg
    ' der Leser ist zum Implementieren einer schnelleren Methode eingeladen
    Call Clone.FromArray(ToArray())
End Function
'----------------------------------------------------

Private Sub RecPush(ByRef Node As Long, Item As String)
    If Node = 0 Then
        Node = Alloc()
        Heap(Node).Seg.Data = Item
    Else
        Dim pTmp As Long
        
        If Item < Heap(Node).Seg.Data Then
            pTmp = Heap(Node).Seg.Left
            Call RecPush(pTmp, Item)
            Heap(Node).Seg.Left = pTmp
        ElseIf Item > Heap(Node).Seg.Data Then
            pTmp = Heap(Node).Seg.Right
            Call RecPush(pTmp, Item)
            Heap(Node).Seg.Right = pTmp
        End If
    End If
End Sub

Private Function RecToArray(Node As Long) As String()
    Dim TempArr()   As String
    Dim LeftArr()   As String
    Dim RightArr()  As String
    Dim CurrItem    As Long
    Dim Offset      As Long
    Dim ArrSize     As Long
    Dim LeftnRight  As Long
    
    ArrSize = 1
    
    If Heap(Node).Seg.Left Then
        LeftArr = RecToArray(Heap(Node).Seg.Left)
        LeftnRight = 1
        ArrSize = ArrSize + UBound(LeftArr) + 1
    End If
    
    If Heap(Node).Seg.Right Then
        RightArr = RecToArray(Heap(Node).Seg.Right)
        LeftnRight = LeftnRight Or 2
        ArrSize = ArrSize + UBound(RightArr) + 1
    End If
    
    ReDim TempArr(ArrSize - 1)
    
    If LeftnRight And 1 Then
        For CurrItem = 0 To UBound(LeftArr)
            TempArr(CurrItem) = LeftArr(CurrItem)
        Next CurrItem
        
        Offset = CurrItem
    End If
    
    TempArr(Offset) = Heap(Node).Seg.Data
    Offset = Offset + 1
    
    If LeftnRight And 2 Then
        For CurrItem = 0 To UBound(RightArr)
            TempArr(Offset + CurrItem) = RightArr(CurrItem)
        Next CurrItem
    End If
    
    RecToArray = TempArr
End Function

Private Sub RecClear(ByRef Node As Long)
    If Heap(Node).Seg.Left Then _
        Call RecClear(Heap(Node).Seg.Left)
    If Heap(Node).Seg.Right Then _
        Call RecClear(Heap(Node).Seg.Right)
    
    Call Free(Node)
    Node = 0
End Sub

Listing 14

Erläuterungen

Dieser Code schreit nach Erklärungen.

Zunächst das einfachste: Clear(). Hier wird einfach RecClear() mit der Wurzel als Argument aufgerufen. In RecClear() ruft sich die Funktion rekursiv auf, und zwar mit ihrem linken Kind, dann mit ihrem rechten Kind (sofern diese Knoten überhaupt definiert sind). Dann wird der aktuelle Knoten gelöst. Zu diesem Zeitpunkt haben wir durch die rekursiven Aufrufe dafür gesorgt, dass der aktuelle Knoten keine Kinder mehr hat. Dieses Rekursionsverfahren nennt sich Tiefensuche ("depth first traversal").

In Push() wird einfach RecPush() mit der Wurzel und dem neuen Wert aufgerufen und dann die Größe erhöht. In RecPush() wird zunächst überprüft, ob der Knoten noch nicht existiert (gleich null ist). Ist dies der Fall, so wird er angelegt und der neue Wert ihm zugewiesen. Existiert der Knoten jedoch schon, so wird geschaut, ob der neue Wert kleiner ist, als der aktuelle Knoten. Ist dies der Fall, so wird RecPush() mit dem linken Kind des aktuellen Knotens aufgerufen. Ist der Wert größer, so wird RecPush() mit dem rechten Kind als Argument aufgerufen. Bei den Aufrufen müssen wir leider einen kleinen Umweg über eine temporäre Variable in Kauf nehmen. Dies ist nötig, da es sein kann, dass wir während des rekursiven Aufrufs das Heap-Feld vergrößern müssen, was nicht möglich ist, wenn ein Feldeintrag als ByVal-Parameter in Benutzung ist (Laufzeitfehler 10).

Man beachte, dass nichts passiert, wenn die Werte gleich groß, also identisch sind. Identische Werte werden von einem Binärbaum ausgefiltert. Somit ist jeder Wert in einem Binärbaum einmalig.

In ToArray() wird lediglich RecToArray() mit der Wurzel als Argument aufgerufen, es sei denn, die Wurzel sei nicht definiert, in welchem Falle die Funktion verlassen wird. RecToArray() ist leider ein wenig komplizierter, zumindest auf den ersten Blick. Wir sollten uns daher darüber klar werden, was diese Funktion macht. Sie erstellt ein Teilfeld, das den aktuellen Knoten und alle Kindern enthält. Dafür muss sie zunächst Teilfeldes für die Kindesknoten erstellen (durch rekursiven Aufruf) und dann diese Teilfeldes zusammensetzen, mit sich selbst dazwischen. Dieses resultierende Feld gibt sie dann zurück.

Und genau dies macht die Funktion: Zuerst wird die Feldgröße auf eins gesetzt, da das resultierende Teilfeld mindestens einen Eintrag hat: den aktuellen Knoten. Nun wird geschaut, ob das linke Kind definiert ist; sollte dies der Fall sein, so wird das linke Teilfeld durch rekursiven Aufruf erstellt und in einer Hilfsvariable gespeichert. Außerdem wird die Feldgröße um die Größte des Teilfeldes erhöht und ein Flag, LeftnRight gesetzt; dieser Flag sagt uns später, dass wir ein linkes Teilfeld haben. Für Erklärungen siehe Verwendung von Flags [Tutorial 4006].

Die Prozedur wiederholt sich für das rechte Kind.

Nun wird das Teilfeld korrekt dimensioniert. Dann wird geschaut, ob der Flag für das linke Kind gesetzt worden ist und so dies der Fall ist, werden die Elemente aus dem linken temporären unserem Teilfeld hinzugefügt. Hernach folgt der Wert des aktuellen Knotens. Sollte der Flag für den rechten Kindesknoten gesetzt sein, werden nun die Werte aus dem rechten Teilfeld hinzugefügt. Dann wird das Teilfeld zurückgegeben. Fertig.

Funktionsbeispiel

Und hier folgt ein feines kleines Funktionsbeispiel:

Sub Main()
    Call SetHeapSize(20)
    
    Dim MyTree  As BinTree
    Dim Words() As String
    Dim I       As Long
    Dim MyArr() As String
        
    Set MyTree = New BinTree
    
    ' some words to sort
    Words = Split("Visual Basic can kick ass with pointers even without API use!", " ")
    
    Call MyTree.FromArray(Words)
    
    MyArr = MyTree.ToArray()
    
    For I = 0 To UBound(MyArr)
        Debug.Print MyArr(I)
    Next I
End Sub

Listing 15

Der Code gibt die Wörter aus dem Beispielsatz dem Alphabet nach sortiert aus.

Zum Download des Beispielcodes.