1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Binary Tree data-structure
16 # A binary tree is a tree data structure in which each node has at most two children
17 # (referred to as the left child and the right child).
18 # In a binary tree, the degree of each node can be at most two.
19 # Binary trees are used to implement binary search trees and binary heaps,
20 # and are used for efficient searching and sorting.
29 # * node.left.key < node.key
30 # * node.right.key > node.key
31 # * no duplicates allowed
34 # * search average O(lg n) worst O(n)
35 # * insert average O(lg n) worst O(n)
36 # * delete average O(lg n) worst O(n)
40 # var tree = new BinTreeMap[Int, String]
42 # assert tree.min == "n1"
43 class BinTreeMap[K
: Comparable, E
]
46 redef type N
: BinTreeNode[K
, E
]
49 private var first_node
: nullable BinTreeNode[K
, E
] = null
50 private var last_node
: nullable BinTreeNode[K
, E
] = null
52 # O(n) in worst case, average is O(h) with h: tree height
54 # var tree = new BinTreeMap[Int, String]
55 # assert tree.is_empty
57 # assert not tree.is_empty
58 redef fun is_empty
do return root
== null
60 # O(n) in worst case, average is O(h) with h: tree height
62 # var tree = new BinTreeMap[Int, String]
63 # assert not tree.has_key(1)
64 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
65 # assert not tree.has_key(0)
66 # assert tree.has_key(2)
67 # assert not tree.has_key(6)
68 redef fun has_key
(key
) do
69 if is_empty
then return false
70 var res
= search_down
(root
.as(not null), key
)
78 private var cache_node
: nullable N
= null
80 # Get the node value associated to `key`
81 # O(n) in worst case, average is O(h) with h: tree height
83 # var tree = new BinTreeMap[Int, String]
84 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
85 # assert tree.has_key(1)
86 # assert tree[1] == "n1"
87 # assert tree.has_key(1)
88 # assert tree[2] == "n2"
90 assert not_empty
: not is_empty
91 if cache_node
!= null and cache_node
.key
== key
then return cache_node
.value
92 var res
= search_down
(root
.as(not null), key
)
93 assert has_key
: res
!= null
97 # Search `key` in `from` and its children nodes.
98 protected fun search_down
(from
: N
, key
: nullable Object): nullable N
do
99 if not key
isa Comparable then return null
100 var cmp
= key
<=> from
.key
101 if cmp
== 0 then return from
102 if from
.left
!= null and cmp
< 0 then
103 return search_down
(from
.left
.as(not null), key
)
104 else if from
.right
!= null then
105 return search_down
(from
.right
.as(not null), key
)
110 # Get the node with the minimum key
111 # O(n) in worst case, average is O(h) with h: tree height
113 # var tree = new BinTreeMap[Int, String]
114 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
115 # assert tree.min == "n1"
117 assert not_empty
: root
!= null
118 return min_from
(root
.as(not null)).value
121 # Get the left-most child from `node`.
122 protected fun min_from
(node
: N
): N
do
123 if node
.left
== null then return node
124 return min_from
(node
.left
.as(not null))
127 # Get the node with the maximum key
128 # O(n) in worst case, average is O(h) with h: tree height
130 # var tree = new BinTreeMap[Int, String]
131 # for i in [4, 2, 1, 5, 3, 6, 7, 8] do tree[i] = "n{i}"
132 # assert tree.max == "n8"
134 assert not_empty
: root
!= null
135 return max_from
(root
.as(not null)).value
138 # Get the right-most child from `node`.
139 protected fun max_from
(node
: N
): N
do
140 if node
.right
== null then return node
141 return max_from
(node
.right
.as(not null))
144 # Insert a new node in tree using `key` and `item`
145 # O(n) in worst case, average is O(h) with h: tree height
147 # var tree = new BinTreeMap[Int, String]
149 # assert tree.max == "n1"
151 # assert tree.max == "n3"
152 redef fun []=(key
, item
) do
153 insert_node
(new BinTreeNode[K
, E
](key
, item
))
156 # Add `node` in the tree.
157 protected fun insert_node
(node
: N
) do
162 shift_down
(root
.as(not null), node
)
164 if first_node
== null then
167 if last_node
!= null then
168 last_node
.next
= node
169 node
.prev
= last_node
174 # Push down the `node` in tree from a specified `from` index
175 protected fun shift_down
(from
, node
: N
) do
176 var cmp
= node
.key
<=> from
.key
178 if from
.left
== null then
182 shift_down
(from
.left
.as(not null), node
)
185 if from
.right
== null then
189 shift_down
(from
.right
.as(not null), node
)
194 # Delete node at `key` (also return the deleted node value)
195 # O(n) in worst case, average is O(h) with h: tree height
197 # var tree = new BinTreeMap[Int, String]
199 # assert tree.max == "n1"
201 # assert tree.max == "n3"
203 # assert tree.max == "n1"
204 fun delete
(key
: K
): nullable E
do
205 assert is_empty
: root
!= null
207 var node
= search_down
(root
.as(not null), key
)
208 if node
== null then return null
209 if node
.left
== null then
210 transplant
(node
, node
.right
)
211 else if node
.right
== null then
212 transplant
(node
, node
.left
)
214 var min
= min_from
(node
.right
.as(not null))
215 if min
.parent
!= node
then
216 transplant
(min
, min
.right
)
217 min
.right
= node
.right
218 min
.right
.parent
= min
220 transplant
(node
, min
)
222 min
.left
.parent
= min
224 if first_node
== node
then
227 if last_node
== node
then
228 last_node
= node
.prev
229 last_node
.next
= null
231 node
.prev
.next
= node
.next
232 node
.next
.prev
= node
.prev
237 # Swap a `node` with the `other` in this Tree
238 # note: Nodes parents are updated, children still untouched
239 protected fun transplant
(node
, other
: nullable N
) do
240 if node
== null then return
241 if node
.parent
== null then
243 else if node
== node
.parent
.left
then
244 node
.parent
.left
= other
246 node
.parent
.right
= other
248 if other
!= null then other
.parent
= node
.parent
251 # Perform left rotation on `node`
261 protected fun rotate_left
(node
: N
) do
264 if y
.left
!= null then
267 y
.parent
= node
.parent
268 if node
.parent
== null then
270 else if node
== node
.parent
.left
then
273 node
.parent
.right
= y
279 # Perform right rotation on `node`
289 protected fun rotate_right
(node
: N
) do
292 if y
.right
!= null then
293 y
.right
.parent
= node
295 y
.parent
= node
.parent
296 if node
.parent
== null then
298 else if node
== node
.parent
.right
then
299 node
.parent
.right
= y
307 # Sort the tree into an array
310 # var tree = new BinTreeMap[Int, String]
311 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
312 # assert tree.sort == ["n1", "n2", "n3", "n4", "n5"]
313 fun sort
: Array[E
] do
314 var sorted
= new Array[E
]
315 if root
== null then return sorted
316 sort_down
(root
.as(not null), sorted
)
320 # Sort the tree from `node` and place results in `sorted`.
321 protected fun sort_down
(node
: N
, sorted
: Array[E
]) do
322 if node
.left
!= null then sort_down
(node
.left
.as(not null), sorted
)
323 sorted
.add
(node
.value
)
324 if node
.right
!= null then sort_down
(node
.right
.as(not null), sorted
)
329 if root
== null then return "[]"
330 return "[{print_tree(root)}]"
333 # Print the tree starting from `node`.
334 protected fun print_tree
(node
: N
): String do
335 var s
= new FlatBuffer
337 if node
.left
!= null then s
.append
(print_tree
(node
.left
.as(not null)))
338 if node
.right
!= null then s
.append
(print_tree
(node
.right
.as(not null)))
342 redef fun show_dot
do
343 assert not_empty
: root
!= null
344 var f
= new ProcessWriter("dot", "-Txlib")
345 f
.write
"digraph \{\n"
346 dot_down
(root
.as(not null), f
)
351 # Translate the tree in dot format starting from `node`.
352 protected fun dot_down
(node
: N
, f
: ProcessWriter) do
353 if node
.left
!= null then dot_down
(node
.left
.as(not null), f
)
355 if node
.right
!= null then dot_down
(node
.right
.as(not null), f
)
360 # var tree = new BinTreeMap[Int, String]
361 # assert tree.length == 0
362 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
363 # assert tree.length == 5
364 redef fun length
do return len
366 # Nodes are iterated in the same order in which they were added to the tree.
369 # var tree = new BinTreeMap[Int, String]
370 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
371 # var keys = new Array[Int]
372 # for k, v in tree do
375 # assert keys == [4, 2, 1, 5, 3]
376 redef fun iterator
do return new BinTreeMapIterator[K
, E
](self)
379 # TreeNode used by BinTree
380 class BinTreeNode[K
: Comparable, E
]
383 private var prev
: nullable BinTreeNode[K
, E
] = null
384 private var next
: nullable BinTreeNode[K
, E
] = null
386 redef type N
: BinTreeNode[K
, E
]
388 private var left_node
: nullable N
= null
390 # `left` tree node child (null if node has no left child)
391 fun left
: nullable N
do return left_node
393 # set `left` child for this node (or null if left no child)
394 # ENSURE: node.key < key (only if node != null)
395 fun left
=(node
: nullable N
) do
396 #assert node != null implies node.key < key
400 private var right_node
: nullable N
= null
402 # `right` tree node child (null if node has no right child)
403 fun right
: nullable N
do return right_node
405 # set `right` child for this node (or null if right no child)
406 # ENSURE: node.key < key (only if node != null)
407 fun right
=(node
: nullable N
) do
408 #assert node != null implies node.key > key
412 # `parent` of the `parent` of this node (null if root)
413 fun grandparent
: nullable N
do
414 if parent
== null then
421 # Other child of the `grandparent`
422 # `left` or `right` depends on the position of the current node against its parent
423 fun uncle
: nullable N
do
428 if parent
== g
.left
then
436 # Other child of the parent
437 # `left` or `right` depends on the position of the current node against its parent
438 fun sibling
: nullable N
do
439 if parent
== null then
441 else if self == parent
.left
then
443 else if self == parent
.right
then
450 redef fun to_s
do return "\{{key}: {value or else ""}\}"
453 private class BinTreeMapIterator[K
: Comparable, E
]
454 super MapIterator[K
, E
]
456 var tree
: BinTreeMap[K
, E
]
457 var current
: nullable BinTreeNode[K
, E
] = null
459 init do current
= tree
.first_node
461 redef fun is_ok
do return not current
== null
462 redef fun next
do current
= current
.next
463 redef fun item
do return current
.value
464 redef fun key
do do return current
.key