Homework 3
Due Dates:
- Sections 1 & 3: Thursday, October 17, in class.
- Sections 2 & 4: Monday, October 21, in class.
Referenced exercises are from Data Structures and Algorithm Analysis in Java by Mark A. Weiss.
-
Exercise 4.6: [Weiss, 3/e]
A full node in a binary tree is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a non-empty binary tree.
-
Exercise 4.49: [Weiss, 3/e (reworded)]
Suppose we want to add the operation findKth() to our binary search tree repertoire. The operation findKth(k) returns the k-th smallest item in the tree. Assume all items are distinct. Explain how to modify the binary search tree data structure to support his operation. The running time of findKth() should be proportional to the height of the tree. Furthermore, the asymptotic running time of all other operations should not be affected.
-
[from Introduction to Algorithms, Cormen, Leiserson & Rivest, 2/e]
Show that any n-node binary search tree can be transformed into any other n-node binary search tree using O( n ) rotations. Hint: first show that n − 1 right rotations is sufficient to transform any binary search tree into a "right-going chain" (a tree where every node, other than the leaf, has a right child and no left child).