Homework: Trees and Heaps
Thanks to OSU CIS 261 course.

Due date Thursday, Nov. 13, 2003 (5:00 PM)

Treat this paper as a specification for your assignment. Your code will be graded on correctness, readability, and style. Study problems and exercises must be legible and will be graded on correctness.

What to do:

Programming:

1. Finding the largest value in a Binary Search Tree is no more difficult than finding the smallest value. Create a new interface called FindMax that is similar to FindMin (with the exception that the FindMax methods are called getLast and removeLast). Create a new class called AVLMax-Tree that extends the AVLTree in the JDS library and implements the FindMax interface. Alternatively, you can also create a new class called AVLMaxTree that extends AVLTree and create a new inner class AVLMaxNode that extends AVLNode and delegate the FindMax functionality to the node.(5 pts).

2. Create a class, BSTSet that extends the BinarySearchTree class in the JDS library and that adds the following methods (15 pts).

(a) Sorted subSet(Object start, Object stop) — returns a sorted collection that contains all the elements larger than or equal to start and smaller than stop.

(b) Sorted headSet(Object stop) — returns a sorted collection that contains all the elements smaller than stop.

(c) Sorted tailSet(Object start) — returns a sorted collection that contains all the elements larger than or equal to start.

Written homework:

• Add the Integers 7, 4, 2, 5, 6, 8, 1, 3, 0 to an initially empty AVL tree in order. Examine the toString() methods in jds/collection/AVLTree.java and write the output of the tree after each insertion as it would be output by toString(). You can, if you want, write a small program to create an AVL tree, insert the above values in the order indicated, and then invoke the toString() method to generate the results (10 pts).

• Chapter 14 Exercises 2 (5 pts) and 6 (5 pts).

E 14.2) Show the result after inserting the values 1, 3, 1, 4, 1, 5, 9 into an initially empty binary search tree. Then show the result after deleting the root node.

E 14.6) Show all the AVL trees that could result after inserting the values 1, 2, 3, and 4 in various permutations. How many different trees are there?

• Chapter 15 Exercise 3 (10 pts).