1	#Region "Microsoft.VisualBasic::9d8242f71ef8d4ebc659b093346e8109, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\BinaryTree\AVLTree.vb"
2
3	' Author:
4	'
5	'       asuka (amethyst.asuka@gcmodeller.org)
6	'       xie (genetics@smrucc.org)
7	'       xieguigang (xie.guigang@live.com)
8	'
9	' Copyright (c) 2018 GPL3 Licensed
10	'
11	'
12	' GNU GENERAL PUBLIC LICENSE (GPL3)
13	'
14	'
15	' This program is free software: you can redistribute it and/or modify
16	' it under the terms of the GNU General Public License as published by
17	' the Free Software Foundation, either version 3 of the License, or
18	' (at your option) any later version.
19	'
20	' This program is distributed in the hope that it will be useful,
21	' but WITHOUT ANY WARRANTY; without even the implied warranty of
22	' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23	' GNU General Public License for more details.
24	'
25	' You should have received a copy of the GNU General Public License
26	' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30	' /********************************************************************************/
31
32	' Summaries:
33
34	'     Class AVLTree
35	'
36	'         Constructor: (+1 Overloads) Sub New
37	'
38	'         Function: Add, Remove
39	'
40	'         Sub: Add, appendLeft, appendRight, Remove, removeCurrent
41	'              removeLeft, removeRight
42	'
43	'
44	' /********************************************************************************/
45
46	#End Region
47
48	Imports System.Runtime.CompilerServices
49
50	Namespace ComponentModel.Algorithm.BinaryTree
51
52	''' <summary>
53	''' The AVL binary tree operator.
54	''' </summary>
55	''' <typeparam name="K"></typeparam>
56	''' <typeparam name="V"></typeparam>
57	''' <remarks>
58	''' http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html
59	''' </remarks>
60	Public Class AVLTree(Of K, V) : Inherits TreeBase(Of K, V)
61
62	''' <summary>
63	''' Create an instance of the AVL binary tree.
64	''' </summary>
65	''' <param name="compares">Compare between two keys.</param>
66	''' <param name="views">Display the key as string</param>
67	Sub New(compares As Comparison(Of K), Optional views As Func(Of K, String) = Nothing)
68	MyBase.New(compares, views)
69	End Sub
70
71	<MethodImpl(MethodImplOptions.AggressiveInlining)>
72	Public Sub Add(key As K, value As V, Optional valueReplace As Boolean = True)
73	_root = Add(key, value, _root, valueReplace)
74	End Sub
75
76	Public Function Add(key As K, value As V, tree As BinaryTree(Of K, V), valueReplace As Boolean) As BinaryTree(Of K, V)
77	If tree Is Nothing Then
78	' 追加新的叶子节点
79	tree = New BinaryTree(Of K, V)(key, value, Nothing, views)
80	stack.Add(tree)
81	End If
82
83	Select Case compares(key, tree.Key)
84	Case < 0 : Call appendLeft(tree, key, value, valueReplace)
85	Case > 0 : Call appendRight(tree, key, value, valueReplace)
86	Case = 0
87
88	' 将value追加到附加值中（也可对应重复元素）
89	If valueReplace Then
90	tree.Value = value
91	End If
92
93	' 2018.3.6
94	' 如果是需要使用二叉树进行聚类操作，那么等于零的值可能都是同一个簇之中的
95	' 在这里将这个member添加进来
96	Call DirectCast(tree!values, List(Of V)).Add(value)
97
98	Case Else
99	' This will never happend!
100	Throw New Exception("????")
101	End Select
102
103	tree.PutHeight
104
105	Return tree
106	End Function
107
108	Private Sub appendRight(ByRef tree As BinaryTree(Of K, V), key As K, value As V, replace As Boolean)
109	tree.Right = Add(key, value, tree.Right, replace)
110
111	If tree.Right.height - tree.Left.height = 2 Then
112	If compares(key, tree.Right.Key) > 0 Then
113	tree = tree.RotateRR
114	Else
115	tree = tree.RotateRL
116	End If
117	End If
118	End Sub
119
120	Private Sub appendLeft(ByRef tree As BinaryTree(Of K, V), key As K, value As V, replace As Boolean)
121	tree.Left = Add(key, value, tree.Left, replace)
122
123	If tree.Left.height - tree.Right.height = 2 Then
124	If compares(key, tree.Left.Key) < 0 Then
125	tree = tree.RotateLL
126	Else
127	tree = tree.RotateLR
128	End If
129	End If
130	End Sub
131
132	<MethodImpl(MethodImplOptions.AggressiveInlining)>
133	Public Sub Remove(key As K)
134	_root = Remove(key, _root)
135	End Sub
136
137	Public Function Remove(key As K, tree As BinaryTree(Of K, V)) As BinaryTree(Of K, V)
138	If tree Is Nothing Then
139	Return Nothing
140	End If
141
142	Select Case compares(key, tree.Key)
143	Case < 0 : Call removeLeft(tree, key)
144	Case > 0 : Call removeRight(tree, key)
145	Case = 0 : Call removeCurrent(tree)
146	Case Else
147	' This will never happed!
148	Throw New Exception("This will never happed!")
149	End Select
150
151	If Not tree Is Nothing Then
152	Call tree.PutHeight
153	End If
154
155	Return tree
156	End Function
157
158	Private Sub removeLeft(ByRef tree As BinaryTree(Of K, V), key As K)
159	tree.Left = Remove(key, tree.Left)
160
161	If tree.Left.height - tree.Right.height = 2 Then
162	If compares(key, tree.Left.Key) < 0 Then
163	tree = tree.RotateLL
164	Else
165	tree = tree.RotateLR
166	End If
167	End If
168	End Sub
169
170	Private Sub removeRight(ByRef tree As BinaryTree(Of K, V), key As K)
171	tree.Right = Remove(key, tree.Right)
172
173	If tree.Right.height - tree.Left.height = 2 Then
174	If compares(key, tree.Right.Key) > 0 Then
175	tree = tree.RotateRR
176	Else
177	tree = tree.RotateRL
178	End If
179	End If
180	End Sub
181
182	Private Sub removeCurrent(ByRef tree As BinaryTree(Of K, V))
183	If Not tree.Left Is Nothing AndAlso Not tree.Right Is Nothing Then
184
185	tree = New BinaryTree(Of K, V)(tree.Right.MinKey, tree.Value) With {
186	.Left = tree.Left,
187	.Right = tree.Right
188	}
189	tree.Right = Remove(tree.Key, tree.Right)
190
191	Else
192	tree = If(tree.Left Is Nothing, tree.Right, tree.Left)
193
194	If tree Is Nothing Then
195	tree = Nothing
196	End If
197	End If
198	End Sub
199	End Class
200	End Namespace