home page - news - syllabus - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
Tutorial 1 - Tutorial 2 - Tutorial 3 - Tutorial 4 - Tutorial 5 - Tutorial 6 - Tutorial 7 - Tutorial 8 - Tutorial 9 - Tutorial 10 - Tutorial 11 - Tutorial 12 - Tutorial 13 - Tutorial 14 - Tutorial 15 - Tutorial 16 |
Ordered Sets, Mappings and Binary Search Trees |
This exercise is based on material presented during the lectures on Friday, October 3 and Monday, October 6.
The objectives of this exercise are
to ensure that you understand the definitions of a binary tree and of a binary search tree, as well as standard notation and terminology for these
to give you practice in solving problems using binary search trees
to give you practice in writing programs to support data structures like binary search trees.
Please read through and try to solve the problems on this exercise before attending the tutorials from October 13 to 17.
Consider the following binary tree.
You may need to consult the course textbook to find definitions of some of the technical terms that are used in the above question!
The next few problems concern representations of dictionaries that initially contain the following elements.
Key | Data |
---|---|
2 | second |
4 | fourth |
6 | sixth |
8 | eighth |
10 | tenth |
Draw the binary search tree that you would obtain by starting with an empty tree and inserting the keys that are listed above, using the order in which they are listed.
Consider a representation of the above mapping as a binary search tree, as shown below (without values being displayed):
Draw the binary search trees that would be obtained if the following sequence of operations was performed.
Repeat the previous question, starting with the following binary search tree instead of the one shown above.
The algorithm for searching in a binary search tree that was presented in the lectures uses “tail recursion:” it only calls itself once (if it does so at all) and this only happens at the end of its computation.
Using this information, produce another algorithm that solves the same problem, as efficiently, without using recursion at all: Your algorithm should use a loop instead.
Describe efficient recursive algorithms that can be used to compute the size as well as the depth of a binary search tree that is given as input. Your functions should each use a number of steps that is at most linear in the size of the given binary search tree.
Suppose that you are given a binary search tree T and a key k as input. and that you wish to find the node storing the smallest key h in the tree that is strictly greater than k.
Describe an algorithm that solves this problem, given k and (as usual) a reference to the root of T as input. Try to describe a reasonably simple algorithm that is as efficient as you can make it.
Now describe an algorithm that solves this problem, given rather different input: This time, the input should be k and a reference to a node is either
the node for the greatest key in the tree that is less than or equal to k, if such a key exists, or
the root of T, if all the keys in the tree are strictly greater than k.
Finally, try to sketch proofs of the correctness of the algorithms for searches, insertions and deletions in binary search trees that have been described in class.
In order to do this you will need to state and work with a property (for each algorithm) that involves
the entire tree T that is given as input at the beginning of a computation, as well as
the subtree of T with a given node x as its root.
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial7.html |