forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
index.html
361 lines (361 loc) · 15.5 KB
/
index.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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>PDR: Laboratory 5: Trees</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="pdr-laboratory-5-trees">PDR: Laboratory 5: Trees</h1>
<p><a href="../index.html">Go up to the Labs table of contents
page</a></p>
<h3 id="objective">Objective</h3>
<ol type="1">
<li>Learn about binary trees</li>
<li>See tree traversals in the context of a useful application</li>
<li>Understand tree rotations</li>
<li>Implement a binary search tree and an AVL tree</li>
<li>Evaluate the performance of binary search trees and AVL trees</li>
</ol>
<h3 id="background">Background</h3>
<p>A binary tree is a tree with a maximum of two children per node. Tree
traversals are commonly associated with binary trees. A pre-order
traversal processes the given node first and then processes its left and
then right subtrees. In an in-order traversal, first the node’s left
subtree is processed, followed by the node itself, and finally its right
subtree. A post-order traversal operates on the left subtree, followed
by the right subtree, and finally on the node itself.</p>
<p>A binary search tree is a binary tree that imposes an ordering on its
nodes. A node’s left child has a lesser value, while its right child has
a greater value. Binary search trees are useful for efficient insertion,
deletion, and lookup of items with a certain key. As we’ll see in this
lab, variations of binary search trees offer different performance
characteristics.</p>
<h3 id="tutorial">Tutorial</h3>
<p>Complete the <a href="../../tutorials/05-make/index.html">Makefile
tutorial</a>. You will need to know how to write one for the pre-lab,
in-lab and post-lab, since all the following labs will be compiled via
Makefiles.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<p>The <a href="https://en.wikipedia.org/wiki/Expression_tree">Wikipedia
article on Expression trees</a>, especially the <a
href="https://en.wikipedia.org/wiki/Expression_tree#Construction_of_an_expression_tree">section
on construction of expression trees</a>. Also the <a
href="../../slides/05-trees.html">05: Trees</a> slide set.</p>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Create a postfix tree calculator</li>
<li>Files to download: <a
href="code/prelab/TreeCalc.h.html">TreeCalc.h</a> (<a
href="code/prelab/TreeCalc.h">src</a>), <a
href="code/prelab/TreeCalc.cpp.html">TreeCalc.cpp</a> (<a
href="code/prelab/TreeCalc.cpp">src</a>), <a
href="code/prelab/TreeNode.h.html">TreeNode.h</a> (<a
href="code/prelab/TreeNode.h">src</a>), <a
href="code/prelab/TreeNode.cpp.html">TreeNode.cpp</a> (<a
href="code/prelab/TreeNode.cpp">src</a>), and <a
href="code/prelab/TreeCalcTest.cpp.html">TreeCalcTest.cpp</a> (<a
href="code/prelab/TreeCalcTest.cpp">src</a>). These files are contained
in the prelab/ directory of the <a href="code.zip">code.zip</a>
file.</li>
<li>Files to submit: TreeCalc.h/cpp, TreeCalcTest.cpp, TreeNode.h/cpp,
Makefile</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol type="1">
<li>Implement a binary search tree</li>
<li>Files to download: <a
href="code/inlab/BinaryNode.h.html">BinaryNode.h</a> (<a
href="code/inlab/BinaryNode.h">src</a>), <a
href="code/inlab/BinaryNode.cpp.html">BinaryNode.cpp</a> (<a
href="code/inlab/BinaryNode.cpp">src</a>), <a
href="code/inlab/BinarySearchTree.h.html">BinarySearchTree.h</a> (<a
href="code/inlab/BinarySearchTree.h">src</a>), <a
href="code/inlab/BinarySearchTree.cpp.html">BinarySearchTree.cpp</a> (<a
href="code/inlab/BinarySearchTree.cpp">src</a>), <a
href="code/inlab/BSTPathTest.cpp.html">BSTPathTest.cpp</a> (<a
href="code/inlab/BSTPathTest.cpp">src</a>), <a
href="code/inlab/testfile1.txt">testfile1.txt</a> (<a
href="code/inlab/testfile1.out.txt">output</a>), <a
href="code/inlab/testfile2.txt">testfile2.txt</a> (<a
href="code/inlab/testfile2.out.txt">output</a>), <a
href="code/inlab/testfile3.txt">testfile3.txt</a> (<a
href="code/inlab/testfile3.out.txt">output</a>). These files are
contained in the inlab/ directory of the <a href="code.zip">code.zip</a>
file.</li>
<li>Files to submit: BinarySearchTree.h, BinarySearchTree.cpp,
BinaryNode.h, BinaryNode.cpp, BSTPathTest.cpp, Makefile, and any other
files needed to make your code compile.</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol type="1">
<li>Implement an AVL tree</li>
<li>Files to download: <a
href="code/postlab/AVLNode.h.html">AVLNode.h</a> (<a
href="code/postlab/AVLNode.h">src</a>), <a
href="code/postlab/AVLNode.cpp.html">AVLNode.cpp</a> (<a
href="code/postlab/AVLNode.cpp">src</a>), <a
href="code/postlab/AVLTree.h.html">AVLTree.h</a> (<a
href="code/postlab/AVLTree.h">src</a>), <a
href="code/postlab/AVLTree.cpp.html">AVLTree.cpp</a> (<a
href="code/postlab/AVLTree.cpp">src</a>), <a
href="code/postlab/AVLPathTest.cpp.html">AVLPathTest.cpp</a> (<a
href="code/postlab/AVLPathTest.cpp">src</a>), <a
href="code/postlab/testfile1.txt">testfile1.txt</a> (<a
href="code/postlab/testfile1.out.txt">output</a>), <a
href="code/postlab/testfile2.txt">testfile2.txt</a> (<a
href="code/postlab/testfile2.out.txt">output</a>), <a
href="code/postlab/testfile3.txt">testfile3.txt</a> (<a
href="code/postlab/testfile3.out.txt">output</a>). These files are
contained in the postlab/ directory of the <a
href="code.zip">code.zip</a> file.</li>
<li>Files to submit: AVLTree.h, AVLTree.cpp, AVLNode.h, AVLNode.cpp,
AVLPathTest.cpp, Makefile, and any other files needed to make your code
compile (see the post-lab section for formatting details)</li>
</ol>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<p>For the pre-lab you will be using a stack to help you read in a
postfix expression into an expression tree. While this is similar to lab
3, you will instead be ultimately creating an expression tree for the
postfix expression, rather than evaluating it and leaving the result on
the stack.</p>
<h3 id="implementation">Implementation</h3>
<p>Your tree calculator will read in well-formed expressions in postfix
notation. You will need to build an expression tree using the algorithm
described in the <a
href="https://en.wikipedia.org/wiki/Expression_tree#Construction_of_an_expression_tree">Wikipedia
article on Expression trees</a> and the <a
href="../../slides/05-trees.html">trees slide set</a>. Trees similar to
this type of expression tree are used extensively in compilers.</p>
<p>Your fully functional tree calculator must:</p>
<ul>
<li>Read well-formed postfix expressions into a stack, supporting the
following input:
<ul>
<li>Integers, both positive and negative</li>
<li><code>+</code>: addition</li>
<li><code>-</code>: subtraction</li>
<li><code>*</code>: multiplication</li>
<li><code>/</code>: integer division</li>
</ul></li>
<li>Build an expression tree using the items in the stack</li>
<li>Print the resulting expression tree as a postfix, infix, and prefix
expression, in the following format:
<ul>
<li>One space between each value, excluding parentheses (leading and
trailing spaces are acceptable)</li>
<li>Parentheses around every infix operation, regardless of operator
precedence</li>
<li>A single line that terminates with a newline character</li>
</ul></li>
<li>Calculate the result of your expression using the expression
tree</li>
<li>Print the result to the screen</li>
<li>Have no memory leaks</li>
</ul>
<p>Additionally, you should use the skeleton source files in the prelab/
directory of <a href="code.zip">code.zip</a> as a basis for your tree
calculator. You may modify and add to the skeleton code as you see fit,
but TreeCalcTest, TreeNode, <code>readInput()</code>, and
<code>printOutput()</code> must NOT be modified.</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>Enter elements one by one in postfix notation
Any non-numeric or non-operator character, e.g. #, will terminate input
Enter first element: 34
Enter next element: 6
Enter next element: +
Enter next element: -8
Enter next element: 4
Enter next element: /
Enter next element: -
Enter next element: #
Expression tree in postfix expression: 34 6 + -8 4 / -
Expression tree in infix expression: ((34 + 6) - (-8 / 4))
Expression tree in prefix expression: - + 34 6 / -8 4
The result of the expression tree is 42</code></pre>
<h3 id="submission">Submission</h3>
<p>You should submit any files required for your tree calculator to run.
TreeCalcTest.cpp, TreeNode.h, and TreeNode.cpp should not be
modified.</p>
<h3 id="hints">Hints</h3>
<p><strong>Recursion is the way to go:</strong> Recursion is very useful
in traversing the expression tree. You’ll need to use recursion for many
of the TreeCalc methods.</p>
<p><strong>Printing in the right order:</strong> Draw a simple tree and
see how you should recurse in order to hit each node in the correct
order. Need more help? Check the <a
href="https://en.wikipedia.org/wiki/Expression_tree">Wikipedia
article</a>!</p>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<p>For this in-lab, you will implement a binary search tree.</p>
<h3 id="bst-implementation">BST Implementation</h3>
<p>The necessary files are in the inlab/ directory of <a
href="code.zip">code.zip</a>.</p>
<p>The required class declarations are located in <a
href="code/inlab/BinaryNode.h.html">BinaryNode.h</a> (<a
href="code/inlab/BinaryNode.h">src</a>) and <a
href="code/inlab/BinarySearchTree.h.html">BinarySearchTree.h</a> (<a
href="code/inlab/BinarySearchTree.h">src</a>). You may want to create
private helper methods for BinarySearchTree, as done for the
implementation of <code>remove()</code>, which is already provided for
you. The private methods take BinaryNodes as parameters which allow them
to recurse over a subtree, a common implementation technique.</p>
<p>You should use <a
href="code/inlab/BSTPathTest.cpp.html">BSTPathTest.cpp</a> (<a
href="code/inlab/BSTPathTest.cpp">src</a>) to test your implementation,
but you may NOT change it.</p>
<p>Unlike the pre-lab, you <em>can</em> modify the various files
provided EXCEPT for BSTPathTest.cpp and AVLPathTest.cpp.</p>
<h3 id="test-files">Test Files</h3>
<p>We provide a number of test files that you can use as input: <a
href="code/inlab/testfile1.txt">testfile1.txt</a> (<a
href="code/inlab/testfile1.out.txt">output</a>), <a
href="code/inlab/testfile2.txt">testfile2.txt</a> (<a
href="code/inlab/testfile2.out.txt">output</a>), and <a
href="code/inlab/testfile3.txt">testfile3.txt</a> (<a
href="code/inlab/testfile3.out.txt">output</a>)</p>
<p>The test program reads a sequence of instruction/word pairs and
attempts to operate on your tree.</p>
<ul>
<li>Insert <word>: <code>I <word></code></li>
<li>Remove <word>: <code>R <word></code></li>
<li>Lookup <word>: <code>L <word></code></li>
</ul>
<p>The Lookup instruction will call the <code>pathTo()</code> method
defined on your tree. <code>pathTo()</code> must return a string
representing the nodes encountered when finding an element. For instance
in the following image, the bold lines indicate the path taken for
locating element W.</p>
<p><img src="avl-tree-pic-1.png" /></p>
<p><code>pathTo("W")</code> would then return the string <code>"M P Z
W"</code>. Calling <code>pathTo()</code> on an element that doesn’t
exist would result in an empty string <code>""</code>.</p>
<h3 id="sample-execution-run-1">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>I We
I can't
I solve
I problems
I by
I using
I the
I same
I kind
I of
I thinking
I we
I used
I when
I we
I created
I them
I -Albert
I Einstein
L created
BST path: We can't solve problems kind created
BST numNodes: 18</code></pre>
<h3 id="submission-1">Submission</h3>
<p>You should submit your BST, any supporting C++ files, as well as a
Makefile to compile everything into an <code>a.out</code>
executable.</p>
<h3 id="hints-1">Hints</h3>
<p><strong>Private methods:</strong> Following the suggestion to
implement private versions of all the public methods that take in
BinaryNodes will help considerably. How should your public method
interact with the private version? In other words, what node should the
public method pass in?</p>
<p><strong>Passing pointers by reference:</strong> When a pointer is
passed by reference, that allows us to change not only the data that the
pointer is pointing to, but also <em>what the pointer is pointing to in
the first place</em>. This is one option that allows you to change the
structure of your tree without having to use parent pointers.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<p>The objective of this post-lab is to understand the run-time
characteristics and trade-offs between normal Binary search trees and
AVL trees. Your deliverable for this post-lab will be an AVL tree
implementation.</p>
<h3 id="avl-implementation">AVL Implementation</h3>
<p>The structure of the provided AVL starter code is analogous to that
of the BST, and is not discussed in further detail here. The starter
files are in the postlab/ directory of <a href="code.zip">code.zip</a>.
The comments in the code of the starter files help explain where to
start.</p>
<p>You may test your implementation with the same test files as before,
though the expected output will be different (<a
href="code/postlab/testfile1.out.txt">output of testfile1</a>, <a
href="code/postlab/testfile2.out.txt">output of testfile2</a>, <a
href="code/postlab/testfile3.out.txt">output of testfile3</a>).</p>
<p>Unlike the pre-lab, you <em>can</em> modify the various files
provided EXCEPT for BSTPathTest.cpp and AVLPathTest.cpp.</p>
<h3 id="sample-execution-run-2">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>I We
I can't
I solve
I problems
I by
I using
I the
I same
I kind
I of
I thinking
I we
I used
I when
I we
I created
I them
I -Albert
I Einstein
L created
AVL path: problems can't kind created
AVL numNodes: 18</code></pre>
<h3 id="submission-2">Submission</h3>
<p>You should submit your AVL tree, any supporting C++ files, and the
Makefile.</p>
<h3 id="hints-2">Hints</h3>
<h4 id="balancing">Balancing</h4>
<p><code>balance(AVLNode*& node)</code> is crucial for both insert
and remove, but has many cases that you must account for. To help avoid
potential issues, here is some pseudocode for the balance method that
you may use:</p>
<pre><code>//Note that balance factor here is assumed to be (height of right subtree - height of left subtree)
balance(node):
if balance factor of node is 2 we will need to rotate left:
first, see if we should also rotate right (i.e., do a double rotation)
if balance factor of right child is negative:
rotate right on the right child
endif
rotate left on node
else if balance factor of node is -2 we will need to rotate right:
first, see if we should also rotate left (i.e., double rotation)
if balance factor of left is positive:
rotate left on the left child
endif
rotate right on node
endif</code></pre>
</body>
</html>