Tutorial 7, CPSC 331, Fall 2008

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

About This Exercise

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.

Problems To Be Solved

1. Consider the following binary tree.

   

   1. Which node is the root of this tree?
   2. What is the size of this tree?
   3. What is the height of this tree?
   4. Which nodes are ancestors of the node with label d?
   5. Which nodes are proper ancestors of the node with label d?
   6. Which nodes are descendants of the node with label d?
   7. Which nodes are proper descendants of the node with label d?
   8. Which nodes are siblings of the node with label d?
   9. Which nodes are children of the node with label d?
   10. What is the depth of the node with label d?
   11. Which of the nodes of this tree are internal nodes?
   12. Which of the nodes of this tree are leaves?

   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

   
   

2. 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.

3. 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.

   1. insert(7, seventh)
   2. delete(6)
   3. insert(12, twelfth)
   4. insert(1, first)
   5. insert(6, sixth)
   6. insert(5, fifth)

4. Repeat the previous question, starting with the following binary search tree instead of the one shown above.

   

5. 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.

6. 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.

7. 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.

   1. 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.

   2. 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.

8. 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