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)
39 # var tree = new BinTreeMap[Int, String]
41 # assert tree.min == "n1"
42 class BinTreeMap[K
: Comparable, E
]
45 redef type N
: BinTreeNode[K
, E
]
47 # Get the node value associated to `key`
48 # O(n) in worst case, average is O(h) with h: tree height
50 # var tree = new BinTreeMap[Int, String]
51 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
52 # assert tree[1] == "n1"
53 redef fun [](key
: K
): E
do
54 assert not_empty
: root
!= null
55 var res
= search_down
(root
.as(not null), key
)
56 assert has_key
: res
!= null
60 protected fun search_down
(from
: N
, key
: K
): nullable N
do
61 if key
== from
.key
then return from
62 if from
.left
!= null and key
< from
.key
then
63 return search_down
(from
.left
.as(not null), key
)
64 else if from
.right
!= null then
65 return search_down
(from
.right
.as(not null), key
)
70 # Get the node with the minimum key
71 # O(n) in worst case, average is O(h) with h: tree height
73 # var tree = new BinTreeMap[Int, String]
74 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
75 # assert tree.min == "n1"
77 assert not_empty
: root
!= null
78 return min_from
(root
.as(not null)).value
81 protected fun min_from
(node
: N
): N
do
82 if node
.left
== null then return node
83 return min_from
(node
.left
.as(not null))
86 # Get the node with the maximum key
87 # O(n) in worst case, average is O(h) with h: tree height
89 # var tree = new BinTreeMap[Int, String]
90 # for i in [4, 2, 1, 5, 3, 6, 7, 8] do tree[i] = "n{i}"
91 # assert tree.max == "n8"
93 assert not_empty
: root
!= null
94 return max_from
(root
.as(not null)).value
97 protected fun max_from
(node
: N
): N
do
98 if node
.right
== null then return node
99 return max_from
(node
.right
.as(not null))
102 # Insert a new node in tree using `key` and `item`
103 # O(n) in worst case, average is O(h) with h: tree height
105 # var tree = new BinTreeMap[Int, String]
107 # assert tree.max == "n1"
109 # assert tree.max == "n3"
110 redef fun []=(key
, item
) do
111 insert_node
(new BinTreeNode[K
, E
](key
, item
))
114 protected fun insert_node
(node
: N
) do
118 shift_down
(root
.as(not null), node
)
122 # Push down the `node` in tree from a specified `from` index
123 protected fun shift_down
(from
, node
: N
) do
124 if node
.key
< from
.key
then
125 if from
.left
== null then
129 shift_down
(from
.left
.as(not null), node
)
131 else if node
.key
> from
.key
then
132 if from
.right
== null then
136 shift_down
(from
.right
.as(not null), node
)
141 # Delete node at `key` (also return the deleted node value)
142 # O(n) in worst case, average is O(h) with h: tree height
144 # var tree = new BinTreeMap[Int, String]
146 # assert tree.max == "n1"
148 # assert tree.max == "n3"
150 # assert tree.max == "n1"
151 fun delete
(key
: K
): nullable E
do
152 assert is_empty
: root
!= null
153 var node
= search_down
(root
.as(not null), key
)
154 if node
== null then return null
155 if node
.left
== null then
156 transplant
(node
, node
.right
)
157 else if node
.right
== null then
158 transplant
(node
, node
.left
)
160 var min
= min_from
(node
.right
.as(not null))
161 if min
.parent
!= node
then
162 transplant
(min
, min
.right
)
163 min
.right
= node
.right
164 min
.right
.parent
= min
166 transplant
(node
, min
)
168 min
.left
.parent
= min
173 # Swap a `node` with the `other` in this Tree
174 # note: Nodes parents are updated, children still untouched
175 protected fun transplant
(node
, other
: nullable N
) do
176 if node
== null then return
177 if node
.parent
== null then
179 else if node
== node
.parent
.left
then
180 node
.parent
.left
= other
182 node
.parent
.right
= other
184 if other
!= null then other
.parent
= node
.parent
187 # Perform left rotation on `node`
195 protected fun rotate_left
(node
: N
) do
198 if y
.left
!= null then
201 y
.parent
= node
.parent
202 if node
.parent
== null then
204 else if node
== node
.parent
.left
then
207 node
.parent
.right
= y
213 # Perform right rotation on `node`
221 protected fun rotate_right
(node
: N
) do
224 if y
.right
!= null then
225 y
.right
.parent
= node
227 y
.parent
= node
.parent
228 if node
.parent
== null then
230 else if node
== node
.parent
.right
then
231 node
.parent
.right
= y
239 # Sort the tree into an array
242 # var tree = new BinTreeMap[Int, String]
243 # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
244 # assert tree.sort == ["n1", "n2", "n3", "n4", "n5"]
245 fun sort
: Array[E
] do
246 var sorted
= new Array[E
]
247 if root
== null then return sorted
248 sort_down
(root
.as(not null), sorted
)
252 protected fun sort_down
(node
: N
, sorted
: Array[E
]) do
253 if node
.left
!= null then sort_down
(node
.left
.as(not null), sorted
)
254 sorted
.add
(node
.value
)
255 if node
.right
!= null then sort_down
(node
.right
.as(not null), sorted
)
260 if root
== null then return "[]"
261 return "[{print_tree(root)}]"
264 protected fun print_tree
(node
: N
): String do
265 var s
= new FlatBuffer
267 if node
.left
!= null then s
.append
(print_tree
(node
.left
.as(not null)))
268 if node
.right
!= null then s
.append
(print_tree
(node
.right
.as(not null)))
272 redef fun show_dot
do
273 assert not_empty
: root
!= null
274 var f
= new OProcess("dot", "-Txlib")
275 f
.write
"digraph \{\n"
276 dot_down
(root
.as(not null), f
)
281 protected fun dot_down
(node
: N
, f
: OProcess) do
282 if node
.left
!= null then dot_down
(node
.left
.as(not null), f
)
284 if node
.right
!= null then dot_down
(node
.right
.as(not null), f
)
288 # TreeNode used by BinTree
289 class BinTreeNode[K
: Comparable, E
]
292 redef type SELF: BinTreeNode[K
, E
]
294 init(key
: K
, item
: E
) do
298 private var left_node
: nullable SELF = null
300 # `left` tree node child (null if node has no left child)
301 fun left
: nullable SELF do return left_node
303 # set `left` child for this node (or null if left no child)
304 # ENSURE: node.key < key (only if node != null)
305 fun left
=(node
: nullable SELF) do
306 assert node
!= null implies node
.key
< key
310 private var right_node
: nullable SELF = null
312 # `right` tree node child (null if node has no right child)
313 fun right
: nullable SELF do return right_node
315 # set `right` child for this node (or null if right no child)
316 # ENSURE: node.key < key (only if node != null)
317 fun right
=(node
: nullable SELF) do
319 assert node
.key
> key
324 # `parent` of the `parent` of this node (null if root)
325 fun grandparent
: nullable SELF do
326 if parent
== null then
333 # Other child of the `grandparent`
334 # `left` or `right` depends on the position of the current node against its parent
335 fun uncle
: nullable SELF do
340 if parent
== g
.left
then
348 # Other child of the parent
349 # `left` or `right` depends on the position of the current node against its parent
350 fun sibling
: nullable SELF do
351 if parent
== null then
353 else if self == parent
.left
then
355 else if self == parent
.right
then
362 redef fun to_s
do return "\{{key}: {value}\}"