forked from gcallah/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 1
/
BinarySearchTrees.html
293 lines (265 loc) · 10.5 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
<html>
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analysis of Algorithms: Binary Search Trees
</title>
</head>
<body>
<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/4/43/BinaryTreeRotations.svg/405px-BinaryTreeRotations.svg.png">
</p>
</div>
<h2>
What is a binary search tree?
</h2>
<h3>
Running time
</h3>
<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>
<h3>
Binary Search Tree Property
</h3>
<blockquote>
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.
</blockquote>
<p>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png">
<br>
<em>(Tree 1)</em>
</p>
<h2>
Querying a binary search tree
</h2>
<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>
<h3>
Search
</h3>
<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>Else recursively call tree search on curr.right.
</ul>
</p>
<p>
<br>
<b>Example:</b>
<br>Let's search for 4 in the tree above.
<ul>
<li>4 < 8; move left
<li>4 > 3; move right
<li>4 < 6; move left
<li>Voila!
</ul>
</p>
<h3>
Minimum and maximum
</h3>
<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>
<h3>
Successor
</h3>
<p>
Similarly, 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.
<br>
<br>
<img
src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/BinTree1.png">
<br>
<em>(Tree 2)</em>
<br>
</p>
<h2>
Insertion and deletion
</h2>
<h3>
Insert
</h3>
<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>5 > 3, so we move right.
<li>5 < 6, so we move left.
<li>5 > 4, so we move right and insert.
</ul>
</p>
<h3>
Delete
</h3>
<p>
Deletion is by far the most complicated coding of any of these
functions. There are four cases (and z is the node to delete):
</p>
<ol>
<li>
<li>z has no left child. (This handles two cases!)
<br>
<b>Action:</b> Replace z by its right child, which might be
NIL.
<li>z has only a left child.
<br>
<b>Action:</b> Replace z by its left child.
<li>z has two children.
<br>
<b>Action:</b> Find z's successor y, which lies in its
right sub-tree.
<ul>
<li>If y is z's right child, replace z by y.
<li>Otherwise, replace y by its own right child, then
replace z by y.
</ul>
</ol>
<p>
Let's walk through deleting 8 in tree 2 above.
</p>
<ul>
<li>8 has two children, so we are in case 4.
<li>The successor of 8 is 9.
<li>9 is not the right child of 8.
<li>So we replace 9 by 10.
<li>Then we replace 8 by 9.
</ul>
<p>
The right half of tree 2 now looks like this:
<br>
<br>
<img
src="https://raw.githubusercontent.com/gcallah/algorithms/master/graphics/BinTree2.png">
</p>
<h2>
Randomly built binary search trees
</h2>
<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>
<h2>
Source Code
</h2>
<p>
<a
href="https://github.com/gcallah/algorithms/blob/master/python/binary_search_trees.py">
Python
</a>
<br>
<a
href="https://github.com/gcallah/algorithms/blob/master/ruby/binary_trees.rb">
Ruby
</a>
</p>
<h2>
External Links
</h2>
<ul>
<li><a
href="https://www.cs.usfca.edu/~galles/visualization/BST.html">
Binary search tree visualizer
</a>
<li><a
href="https://www.khanacademy.org/computer-programming/binary-search-tree-visualization/5765350200442880">
Khan Academy BST visualizer
</a>.
</ul>
<h2>
Homework
</h2>
<ol>
<li>For the first tree above, write the steps that will take place
when we insert 11.
<li>Write recursive versions of TREE-MINIMUM and
TREE-MAXIMUM.
<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>Keys are input to a binary search tree (BST) in the following order:
5, 10, 15, 20, 25.
Draw the resulting BST.
<li>Keys are input to a binary search tree (BST) in the following order:
50, 40, 35, 20, 15.
Draw the resulting BST.
<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>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.
</ol>
</body>
</html>