Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
The laboratory exercise on extending the binary tree class primarily exercises students’ ability to design and reason formally about binary tree algorithms. However, some of the problems are subtle, requiring cleverness to design clear and efficient algorithms. The exercise can therefore also help students develop good taste in algorithms and habits of thoughtful design, reducing tendencies to code the first solution to a problem that comes to mind.
Many of the problems in this lab can be solved by straightforward tree traversals. Computing a tree’s size, height, and number of leaves fall squarely into this category. So does determining whether two trees are identical, although the algorithm must traverse both trees simultaneously. Correctness proofs for all of these algorithms can be done by strong induction on either the tree’s size or its height (either will work for any of the proofs, and neither makes the proof significantly easier or harder to construct). Performance analyses can be done by setting up recurrence relations for the work the algorithm does in terms of the work it does recursively to process the two subtrees — the recursive parts of the recurrences will therefore be of the form
f(n) = k + f(n1) + f(n2) if n > 0
where n is tree size, k is a constant, and n1 and n2 are the sizes of the two subtrees (thus implying the constraint that n1 + n2 = n-1). Such recurrences have closed forms that are Θ(n).
The problems of determining whether a tree is fully balanced, and of determining whether a tree is ordered, require insight or clever design to solve efficiently. Both can be solved by easily discovered multi-pass algorithms (in the case of balance, recursively determine whether the left and right subtrees are fully balanced, then verify that both subtrees have the same height; in the case of order, recursively determine whether the left and right subtrees are ordered, then that the root’s value lies between the largest value in the left subtree and the smallest in the right). However, because these algorithms make multiple, redundant, passes over a tree, they run in Θ( nlogn ) time on n-element trees. Both problems can be solved in Θ(n) time by cleverer algorithms. (Unfortunately, this document doesn’t describe those algorithms, so as not to give away lab solutions on the World Wide Web; however, people who are verifiably course instructors and want to discuss these algorithms privately should contact baldwin@geneseo.edu.)
Most students will have little trouble finding the maximum element in an ordered binary tree. This is the one problem in this lab whose best solution involves an execution time other than Θ(n).
Because each exercise involves designing and coding an algorithm, writing a correctness proof, and deriving an asymptotic execution time, this lab is time-consuming both for students and for whoever grades the solutions.
Few instructors will assign all the exercises in a single lab session. Instead, most instructors will probably pick a subset of the exercises for their students to do. Depending on the duration of the lab sessions, and the sophistication of the students, subsets containing between two and four of the exercises are reasonable.
The message that determines whether two trees are identical is almost the equals message
that every Java class should handle. The only difference is that Java’s equals must
accept any object as its parameter, whereas the one in this lab only has to
accept a binary tree. We specified our message in this way so
that students would not have to know how to discover an object’s class
in order to solve the exercise. For students who already know how to do this,
however,
modifying the exercise to write a fully Java-compliant equals method
provides good experience writing code to a robust, real-world, specification.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin