Subscribe to The Madman Scribblings        RSS Feed
-----

Generic Binary Tree

Icon Leave Comment
Generic Binary Tree

This blog post is a result of me, trying to decipher what was happen with tjoney's code in this post.

I've broken the post in to three distinct sections;-
1. Nodes
2. Tree
3. Proof of Concept Code



1. Node(Of T)

The basic layout of node is this.
                        LeftNode : Node(Of T)
                       /
Parent : Node(Of T) <-(Value : T)
                       \
                        RighNode : Node(Of T)



Value => What this node's value is.
Parent => Which node is the Parent of this Node
LeftNode => The Child to the Left of this Node
RighNode => The Child to the Right of the Node. (Note: I'm using Righ so the code layout looks cleaner.



Public Class Node(Of T As IComparable(Of T))
#Region "Instance Variables"
    Protected _Value As T
    Protected _LeftNode As Node(Of T)
    Protected _RighNode As Node(Of T)
    Protected _Parent As Node(Of T)
#End Region



    Public Sub New(v As T, p As Node(Of T))
        _Value = v
        _Parent = p
    End Sub


Let's us create a new instance of the Node Class, along with this Node Value and Parent.

    Public Overrides Function ToString() As String
        Return _Value.ToString
    End Function


Overriding the ToString() Function to Display the Node's Value. (It's also used by the watch window in the debugger.)

#Region "Properties"
    Property Parent() As Node(Of T)
        Get
            Return _Parent
        End Get
        Protected Friend Set(value As Node(Of T))
            _Parent = value
        End Set
    End Property
    Public Property Value As T
        Get
            Return _Value
        End Get
        Protected Friend Set(value As T)
            _Value = value
        End Set
    End Property
    Public Property Left As Node(Of T)
        Get
            Return _LeftNode
        End Get
        Protected Friend Set(value As Node(Of T))
            _LeftNode = value
        End Set
    End Property
    Public Property Righ As Node(Of T)
        Get
            Return _RighNode
        End Get
        Protected Friend Set(value As Node(Of T))
            _RighNode = value
        End Set
    End Property
#End Region





The follow helpers makes the code easier read and type.
#Region "Helpers"
    Public Function HasLeft() As Boolean
        Return _LeftNode IsNot Nothing
    End Function
    Public Function HasRigh() As Boolean
        Return _RighNode IsNot Nothing
    End Function
    Public Function ParentAbsent() As Boolean
        Return _Parent Is Nothing
    End Function
    Public Function LeftIsEmpty() As Boolean
        Return _LeftNode Is Nothing
    End Function
    Public Function RighIsEmpty() As Boolean
        Return _RighNode Is Nothing
    End Function
#End Region



The Operators
I've define some comparison operators to save me writting a.Value.CompareTo(b.Value) == 0 whenever I want check if to nodes have the same value. Also I've add some the compare a Node against a value.

#Region "Comparision Operators"
#Region "Node Based"
    Public Shared Operator =(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) = 0
    End Operator
    Public Shared Operator <>(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) <> 0
    End Operator
    Public Shared Operator <(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) < 0
    End Operator
    Public Shared Operator <=(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) <= 0
    End Operator
    Public Shared Operator >(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) > 0
    End Operator
    Public Shared Operator >=(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) >= 0
    End Operator
#End Region
#Region "Comparision Operators with Value"
    Public Shared Operator =(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) = 0
    End Operator
    Public Shared Operator <>(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) <> 0
    End Operator
    Public Shared Operator <(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) < 0
    End Operator
    Public Shared Operator >(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) > 0
    End Operator
    Public Shared Operator <=(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) <= 0
    End Operator
    Public Shared Operator >=(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) >= 0
    End Operator
#End Region
#End Region

End Class


And that's it, rather a simple class.




2. BTree(Of T)

        (3)
      /
    (16)
      \
        (22)
  /
(24)
  \
        (37)
      /
    (45)
      \
        (99)


Note: The Left child is the higher of the branches.

Public Class BTree(Of T As IComparable(Of T))
#Region "Instance Variables"
    Protected _root As Node(Of T)
#End Region
    Public Sub New()
        _root = Nothing
    End Sub



A Null value at the Root indicates the Tree is empty.

#Region "Insert Methods"
#Region "Insert based on value"
    Public Sub Insert(ByRef i As T)
        If _root Is Nothing Then
            _root = New Node(Of T)(i, Nothing)
        Else
            Insert(_root, i)
        End If
    End Sub

    Protected Sub Insert(ByRef ThisNode As Node(Of T), Value As T)
        If ThisNode > Value Then
            If ThisNode.LeftIsEmpty Then
                ThisNode.Left = New Node(Of T)(Value, ThisNode)
            Else
                Insert(ThisNode.Left, Value)
            End If
        Else
            If ThisNode.RightIsEmpty Then
                ThisNode.Righ = New Node(Of T)(Value, ThisNode)
            Else
                Insert(ThisNode.Righ, Value)
            End If
        End If
    End Sub
#End Region



You may be asking yourself why the two Insert methods. The first is the public method it makes clean simple API for the user.
It calls a second Protected method, which is internal mechanics of the insertion. This is because I utilise recursion, it save the user remembering who the correctly call it.

There's another protected insertion method inside the BinTree Class, it is utilised by the delete method.

#Region "Insert Based on nodes"
    Protected Sub Insert(ByRef ThisNode As Node(Of T), NodeBeingInserted As Node(Of T))
        If NodeBeingInserted < ThisNode Then
            If ThisNode.LeftIsEmpty Then
                ThisNode.Left = NodeBeingInserted
                NodeBeingInserted.Parent = ThisNode
            Else
                Insert(ThisNode.Left, NodeBeingInserted)
            End If
        Else
            If ThisNode.RightIsEmpty Then
                ThisNode.Righ = NodeBeingInserted
                NodeBeingInserted.Parent = ThisNode
            Else
                Insert(ThisNode.Righ, NodeBeingInserted)
            End If
        End If
    End Sub
#End Region
#End Region



Contains searches the BinTree to see if a key exists, it will only find the first occurrence of the key.
#Region "Contains"

    Public Function Contains(ByVal key As T) As Boolean
        Return _Contains(key) IsNot Nothing
    End Function

    Private Function _Contains(ByVal key As T) As Node(Of T)
        Dim current As Node(Of T) = _root
        While (current IsNot Nothing) AndAlso (current <> key)
            current = If(current > key, current.Left, current.Righ)
        End While
        Return current
    End Function
#End Region



When were clearing the BinTree, we need to get rid of all the references to the Nodes.
We can't simply set _root to nothing and be done with.

#Region "Deletion"
    Public Sub Clear()
        Dim NodeList As New List(Of Node(Of T))
        Traverse_InOrder_Nodes(_root, NodeList)
        NodeList.ForEach(Sub(n)
                             SetLinksToNull(n)
                             n = Nothing
                         End Sub)
        _root = Nothing
    End Sub



Deleting a Key

    Public Function Delete(ByVal key As T) As Boolean
        Dim NodeLoci = _Contains(key)
        ' Not Found is idicated by a null value.
        If NodeLoci Is Nothing Then Return False
        Dim ChildrenOfNode = Traverse_InOrder_Nodes_ExceptMe(NodeLoci)
        If NodeLoci.ParentAbsent Then
            _root = Nothing
            ChildrenOfNode.ForEach(Sub(n)
                                       SetLinksToNull(n)
                                       If _root Is Nothing Then
                                           _root = n
                                       Else
                                           Insert(_root, n)
                                       End If
                                   End Sub)
            Return True
        Else
            Dim MoveChildren = Function()
                                   ChildrenOfNode.ForEach(Sub(n) Insert(_root, SetLinksToNull(n))) ' Insert(NodeLoci.Parent, SetLinksToNull(n)))
                                   Return True
                               End Function
            With NodeLoci.Parent
                If .HasLeft AndAlso (.Left = NodeLoci) Then
                    .Left = Nothing : Return MoveChildren()
                ElseIf .HasRigh AndAlso (.Righ = NodeLoci) Then
                    .Righ = Nothing : Return MoveChildren()
                End If
            End With
        End If
        Return False
    End Function
#End Region




#Region "Helper Methods"
    Private Function SetLinksToNull(ByRef n As Node(Of T)) As Node(Of T)
        n.Left = Nothing
        n.Righ = Nothing
        n.Parent = Nothing
        Return n
    End Function
#End Region



Traversal of the Nodes in the BinTree
#Region "In-Order Traversals"

    Public Function Travers_InOrder_Values() As List(Of T)
        Dim rl As New List(Of Node(Of T))
        Traverse_InOrder_Nodes(_root, rl)
        Return rl.Select(Function(n) n.Value).ToList
    End Function

    Private Function Traverse_InOrder_Nodes_ExceptMe(ByRef thisNode As Node(Of T)) As List(Of Node(Of T))
        Dim Children_Left As New List(Of Node(Of T))
        Dim Children_Righ As New List(Of Node(Of T))
        If thisNode IsNot Nothing Then
            If thisNode.HasLeft Then Traverse_InOrder_Nodes(thisNode.Left, Children_Left)
            If thisNode.HasRigh Then Traverse_InOrder_Nodes(thisNode.Righ, Children_Righ)
        End If
        Children_Left.Reverse()
        Return Children_Left.Concat(Children_Righ).ToList()
    End Function

    Private Sub Traverse_InOrder_Nodes(ByVal thisNode As Node(Of T), ByRef NodeList As List(Of Node(Of T)))
        If thisNode IsNot Nothing Then
            If thisNode.HasLeft Then Traverse_InOrder_Nodes(thisNode.Left, NodeList)
            NodeList.Add(thisNode)
            If thisNode.HasRigh Then Traverse_InOrder_Nodes(thisNode.Righ, NodeList)
        End If
    End Sub



Outputting the BinTree.

The first PrintOut prints out the nodes values on one line.
(Note: The Input parameter is of type System.IO.TextWriter) which allow the outputted not only to console, but could be outputted to a file.
The Second PrintIndented outputs the BinTree as an ASCII Representation.

        (3)
      /
    (16)
      \
        (22)
  /
(24)
  \
        (37)
      /
    (45)
      \
        (99)




#Region "Output Displays"

    Public Sub PrintOut(cout As System.IO.TextWriter)
        Travers_InOrder_Values.ForEach(Sub(n) cout.Write("{0} ", n))
        cout.WriteLine()
        cout.Flush()
    End Sub 

    Public Sub PrintIndented(cout As System.IO.TextWriter)
        Traverse_InOrder_Indented(_root, cout, 0)
    End Sub

    Private Shared Sub Traverse_InOrder_Indented(ByVal thisNode As Node(Of T), cout As System.IO.TextWriter, Optional Indent As Integer = 0)
        If thisNode IsNot Nothing Then
            If thisNode.HasLeft Then
                Traverse_InOrder_Indented(thisNode.Left, cout, Indent + 4)
                cout.WriteLine("{0}{1}", New String(" ", 2 + Indent), "/")
            End If
            cout.WriteLine("{0}({1})", New String(" ", Indent), thisNode.Value.ToString)
            If thisNode.HasRigh Then
                cout.WriteLine("{0}{1}", New String(" ", 2 + Indent), "\")
                Traverse_InOrder_Indented(thisNode.Righ, cout, Indent + 4)
            End If
        End If
        cout.Flush()
    End Sub
#End Region


#End Region


End Class







3. Proof of Concept code.

Now let's try out our BinTree Class.


Module Module1
    Sub Main()
        Dim nums As New BTree(Of Integer)()
        nums.Insert(24)
        nums.Insert(45)
        nums.Insert(16)
        nums.Insert(37)
        nums.Insert(3)
        nums.Insert(99)
        nums.Insert(22)

        Console.WriteLine("Inorder Traversal: " & vbCrLf)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        nums.Delete(45)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        nums.Delete(16)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        nums.Delete(24)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        Console.Write("Press enter to continue. ")
        Console.ReadLine()
    End Sub

End Module






:shuriken:

0 Comments On This Entry

 

Search My Blog

Recent Entries

Recent Comments