-
Notifications
You must be signed in to change notification settings - Fork 7
/
SelfBalancingBinaryTree.vb
205 lines (187 loc) · 5.93 KB
/
SelfBalancingBinaryTree.vb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
'*************************************************************
' * SelfBalancingBinaryTree.vb
' * Created by Stephen Hall on 11/21/17.
' * Copyright (c) 2017 Stephen Hall. All rights reserved.
' * Self Balancing Binary Tree implementation in Visual Basic
' *************************************************************
Namespace Trees.SelfBalancingBinaryTree
''' <summary>
''' Self Balancing Binary Tree Class
''' </summary>
''' <typeparam name="T">Generic Type</typeparam>
Public Class SelfBalancingBinaryTree(Of T As IComparable)
''' <summary>
''' Node class for SelfBalancingBinaryTree
''' </summary>
Public Class Node
''' <summary>
''' public members of the node class
''' </summary>
Public Property Left As Node
Public Property Right As Node
Public Property Data As T
Public Property Height As Integer
''' <summary>
''' Node Constructor
''' </summary>
Public Sub New()
Left = Nothing
Right = Nothing
Data = Nothing
Height = 0
End Sub
''' <summary>
''' Node Constructor
''' </summary>
''' <param name="data1">Data for the node to hold</param>
Public Sub New(data1 As T)
Left = Nothing
Right = Nothing
Data = data1
Height = 0
End Sub
End Class
''' <summary>
''' Private members
''' </summary>
Private _root As Node
Private _count As Integer
''' <summary>
''' SelfBalancingBinaryTree Constructor
''' </summary>
Public Sub New()
_root = Nothing
_count = 0
End Sub
''' <summary>
''' Insert data into the tree
''' </summary>
''' <param name="data">data to insert</param>
Public Sub Insert(data As T)
_root = Insert(data, _root)
End Sub
''' <summary>
''' Inserts data into the tree
''' </summary>
''' <param name="data">data to insert</param>
''' <param name="node">node to start at</param>
''' <returns>new root</returns>
Private Function Insert(data As T, node As Node) As Node
If node Is Nothing Then
node = New Node(data)
ElseIf LessThan(data, node.Data) Then
node.Left = Insert(data, node.Left)
If Height(node.Left) - Height(node.Right) = 2 Then
node = If(LessThan(data, node.Left.Data), RotateLeft(node), DoubleLeft(node))
End If
ElseIf GreaterThan(data, node.Data) Then
node.Right = Insert(data, node.Right)
If Height(node.Right) - Height(node.Left) = 2 Then
node = If(GreaterThan(data, node.Right.Data), RotateRight(node), DoubleRight(node))
End If
End If
node.Height = Max(Height(node.Left), Height(node.Right)) + 1
_count += 1
Return node
End Function
''' <summary>
''' Rotates the given root node left
''' </summary>
''' <param name="node">node to rotate</param>
''' <returns>new root</returns>
Private Function RotateLeft(node As Node) As Node
Dim tmp As Node = node.Left
node.Left = tmp.Right
tmp.Right = node
node.Height = Max(Height(node.Left), Height(node.Right)) + 1
tmp.Height = Max(Height(tmp.Left), node.Height) + 1
Return tmp
End Function
''' <summary>
''' Rotates the given root node right
''' </summary>
''' <param name="node">node to rotate</param>
''' <returns>new root</returns>
Private Function RotateRight(node As Node) As Node
Dim tmp As Node = node.Right
node.Right = tmp.Left
tmp.Left = node
node.Height = Max(Height(node.Left), Height(node.Right)) + 1
tmp.Height = Max(Height(tmp.Right), node.Height) + 1
Return tmp
End Function
''' <summary>
''' Rotates the left child right than the root node left
''' </summary>
''' <param name="node">root node to rotate</param>
''' <returns>new root</returns>
Private Function DoubleLeft(node As Node) As Node
node.Left = RotateRight(node.Left)
Return RotateLeft(node)
End Function
''' <summary>
''' rotates the right child left than the root right
''' </summary>
''' <param name="node">node to rotate</param>
''' <returns>new root</returns>
Private Function DoubleRight(node As Node) As Node
node.Right = RotateLeft(node.Right)
Return RotateRight(node)
End Function
''' <summary>
''' Gets the size of the tree
''' </summary>
''' <returns>number of node in the tree</returns>
Public Function Size() As Integer
Return _count
End Function
''' <summary>
''' Gets the height of the node
''' </summary>
''' <param name="node">node to test</param>
''' <returns>height of the node</returns>
Private Function Height(node As Node) As Integer
Return If(node Is Nothing, -1, node.Height)
End Function
''' <summary>
''' Function to get the max of left/right node
''' </summary>
''' <param name="left">left element to test</param>
''' <param name="right">right element to test</param>
''' <returns>the max of given left and right</returns>
Private Shared Function Max(left As Integer, right As Integer) As Integer
Return If(left > right, left, right)
End Function
''' <summary>
''' check if tree is empty
''' </summary>
''' <returns>rue|false</returns>
Public Function IsEmpty() As Boolean
Return _root Is Nothing
End Function
''' <summary>
''' Clears the data from the tree
''' </summary>
Public Sub Clear()
_root = Nothing
End Sub
''' <summary>
''' Determines if a is less than b
''' </summary>
''' <param name="a">generic type to test</param>
''' <param name="b">generic type to test</param>
''' <returns>true|false</returns>
Private Shared Function LessThan(a As T, b As T) As Boolean
Return a.CompareTo(b) < 0
End Function
''' <summary>
''' Determines if a is greater than b
''' </summary>
''' <param name="a">generic type to test</param>
''' <param name="b">generic type to test</param>
''' <returns>true|false</returns>
Private Shared Function GreaterThan(a As T, b As T) As Boolean
Return a.CompareTo(b) > 0
End Function
End Class
End Namespace