1 | #Region "Microsoft.VisualBasic::6abf7be1188e9cce30e4aa8d6f07be60, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\BinaryTree\NaiveBinaryTree.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 NaiveBinaryTree |
35 | ' |
36 | ' Properties: Length |
37 | ' |
38 | ' Constructor: (+2 Overloads) Sub New |
39 | ' |
40 | ' Function: add, drawNode, findSuccessor, FindSymbol, insert |
41 | ' ToString |
42 | ' |
43 | ' Sub: clear, delete, KillTree |
44 | ' |
45 | ' |
46 | ' /********************************************************************************/ |
47 | |
48 | #End Region |
49 | |
50 | Imports System.Runtime.CompilerServices |
51 | |
52 | ' Software License Agreement (BSD License) |
53 | '* |
54 | '* Copyright (c) 2003, Herbert M Sauro |
55 | '* All rights reserved. |
56 | '* |
57 | '* Redistribution and use in source and binary forms, with or without |
58 | '* modification, are permitted provided that the following conditions are met: |
59 | '* * Redistributions of source code must retain the above copyright |
60 | '* notice, this list of conditions and the following disclaimer. |
61 | '* * Redistributions in binary form must reproduce the above copyright |
62 | '* notice, this list of conditions and the following disclaimer in the |
63 | '* documentation and/or other materials provided with the distribution. |
64 | '* * Neither the name of Herbert M Sauro nor the |
65 | '* names of its contributors may be used to endorse or promote products |
66 | '* derived from this software without specific prior written permission. |
67 | '* |
68 | '* THIS SOFTWARE IS PROVIDED BY <copyright holder> ``AS IS'' AND ANY |
69 | '* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
70 | '* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
71 | '* DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY |
72 | '* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
73 | '* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
74 | '* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
75 | '* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
76 | '* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
77 | '* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
78 | ' |
79 | |
80 | Namespace ComponentModel.Algorithm.BinaryTree |
81 | |
82 | ''' <summary> |
83 | ''' The Binary tree itself. 朴素二叉树 |
84 | ''' |
85 | ''' A very basic Binary Search Tree. Not generalized, stores |
86 | ''' name/value pairs in the tree nodes. name is the node key. |
87 | ''' The advantage of a binary tree is its fast insert and lookup |
88 | ''' characteristics. This version does not deal with tree balancing. |
89 | ''' (二叉搜索树,用于建立对repository的索引文件) |
90 | ''' </summary> |
91 | ''' <remarks></remarks> |
92 | Public Class NaiveBinaryTree(Of K, V) : Inherits TreeBase(Of K, V) |
93 | |
94 | ''' <summary> |
95 | ''' Returns the number of nodes in the tree |
96 | ''' </summary> |
97 | ''' <returns>Number of nodes in the tree</returns> |
98 | Public ReadOnly Property Length As Integer |
99 | <MethodImpl(MethodImplOptions.AggressiveInlining)> |
100 | Get |
101 | Return stack.Count |
102 | End Get |
103 | End Property |
104 | |
105 | Public Sub New(key As K, value As V, compares As Comparison(Of K), Optional views As Func(Of K, String) = Nothing) |
106 | Call MyBase.New(compares, views) |
107 | Call Me.insert(key, value) |
108 | End Sub |
109 | |
110 | Public Sub New(compares As Comparison(Of K), Optional views As Func(Of K, String) = Nothing) |
111 | MyBase.New(compares, views) |
112 | End Sub |
113 | |
114 | ' Recursive destruction of binary search tree, called by method clear |
115 | ' and destroy. Can be used to kill a sub-tree of a larger tree. |
116 | ' This is a hanger on from its Delphi origins, it might be dispensable |
117 | ' given the garbage collection abilities of .NET |
118 | Private Sub KillTree(ByRef p As BinaryTree(Of K, V)) |
119 | If p IsNot Nothing Then |
120 | KillTree(p.Left) |
121 | KillTree(p.Right) |
122 | p = Nothing |
123 | End If |
124 | End Sub |
125 | |
126 | ''' <summary> |
127 | ''' Clear the binary tree. |
128 | ''' </summary> |
129 | Public Sub clear() |
130 | Call KillTree(root) |
131 | Call stack.Clear() |
132 | End Sub |
133 | |
134 | ''' <summary> |
135 | ''' Find name in tree. Return a reference to the node |
136 | ''' if symbol found else return null to indicate failure. |
137 | ''' </summary> |
138 | ''' <param name="key">Name of node to locate</param> |
139 | ''' <returns>Returns null if it fails to find the node, else returns reference to node</returns> |
140 | Public Function FindSymbol(key As K, Optional ByRef parent As BinaryTree(Of K, V) = Nothing) As BinaryTree(Of K, V) |
141 | Dim np As BinaryTree(Of K, V) = root |
142 | Dim cmp As Integer |
143 | |
144 | parent = Nothing |
145 | |
146 | While np IsNot Nothing |
147 | cmp = compares(key, np.Key) |
148 | |
149 | If cmp = 0 Then |
150 | ' found ! |
151 | Return np |
152 | Else |
153 | parent = np |
154 | End If |
155 | |
156 | If cmp < 0 Then |
157 | np = np.Left |
158 | Else |
159 | np = np.Right |
160 | End If |
161 | End While |
162 | |
163 | ' Return null to indicate failure to find name |
164 | Return Nothing |
165 | End Function |
166 | |
167 | ''' <summary> |
168 | ''' Recursively locates an empty slot in the binary tree and inserts the node |
169 | ''' </summary> |
170 | ''' <param name="node"></param> |
171 | ''' <param name="tree"></param> |
172 | ''' <returns> |
173 | ''' 当处于append模式下,append值的时候不会返回节点,而是返回nothing |
174 | ''' </returns> |
175 | Private Function add(node As BinaryTree(Of K, V), ByRef tree As BinaryTree(Of K, V), append As Boolean) As BinaryTree(Of K, V) |
176 | Do While True |
177 | ' If we find a node with the same name then it's |
178 | ' a duplicate and we can't continue |
179 | Dim comparison As Integer = compares(node.Key, tree.Key) |
180 | |
181 | If comparison = 0 Then |
182 | ' Duplicated node was found! |
183 | If append Then |
184 | ' clustering |
185 | DirectCast(tree!values, List(Of V)).Add(node.Value) |
186 | Return Nothing |
187 | Else |
188 | ' Value replace when not append |
189 | tree.Value = node.Value |
190 | Return node |
191 | End If |
192 | ElseIf comparison < 0 Then |
193 | If Not tree.Left Is Nothing Then |
194 | tree = tree.Left |
195 | Else |
196 | tree.Left = node |
197 | Return node |
198 | End If |
199 | Else |
200 | If Not tree.Right Is Nothing Then |
201 | tree = tree.Right |
202 | Else |
203 | tree.Right = node |
204 | Return node |
205 | End If |
206 | End If |
207 | Loop |
208 | |
209 | Throw New NotImplementedException("This exception will never happends!") |
210 | End Function |
211 | |
212 | ''' <summary> |
213 | ''' Add a symbol to the tree if it's a new one. Returns reference to the new |
214 | ''' node if a new node inserted, else returns null to indicate node already present. |
215 | ''' </summary> |
216 | ''' <returns> Returns reference to the new node is the node was inserted. |
217 | ''' If a duplicate node (same name was located then returns null</returns> |
218 | Public Function insert(key As K, obj As V, Optional append As Boolean = True) As BinaryTree(Of K, V) |
219 | Dim node As New BinaryTree(Of K, V)(key, obj, toString:=views) |
220 | |
221 | Try |
222 | If root Is Nothing Then |
223 | _root = node |
224 | Else |
225 | node = add(node, root, append) |
226 | End If |
227 | |
228 | If Not node Is Nothing Then |
229 | Call stack.Add(node) |
230 | End If |
231 | |
232 | Return node |
233 | Catch generatedExceptionName As Exception |
234 | Dim ex = New Exception(node.ToString, generatedExceptionName) |
235 | Return App.LogException(ex) |
236 | End Try |
237 | End Function |
238 | |
239 | ''' <summary> |
240 | ''' Find the next ordinal node starting at node startNode. |
241 | ''' Due to the structure of a binary search tree, the |
242 | ''' successor node is simply the left most node on the right branch. |
243 | ''' </summary> |
244 | ''' <param name="startNode">Name key to use for searching</param> |
245 | ''' <param name="parent">Returns the parent node if search successful</param> |
246 | ''' <returns>Returns a reference to the node if successful, else null</returns> |
247 | Public Function findSuccessor(startNode As BinaryTree(Of K, V), ByRef parent As BinaryTree(Of K, V)) As BinaryTree(Of K, V) |
248 | parent = startNode |
249 | ' Look for the left-most node on the right side |
250 | startNode = startNode.Right |
251 | While startNode.Left IsNot Nothing |
252 | parent = startNode |
253 | startNode = startNode.Left |
254 | End While |
255 | Return startNode |
256 | End Function |
257 | |
258 | ''' <summary> |
259 | ''' Delete a given node. This is the more complex method in the binary search |
260 | ''' class. The method considers three senarios, 1) the deleted node has no |
261 | ''' children; 2) the deleted node as one child; 3) the deleted node has two |
262 | ''' children. Case one and two are relatively simple to handle, the only |
263 | ''' unusual considerations are when the node is the root node. Case 3) is |
264 | ''' much more complicated. It requires the location of the successor node. |
265 | ''' The node to be deleted is then replaced by the sucessor node and the |
266 | ''' successor node itself deleted. Throws an exception if the method fails |
267 | ''' to locate the node for deletion. |
268 | ''' </summary> |
269 | ''' <param name="key">Name key of node to delete</param> |
270 | Public Sub delete(key As K) |
271 | Dim parent As BinaryTree(Of K, V) = Nothing |
272 | ' First find the node to delete and its parent |
273 | Dim nodeToDelete As BinaryTree(Of K, V) = FindSymbol(key, parent) |
274 | |
275 | If nodeToDelete Is Nothing Then |
276 | Throw New Exception("Unable to delete node: " & key.ToString()) |
277 | End If |
278 | ' can't find node, then say so |
279 | ' Three cases to consider, leaf, one child, two children |
280 | |
281 | ' If it is a simple leaf then just null what the parent is pointing to |
282 | If (nodeToDelete.Left Is Nothing) AndAlso (nodeToDelete.Right Is Nothing) Then |
283 | If parent Is Nothing Then |
284 | _root = Nothing |
285 | Return |
286 | End If |
287 | |
288 | ' find out whether left or right is associated |
289 | ' with the parent and null as appropriate |
290 | If parent.Left Is nodeToDelete Then |
291 | parent.Left = Nothing |
292 | Else |
293 | parent.Right = Nothing |
294 | End If |
295 | |
296 | Call stack.Remove(nodeToDelete) |
297 | |
298 | Return |
299 | End If |
300 | |
301 | ' One of the children is null, in this case |
302 | ' delete the node and move child up |
303 | If nodeToDelete.Left Is Nothing Then |
304 | ' Special case if we're at the root |
305 | If parent Is Nothing Then |
306 | _root = nodeToDelete.Right |
307 | Return |
308 | End If |
309 | |
310 | ' Identify the child and point the parent at the child |
311 | If parent.Left Is nodeToDelete Then |
312 | parent.Right = nodeToDelete.Right |
313 | Else |
314 | parent.Left = nodeToDelete.Right |
315 | End If |
316 | nodeToDelete = Nothing |
317 | ' Clean up the deleted node |
318 | Call stack.Remove(nodeToDelete) |
319 | |
320 | Return |
321 | End If |
322 | |
323 | ' One of the children is null, in this case |
324 | ' delete the node and move child up |
325 | If nodeToDelete.Right Is Nothing Then |
326 | ' Special case if we're at the root |
327 | If parent Is Nothing Then |
328 | _root = nodeToDelete.Left |
329 | Return |
330 | End If |
331 | |
332 | ' Identify the child and point the parent at the child |
333 | If parent.Left Is nodeToDelete Then |
334 | parent.Left = nodeToDelete.Left |
335 | Else |
336 | parent.Right = nodeToDelete.Left |
337 | End If |
338 | nodeToDelete = Nothing |
339 | ' Clean up the deleted node |
340 | Call stack.Remove(nodeToDelete) |
341 | |
342 | Return |
343 | End If |
344 | |
345 | ' Both children have nodes, therefore find the successor, |
346 | ' replace deleted node with successor and remove successor |
347 | ' The parent argument becomes the parent of the successor |
348 | Dim successor As BinaryTree(Of K, V) = findSuccessor(nodeToDelete, parent) |
349 | ' Make a copy of the successor node |
350 | Dim tmp As New BinaryTree(Of K, V)(successor.Key, successor.Value) |
351 | ' Find out which side the successor parent is pointing to the |
352 | ' successor and remove the successor |
353 | If parent.Left Is successor Then |
354 | parent.Left = Nothing |
355 | Else |
356 | parent.Right = Nothing |
357 | End If |
358 | |
359 | ' Copy over the successor values to the deleted node position |
360 | Call nodeToDelete.Copy(tmp) |
361 | Call stack.Remove(nodeToDelete) |
362 | End Sub |
363 | |
364 | ' Simple 'drawing' routines |
365 | Private Function drawNode(node As BinaryTree(Of K, V)) As String |
366 | If node Is Nothing Then |
367 | Return "empty" |
368 | End If |
369 | |
370 | If (node.Left Is Nothing) AndAlso (node.Right Is Nothing) Then |
371 | Return views(node.Key) |
372 | End If |
373 | If (node.Left IsNot Nothing) AndAlso (node.Right Is Nothing) Then |
374 | Return views(node.Key) & "(" & drawNode(node.Left) & ", _)" |
375 | End If |
376 | |
377 | If (node.Right IsNot Nothing) AndAlso (node.Left Is Nothing) Then |
378 | Return views(node.Key) & "(_, " & drawNode(node.Right) & ")" |
379 | End If |
380 | |
381 | Return views(node.Key) & "(" & drawNode(node.Left) & ", " & drawNode(node.Right) & ")" |
382 | End Function |
383 | |
384 | ''' <summary> |
385 | ''' Return the tree depicted as a simple string, useful for debugging, eg |
386 | ''' 50(40(30(20, 35), 45(44, 46)), 60) |
387 | ''' </summary> |
388 | ''' <returns>Returns the tree</returns> |
389 | Public Overrides Function ToString() As String |
390 | Return drawNode(root) |
391 | End Function |
392 | End Class |
393 | End Namespace |