-
Notifications
You must be signed in to change notification settings - Fork 54
/
Copy pathBinarySearchTrees.html
452 lines (413 loc) · 16 KB
/
BinarySearchTrees.html
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
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analysis of Algorithms: Binary Search Trees
</title>
</head>
<body>
<div id="header">
<div id="logo">
<img src="graphics/Julia.png">
</div>
<div id="user-tools">
<a href="index.html">Home</a>
<a href="about.html">About</a>
<a href="feedback.html">Feedback</a>
</div>
</div>
<h1>
Design and Analysis of Algorithms: Binary Search Trees
</h1>
<div style="text-align:center">
<p>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/200px-Binary_search_tree.svg.png">
</p>
</div>
<details>
<summary class="sum1">
12.1 What is a binary search tree?
</summary>
<details>
<summary class="sum2">
Binary Search Tree Property
</summary>
<p>
<i>
Let x be a node in a binary search tree. If y is a node in the
left subtree of x, then y.key ≤ x.key. If y is a node in the
right subtree of x, then y.key ≥ x.key.
</i>
</p>
<figure>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png">
<em>(Tree 1)</em>
</figure>
</details>
<details>
<summary class="sum2">
Inorder Tree Walk
</summary>
<pre>
<code>
Inorder-Tree-Walk(x)
if x != NIL
Inorder-Tree-Walk(x.left)
print x.key
Inorder-Tree-Walk(x.right)
</code>
</pre>
<p>
Compare with:
</p>
<pre>
<code>
Postorder-Tree-Walk(x)
if x != NIL
Postorder-Tree-Walk(x.left)
Postorder-Tree-Walk(x.right)
print x.key
</code>
</pre>
</details>
</details>
<details>
<summary class="sum1">
12.2 Querying a binary search tree
</summary>
<p>
Why do we pass in a node rather than the tree itself?
<br>
Note why CLRS pseudo-code for max and min contains mistake
from practical point of view.
<br>
Library code versus application code.
<br>
Library must protect itself against both malicious and merely
inept users. So, need to check for NIL input!
<br>
<br>
Recursive versus loop: compare the two searches.
<br>
<br>
All searching functions (search, minimum, maximum, predecessor,
successor) run in <em>O(h)</em> time,
where <em>h</em> is the height of the tree.
<br>
</p>
<details>
<summary class="sum2">
Search
</summary>
<p>
We search by starting with the root node.
If it's key is equal to the key for
which we are searching, we are done: that is the
key we want.
<br>
On the other hand, if we have a NIL node at hand,
we are also done, but have failed to find the key.
<br>
Finally, if neither is true, we check the key
at hand against the key sought for.
<ul>
<li>If k < curr.key, recursively call
tree search on curr.left.
</li>
<li>Else recursively call tree search on curr.right.
</li>
</ul>
</p>
<figure>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/200px-Binary_search_tree.svg.png">
<figcaption>
</figcaption>
</figure>
<p>
<br>
<b>Example:</b>
<br>Let's search for 4 in the tree above.
<ul>
<li>4 < 8; move left</li>
<li>4 > 3; move right</li>
<li>4 < 6; move left</li>
<li>Voila!</li>
</ul>
</p>
<details>
<summary class="sum3">
Running time
</summary>
<p>
<b>Worst case:</b> Θ(n)
<br>
This occurs when the tree simply makes one long chain.
<br>
<br>
<b>Average case:</b> Θ(lg n)
<br>
That is because the expected height of a
randomly built binary search tree is O(lg n).
</p>
</details>
</details>
<details>
<summary class="sum2">
Minimum and maximum
</summary>
<p>
To find the minimum, we simply walk down the left side of the tree.
<br>
To find the maximum, we simply walk down
the right side of the tree.
</p>
</details>
<details>
<summary class="sum2">
Successor
</summary>
<figure>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/200px-Binary_search_tree.svg.png">
<figcaption>
</figcaption>
</figure>
<p>
Let's walk through successor for our tree above.
<br>
<br>
Imagine we are seeking the successor
of 3. The right tree of three is non-empty. So we simply
seek the minimum of that tree,
which is the leftmost node in the tree, in this case, 4.
<br>
<br>
On the other hand, take this tree, and start with node 10.
</p>
<figure>
<img
src="graphics/BinTree1.png">
<figcaption>
Tree 2
</figcaption>
</figure>
<p>
<br>
10 has no right child, so its successor must lie further up
the tree. But it is the right hand node of its
parent, so its parent can't be it. However, at the
next move back a generation we move left... and
that's the successor!
</p>
</details>
</details>
<details>
<summary class="sum1">
12.3 Insertion and deletion
</summary>
<details>
<summary class="sum2">
Insert
</summary>
<p>
Let's walk through insert for tree 1 above.
<br>
<br>
We will insert 5. (When I say "Insert x," you should take that
to be shorthand for "Insert a node with key x.")
<ul>
<li>5 < 8, so we move left.</li>
<li>5 > 3, so we move right. </li>
<li>5 < 6, so we move left.</li>
<li>5 > 4, so we move right and insert. </li>
</ul>
</p>
</details>
<details>
<summary class="sum2">
Delete
</summary>
<p>
Deletion is by far the most complicated coding of any of these
functions. There are four cases (<i>z</i> is the node to delete):
</p>
<ol>
<li><i>z</i> has no left child. (This handles two cases!)
<br>
<b>Action:</b> Replace <i>z</i> by its right child,
which might be
NIL.
</li>
<li><i>z</i> has only a left child.
<br>
<b>Action:</b> Replace <i>z</i> by its left child.
</li>
<li><i>z</i> has two children.
<br>
<b>Action:</b> Find <i>z</i>'s successor y, which lies in its
right sub-tree.
<ul class="nested">
<li>If <i>y</i> is <i>z</i>'s right child, replace
<i>z</i> by <i>y</i>.
</li>
<li>Otherwise, replace <i>y</i> by its own
right child, then replace <i>z</i> by <i>y</i>.
</li>
</ul>
</li>
</ol>
<details>
<summary class="sum3">
Walk through of delete
</summary>
<figure>
<img src="graphics/BinTree1.png">
<figcaption>
</figcaption>
</figure>
<p>
Let's walk through deleting 8 in the tree above.
</p>
<ul>
<li>8 has two children, so we are in case 4.</li>
<li>The successor of 8 is 9.</li>
<li>9 is not the right child of 8.</li>
<li>So we replace 9 by 10.</li>
<li>Then we replace 8 by 9.</li>
</ul>
<p>
The right half of tree 2 now looks like this:
<br>
<br>
<img
src="graphics/BinTree2.png">
</p>
</details>
</details>
</details>
<details>
<summary class="sum1">
12.4 Randomly built binary search trees
</summary>
<p>
We insert the keys randomly. (We would have to have all keys at
hand at the start, and then do a random shuffle on the set of
keys.) The expected height of such a tree is O(lg n).
<br>
<br>
This handles the situation where we believe we might get handed
input that is already sorted, which would create a worst-case
scenario.
</p>
</details>
<details>
<summary class="sum1">
Run the Python code
</summary>
<p>
In the console below, type or paste:
<br />
<code>
!git clone
https://gist.github.com/gcallah/f0d36f8c107e6c1e888d58aefcb3a5aa
<br />
cd f0d36f8c107e6c1e888d58aefcb3a5aa
<br />
from binary_search_trees import *
<br />
</code>
</p>
<div class="python-console">
<iframe style="width: 640; height: 480;"
name="embedded_python_anywhere"
src="https://www.pythonanywhere.com/embedded3/" scrolling="yes">
</iframe>
<figcaption>
Python console
</figcaption>
</div>
</details>
<details>
<summary class="sum1">
Source Code
</summary>
<p>
<a href="https://github.com/gcallah/algorithms/tree/master/Java/BinarySearchTrees">Java</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Ruby/BinarySearchTrees">Ruby</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Python/BinarySearchTrees">Python</a><br>
</p>
</details>
<details>
<summary class="sum1">
For Further Study
</summary>
<ul>
<li><a
href="https://www.cs.usfca.edu/~galles/visualization/BST.html">
Binary search tree visualizer
</a>
</li>
<li><a
href="https://www.khanacademy.org/computer-programming/binary-search-tree-visualization/5765350200442880">
Khan Academy BST visualizer
</a>.
</li>
</ul>
</details>
<details>
<summary class="sum1">
Homework
</summary>
<ol>
<li>For the first tree above, write the steps that will take place
when we insert 11.
</li>
<li>Write recursive versions of TREE-MINIMUM and
TREE-MAXIMUM.
</li>
<li>Compare the deletion of the node with key == 8
in Tree 2 that takes place following our
textbook's algorithm with what the first visualizer linked
to above actually does in this situation. Clearly, two
different binary trees result. What algorithm is being used
by the visualizer? (You could build different trees and see
what it does: this is called <b>reverse engineering</b>.)
If both algorithms always build valid BSTs, is there some
reason we should prefer one algorithm or the other?
</li>
<li>Keys are input to a binary search tree (BST) in the following order:
5, 10, 15, 20, 25.
Draw the resulting BST.
</li>
<li>Keys are input to a binary search tree (BST) in the following order:
50, 40, 35, 20, 15.
Draw the resulting BST.
</li>
<li>Keys are input in the following order:
10, 7, 15, 2, 25, 33, 1, 8, 9.
Draw the resulting BST.
Trace the process that occurs when inserting key 18.
</li>
<li>Keys are input in the following order:
6, 98, 4, 3, 5, 2, 1, 13, 106, 14, 18, 80.
Trace the process by which the successor of 80 will be
found.
</li>
</ol>
</details>
</body>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-97026578-2', 'auto');
ga('send', 'pageview');
</script>
</html>