VBAで二分探索木

BSTree.cls.vba

Option Explicit

Private Root As TreeNode
Private Values() As String

Public Sub Add(v As String)
    Dim n As TreeNode
    
    If Root Is Nothing Then
        Set Root = New TreeNode
        Root.Value = v
        Exit Sub
    End If
    
    Set n = Root
    
    Do
        If v < n.Value Then
            If n.Left Is Nothing Then
                Set n.Left = New TreeNode
                n.Left.Value = v
                Exit Do
            Else
                Set n = n.Left
            End If
        Else
            If n.Right Is Nothing Then
                Set n.Right = New TreeNode
                n.Right.Value = v
                Exit Do
            Else
                Set n = n.Right
            End If
        End If
    Loop
End Sub

Public Function Contains(v As String) As Boolean
    Contains = Not Contains_(Root, v) Is Nothing
End Function

Private Function Contains_(n As TreeNode, v As String) As TreeNode
    If n Is Nothing Then
        Set Contains_ = Nothing
    ElseIf v = n.Value Then
        Set Contains_ = n
    ElseIf v < n.Value Then
        Set Contains_ = Contains_(n.Left, v)
    Else
        Set Contains_ = Contains_(n.Right, v)
    End If
End Function

Public Property Get ArrayValue() As String()
    Erase Values
    Walk Root
    ArrayValue = Values
End Property

Private Sub Walk(n As TreeNode)
    If n Is Nothing Then
        Exit Sub
    End If
    If Not n.Left Is Nothing Then
        Walk n.Left
    End If
    
    ReDim Preserve Values(MaxIndex(Values) + 1) As String
    Values(UBound(Values)) = n.Value

    Walk n.Right
End Sub

Private Function MaxIndex(a) As Long
    On Error GoTo Err
    MaxIndex = UBound(a)
    Exit Function
Err:
    MaxIndex = -1
End Function

Module1.bas

Option Explicit

Sub test()
    Const COUNT As Long = 20000
    Dim SArray4 As BSTree
    Dim strArray4() As String
    Dim strBase(COUNT) As String
    Dim i As Long
    Dim t As Single
    
    Randomize
    For i = 0 To COUNT
        strBase(i) = Int(Rnd * COUNT)
    Next i
    
    ' 二分探索木
    t = Timer
    Set SArray4 = New BSTree
    For i = 0 To COUNT
        SArray4.Add strBase(i)
    Next i
    
    strArray4 = SArray4.ArrayValue
    Debug.Print Timer - t
    Stop
End Sub

TreeNode.cls.vba

Option Explicit

Public Value As String
Public Left As TreeNode
Public Right As TreeNode