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 OverloadsSub 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 BooleanAs 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