New Topic/Question
Reply
'Pankaj Pande
'IS 622
'AVL Tree Assignment
'
'
'
Imports System
Public Class clsAVLTree
'Data Members
Private nRoot As clsNode 'Stores the root node of the tree
'Constructor(s)
Public Sub New()
nRoot = Nothing
End Sub
'Properties
Public Property nodRoot() As clsNode
Get
Return nRoot
End Get
Set(ByVal nodValue As clsNode)
nRoot = nodValue
End Set
End Property
Property nodleft As clsNode
Property nodright As clsNode
'Methods
Public Function intFindMin() As Integer 'Finding Minimum value
Dim objCurrent As clsNode = nRoot
While (Not (objCurrent.Left Is Nothing))
objCurrent = objCurrent.Left
End While
objCurrent.DisplayNode()
Return objCurrent.Data
End Function
Public Function intFindMax() As Integer 'Finding Maximum value
Dim objCurrent As clsNode = nRoot
While (Not (objCurrent.Right Is Nothing))
objCurrent = objCurrent.Right
End While
objCurrent.DisplayNode()
Return objCurrent.Data
End Function
Public Function Find(ByVal intKey As Integer) As clsNode 'Finding certain value
Dim objCurrent As clsNode = nRoot
While (objCurrent.Data <> intKey)
If (intKey < objCurrent.Data) Then
objCurrent = objCurrent.Left
Else
objCurrent = objCurrent.Right
End If
If (objCurrent Is Nothing) Then
Console.WriteLine("Not in the set")
Return Nothing
End If
End While
objCurrent.DisplayNode()
Console.WriteLine("Is in the set")
Return objCurrent
End Function
'Inorder Traversal
Public Sub inOrder(ByVal theRoot As clsNode)
If (Not (theRoot Is Nothing)) Then
inOrder(theRoot.Left)
If theRoot.Deleted = False Then
theRoot.DisplayNode()
End If
inOrder(theRoot.Right)
End If
End Sub
'Breadth First Search Traversal or By Level Traversal
Public Sub ByLevel(ByVal theRoot As clsNode, ByVal udtHead As clsNode, ByVal udtTail As clsNode)
Dim queue As New clsQueue
'Insert the root in the queue
queue.AddTail(25, theRoot)
recursiveSearch(theRoot, queue)
End Sub
Public Sub recursiveSearch(ByVal theRoot As clsNode, ByVal queue As clsQueue)
theRoot.DisplayNode()
queue.removeQueue()
'Insert Left node
If Not (theRoot.Left Is Nothing) Then
queue.AddTail(23, theRoot.Left)
End If
'Insert Right node
If Not (theRoot.Right Is Nothing) Then
queue.AddTail(60, theRoot.Right)
End If
If Not (queue.Head.Right Is Nothing) Then
Dim udtTemp As New Object
udtTemp = queue.Head.Right.Data
recursiveSearch(udtTemp, queue)
End If
End Sub
'Insert Function
Public Function Insert(ByVal objItem As Object, ByVal nodN As clsNode) As clsNode
If (nodN Is Nothing) Then
nodN = New clsNode(objItem, Nothing, Nothing)
ElseIf (objItem.compareto(nodN.Data) < 0) Then
nodN.Left = Insert(objItem, nodN.Left)
If getHeight(nodN.Left) - getHeight(nodN.Right) = 2 Then
If (objItem.CompareTo(nodN.Left.Data) < 0) Then
nodN = RotateWithLeftChild(nodN)
Else
nodN = DoubleWithLeftChild(nodN)
End If
End If
ElseIf (objItem.compareto(nodN.Data) > 0) Then
nodN.Right = Insert(objItem, nodN.Right)
If (getHeight(nodN.Right) - getHeight(nodN.Left) = 2) Then
If (objItem.compareto(nodN.Right.Data) > 0) Then
nodN = RotateWithRightChild(nodN)
Else
nodN = DoubleWithRightChild(nodN)
End If
End If
Else
'do nothing, duplicate value
End If
nodN.getHeight = Math.Max(getHeight(nodN.Left), getHeight(nodN.Right)) + 1
Return nodN
End Function
Private Function RotateWithLeftChild(ByVal nodTwo As clsNode) As clsNode
Dim nodOne As clsNode = nodTwo.Left
nodTwo.Left = nodOne.Right
nodOne.Right = nodTwo
nodTwo.getHeight = Math.Max(getHeight(nodTwo.Left), getHeight(nodTwo.Right)) + 1
nodOne.getHeight = Math.Max(getHeight(nodOne.Left), nodTwo.getHeight) + 1
Return nodOne
End Function
Private Function RotateWithRightChild(ByVal nodOne As clsNode) As clsNode
Dim nodTwo As clsNode = nodOne.Right
nodOne.Right = nodTwo.Left
nodTwo.Left = nodOne
nodOne.getHeight = Math.Max(getHeight(nodOne.Left), getHeight(nodOne.Right)) + 1
nodTwo.getHeight = Math.Max(getHeight(nodTwo.Right), nodOne.getHeight) + 1
Return nodTwo
End Function
Private Function DoubleWithLeftChild(ByVal nodTwo As clsNode) As clsNode
nodTwo.Left = RotateWithRightChild(nodTwo.Left)
Return RotateWithLeftChild(nodTwo)
End Function
Private Function DoubleWithRightChild(ByVal nodTwo As clsNode) As clsNode
nodTwo.Right = RotateWithLeftChild(nodTwo.Right)
Return RotateWithRightChild(nodTwo)
End Function
Function getHeight(ByVal nodNode As clsNode) As Integer
If nodNode Is Nothing Then
Return 0
Else
Return nodNode.getHeight
End If
End Function
Public Function getSuccessor(ByVal delNode As clsNode) As clsNode
Dim nSuccessorParent As clsNode = delNode
Dim nSuccessor As clsNode = delNode
Dim nCurrent As clsNode = delNode.Right
While (Not (nCurrent Is Nothing))
nSuccessorParent.Left = nSuccessor
nSuccessor = nCurrent
nCurrent = nCurrent.Left
End While
If (Not (nSuccessor Is delNode.Right)) Then
nSuccessorParent.Left = nSuccessor.Right
nSuccessor.Right = delNode.Right
End If
Return nSuccessor
End Function
'Delete Function
Public Function Delete(ByVal intD As Object, ByVal nodRoot As clsNode) As Boolean
If nodRoot Is Nothing Then
Return False
Else
If intD = nodRoot.Data Then
nodRoot.Deleted = True
Return True
Else
If Delete(intD, nodRoot.Left) = True Or Delete(intD, nodRoot.Right) = True Then
Return True
Else
Return False
End If
End If
End If
End Function
End Class
This post has been edited by smohd: 15 February 2012 - 11:47 AM
Reason for edit:: Code tags added. Please use [code] tags when posting codes
MultiQuote
| 