Avl tree node insertion in vb.net

Vb program for Avl tree node insertion. Here problem description and other solutions.

' Include namespace system
Imports System 
'  Vb.net program
'  AVL Tree insertion

'  Avl Tree Node
Public Class TreeNode 
    Public  data As Integer
    Public  height As Integer
    Public  left As TreeNode
    Public  right As TreeNode
    
    Public Sub New(ByVal data As Integer)
        '  Set node value of avl tree
        Me.data = data
        Me.height = 1
        Me.left = Nothing
        Me.right = Nothing
    End Sub
End Class
Public Class AvlTree 
    '  Tree root node
    Public  root As TreeNode
    Public Sub New()
        '  Set value of root
        Me.root = Nothing
    End Sub
    '  Get the height of given node
    Public Function  getHeight(ByVal node As TreeNode) As Integer
        if (node  Is  Nothing) Then 
            Return 0
        End If
        Return node.height
    End Function 
    '  Get the max value of given two numbers
    
    Public Function  maxHeight(ByVal a As Integer, 
                               ByVal b As Integer) As Integer
        if (a > b) Then 
            Return a
        Else 
            Return b
        End IF

    
    End Function 
    '  Perform the Right rotate operation
    
    Public Function  rightRotate(ByVal node As TreeNode) As TreeNode
        '  Get left child node
        Dim leftNode As TreeNode = node.left
        '  Get left node right subtree
        Dim rightSubtree As TreeNode = leftNode.right
        '  Update the left and right subtree
        leftNode.right = node
        node.left = rightSubtree
        '  Change the height of modified node
        node.height = Me.maxHeight(
          Me.getHeight(node.left), Me.getHeight(node.right)) + 1
        leftNode.height = Me.maxHeight(
          Me.getHeight(leftNode.left), 
          Me.getHeight(leftNode.right)) + 1
        Return leftNode
    
    End Function 
    '  Perform the Left Rotate operation
    
    Public Function  leftRotate(ByVal node As TreeNode) As TreeNode
        '  Get right child node
        Dim rightNode As TreeNode = node.right
        '  Get right node left subtree
        Dim leftSubtree As TreeNode = rightNode.left
        '  Update the left and right subtree
        rightNode.left = node
        node.right = leftSubtree
        '  Change the height of modified node
        node.height = Me.maxHeight(
          Me.getHeight(node.left), Me.getHeight(node.right)) + 1
        rightNode.height = Me.maxHeight(
          Me.getHeight(rightNode.left), 
          Me.getHeight(rightNode.right)) + 1
        Return rightNode
    
    End Function 
    '  Get the balance factor
    
    Public Function  getBalanceFactor(ByVal node As TreeNode) As Integer
        if (node  Is  Nothing) Then 
            Return 0
        End If
        Return Me.getHeight(node.left) - Me.getHeight(node.right)
    
    End Function 
    '  Recursively, add a node in AVL tree
    '  Duplicate keys (data) are not allowed
    
    Public Function  addNode(ByVal node As TreeNode, 
                             ByVal data As Integer) As TreeNode
        if (node  Is  Nothing) Then 
            '  Return a new node
            Return New TreeNode(data)
        End If

        if (data < node.data) Then 
            node.left = Me.addNode(node.left, data)
        ElseIf (data > node.data) Then 
            node.right = Me.addNode(node.right, data)
        Else 
            '  When given key data already exists
            Return node
        End IF

        '  Change the height of current node
        node.height = 1 + Me.maxHeight(
          Me.getHeight(node.left), Me.getHeight(node.right))
        '  Get balance factor of a node
        Dim factor As Integer = Me.getBalanceFactor(node)
        '  LL Case
        if (factor > 1 AndAlso data < node.left.data) Then 
            Return Me.rightRotate(node)
        End If

        '  RR Case
        if (factor < -1 AndAlso data > node.right.data) Then 
            Return Me.leftRotate(node)
        End If

        '  LL Case
        if (factor > 1 AndAlso data > node.left.data) Then 
            node.left = Me.leftRotate(node.left)
            Return Me.rightRotate(node)
        End If

        '  RR Case
        if (factor < -1 AndAlso data < node.right.data) Then 
            node.right = Me.rightRotate(node.right)
            Return Me.leftRotate(node)
        End If

        Return node
    
    End Function 
    '  Print the tree in preorder form
    Public Sub preorder(ByVal node As TreeNode)
        if (node IsNot Nothing) Then 
            Console.Write("  " + node.data.ToString())
            Me.preorder(node.left)
            Me.preorder(node.right)
        End If
    End Sub
    '  Print the tree in inorder form
    Public Sub inorder(ByVal node As TreeNode)
        if (node IsNot Nothing) Then 
            Me.inorder(node.left)
            Console.Write("  " + node.data.ToString())
            Me.inorder(node.right)
        End If

    
    End Sub
    '  Print the tree in postorder form
    Public Sub postorder(ByVal node As TreeNode)
        if (node IsNot Nothing) Then 
            Me.postorder(node.left)
            Me.postorder(node.right)
            Console.Write("  " + node.data.ToString())
        End If
    End Sub
    
    Public Shared Sub Main(ByVal args As String())
        Dim tree As AvlTree = New AvlTree()
        '  Add tree node
        tree.root = tree.addNode(tree.root, 4)
        tree.root = tree.addNode(tree.root, 7)
        tree.root = tree.addNode(tree.root, 5)
        tree.root = tree.addNode(tree.root, 19)
        tree.root = tree.addNode(tree.root, 17)
        tree.root = tree.addNode(tree.root, 13)
        tree.root = tree.addNode(tree.root, 11)
        tree.root = tree.addNode(tree.root, 3)
        tree.root = tree.addNode(tree.root, 2)
        tree.root = tree.addNode(tree.root, -3)
        '  Resultant  AVL Tree
        '  -----------------
        '         7
        '        /  \ 
        '       /    \
        '      4      17
        '     / \     / \
        '    2   5  13  19
        '   / \     /
        ' -3   3   11
        Console.Write("Resultant AVL Tree")
        Console.Write(vbLf & "Preorder  :")
        tree.preorder(tree.root)
        Console.Write( vbLf & "Inorder   :")
        tree.inorder(tree.root)
        Console.Write(vbLf & "Postorder :")
        tree.postorder(tree.root)
    
    End Sub

End Class

Output

Resultant AVL Tree
Preorder  :  7  4  2  -3  3  5  17  13  11  19
Inorder   :  -3  2  3  4  5  7  11  13  17  19
Postorder :  -3  3  2  5  4  11  13  19  17  7


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved