-
Notifications
You must be signed in to change notification settings - Fork 17
/
Copy pathy-BST.txt
291 lines (224 loc) · 12.2 KB
/
y-BST.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
From: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/binarySearchTree.htm
Index: http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html
19
11 35
7 16 23
13 17
Binary Search Tree/ BST
binary_search_tree property.
for each, internal node, say node
any node's key in node's left sub tree is <= node
any node's key in node's right sub tree is >= node
left subtree < node
right subtree > node
19
11 35
7 16 23
13 17
NOTE:
in actual, <= and >= cannot exists same time.
so, one among below exists:
<= and >
OR
< and >=
OR
< and >
height =
number of links from root to deepest node
operations depend on height of tree
case worst-case time
complete binary tree O(log N)
linear-chain tree O(N)
node can have a
element (also called info, it will include either key/value)
and 3 pointer fields
left
right
parent
parent is NULL for root
left & right are NULL for leafs
Walk
//
// while the current node is not NULL, walk current node's left, then visit current node, then walk current node's right
//
inorder_walk (current_node)
if current_node is NOT NULL:
inorder_walk (current_node's left)
access current_node's key
inorder_walk (current_node's right)
//
// call: inorder_walk(root)
// all nodes will be walked so it's O(N)
// the order is: (left-subtree)current_node(right-subtree)
// if printed, will be ascending order
//
//
// while the current node is not NULL, visit current node, then walk current node's left, then walk current node's right
//
preorder_walk (current_node)
if current_node is NOT NULL:
access current_node's key
preorder_walk (current_node's left)
preorder_walk (current_node's right)
//
// call: preorder_walk(root)
// all nodes will be walked so it's O(N)
// the order is: current_node(left-subtree)(right-subtree)
//
//
// while the current node is not NULL, walk current node's left, then walk current node's right, then visit current node
//
postorder_walk (current_node)
if current_node is NOT NULL:
postorder_walk (current_node's left)
postorder_walk (current_node's right)
access current_node's key
//
// call: postorder_walk(root)
// all nodes will be walked so it's O(N)
// the order is: (left-subtree)(right-subtree)current_node
//
Querying a Binary Search Tree
MINIMUM, MAXIMUM, SUCCESSOR and PREDESESSOR
O(h)
h is height of the tree i.e., the number of links root node to the deepest node.
// depending on the the given key to find, traverse down
// traverse down to left, if key is < current node
// traverse down to right, if key is > current node
// else return node, that is, if key is = current node
bst_tree_search (current_node, key)
if current_node is NULL
return current_node
if key == current_node's key:
return current_node
if key < current_node's key:
return bst_tree_search (current_node's left, key)
else
return bst_tree_search (current_node's right, key)
bst_tree_search_iterative (current_node, key)
while current_node != NULL AND key < current_node's key
current_node = current_node's left
while current_node != NULL AND key > current_node's key
current_node = current_node's right
if current_node == NULL:
return current_node
if key == current_node's key:
return current_node
// To get the minimum, go down to the left most element of the tree
// does not look at key
bst_tree_minimum (current_node)
if current_node == NULL:
return current_node
while current_node's left != NULL
current_node = current_node's left
return current_node
// To get the maximum, go down to the right most element of the tree
// does not look at key
bst_tree_maximum (current_node)
if current_node == NULL:
return current_node
while current_node's right != NULL
current_node = current_node's right
return current_node
// find node with key just > current_node's key
// it is either
// minimum element of the right child's subtree, if right child exists
// or
// you go up from the node, until a node's parent's right child is not the node itself.
// does not look at key
bst_tree_successor (current_node)
if current_node's right != NULL
return bst_tree_minimum (current_node's right)
// ** redundant **
// if current_node's parent != NULL AND current_node's parent's key > current_node's key // looks fine but we shudn't look at keys
if current_node's parent != NULL AND current_node's parent's left == current_node
return current_node's parent
// while current_node's parent != NULL AND current_node's parent < current_node's key // looks fine but we shudn't look at keys
while current_node's parent != NULL AND current_node's parent's right == current_node
current_node = current_node's parent
// current_node's parent's right is now NULL or other
return current_node's parent
NOTE:
An inorder tree walk of an n-node BST
can be implemented in O(n)-time
by finding the minimum element in the tree with bst_tree_minimum(x) algorithm and
then making n-1 calls to bst_tree_successor (x).
// find node with key just < current_node's key
// it is either
// maximum element of the left child's subtree, if left child exists
// or
// you go up from the node, until a node's parent's left child is not the node itself.
// does not look at key
bst_tree_predecessor (current_node)
if current_node's left != NULL
return bst_tree_maximum (current_node's left)
// ** redundant **
// if current_node's parent != NULL AND current_node's parent's key < current_node's key // looks fine but we shudn't look at keys
if current_node's parent != NULL AND current_node's parent's right == current_node
return current_node's parent
// while current_node's parent != NULL AND current_node's parent > current_node's key // looks fine but we shudn't look at keys
while current_node's parent != NULL AND current_node's parent's left == current_node
current_node = current_node's parent
// current_node's parent's left is now NULL or other
return current_node's parent
// go to leaf, add it
bst_tree_insert (current_node, node_to_insert)
if current_node == NULL
current_node = node_to_insert
return
while current_node != NULL
current_node_parent = current_node
if node_to_insert's key < current_node's key
current_node = current_node's left
else
current_node = current_node's right
if node_to_insert's key < current_node_parent's key
current_node_parent's left = node_to_insert
else
current_node_parent's right = node_to_insert
// =====
// if the 1st element to insert is either smallest or biggest or near to them, the tree will be nearly single chain of node
// in which case the build will take O(N^2), i.e. O(N) for each of the N elements, in actually 1,2,3...N insertion cost which is n(n+1)/2 => O(N^2)
// else best case blanced tree, root is in the one of mid value(s) in sorted order, build will take O(N logN), i.e. log N for each of the N elements
// =====
// build bst tree from array
// inorder_walk the bst tree, to print in ascending sorted order
bst_tree_print_ascending_order_sort (array)
current_node = NULL
// create tree
for each element in array:
if 1st element of array:
current_node = bst_tree_create_single_node(element);
else:
node_to_insert = bst_tree_create_single_node(element);
bst_tree_insert(current_node, node_to_insert)
// print inorder
inorder_walk (current_node)
// =====
// if the 1st element to insert is either smallest or biggest or near to them, the tree will be nearly single chain of node
// in which case the build will take O(N^2), i.e. O(N) for each of the N elements, in actually 1,2,3...N insertion cost which is n(n+1)/2 => O(N^2)
// else best case blanced tree, root is in the one of mid value(s) in sorted order, build will take O(N logN), i.e. log N for each of the N elements
// =====
/* LOOKS CORRECT, NEEDS VERFICATION */
// case 1: if node_to_delete has no children, then delete node_to_delete
// case 2: if node_to_delete has one child, link the node_to_delete's child to node_to_delete's parent, delete node_to_delete
// case 2: if node_to_delete has two children, find successor of node_to_delete using current_node
// copy the successor's value to node_to_delete, then delete successor node
bst_tree_delete (current_node, node_to_delete)
// cover both NULL
if node_to_delete's right == NULL
if node_to_delete's parent's left == node_to_delete
node_to_delete's parent's left = node_to_delete's left
else // if node_to_delete's parent's right == node_to_delete
node_to_delete's parent's right = node_to_delete's left
return
if node_to_delete's left == NULL
if node_to_delete's parent's left == node_to_delete
node_to_delete's parent's left = node_to_delete's right
else // if node_to_delete's parent's right == node_to_delete
node_to_delete's parent's right = node_to_delete's right
return
successor_node = bst_tree_successor (node_to_delete)
node_to_delete's key = successor_node's key
delete successor_node
return