Problem Set 8. Posted 4/19. Due on 4/27.

1. Here is an implementation of the BinarySearchTree class due to Lafore. It is correct, but ugly and too long. Your task is to reorganize this code and shorten it by reusing code. Your tasks are as follows:
   1. Make the Node class and the tree class generic. Do this by assuming that each node has a field called data of generic type, in addition to the fields leftChild and rightChild. The binary search tree will be organized according to the data field.

   2. Implement a private search function with the following function header:

      	boolean search(E key, Node current, Node parent)
      

      The function returns true or false to indicate if key has been found in the tree. If key has been found, the reference current will point to the node containing key; otherwise, current will be null. If key has been found and current has a parent, then the reference parent will point to that parent. If key has not been found and the tree is non-empty, then parent will point to the node who would be the parent of the node containing key, if key were to be inserted now. In all other cases, parent should be null.

   3. The find, insert, and delete functions, all start with a search of the binary search tree. Modify each of these functions by replacing the code for "search" by a call to search function defined above.

   4. Implement a method in the tree class called height that returns the height of the binary search tree. Recall that the height of a binary search tree is the length of a longest path from root to a left. An empty tree has no root and therefore its height is undefined; in this case your function should return -1.
      Hint: This function is easy if you use recursion: get the height of the left subtree, the height of the right subtree, and combine these two pieces of information to get the height of the current tree.

   5. To test your implementation, run the following experiments.
      1. Generate for each value of n, 10 real arrays of size n, filling each array with a random real number between 0 and n-1. For each array, scan it "left to right" (i.e., from slot 0 to slot 1 to slot 2, etc. all the way to slot n-1) and insert each real number into the binary search tree. After all the insertions have been completed, compute the height of the tree. Then compute the average height of the tree, over the 10 runs with this value of n. Do this for the following values of n: 1000, 2000, 3000, ..., 10,000 and plot the average height as a function of n.
      2. Repeat the above experiment, but with each size-n real array generated in the following manner. Thus the array starts off with entries 0, 1, 2, ..., n-1 in that order. Then do the following 20 times: pick a pair of indices i and j, at random, in the range [0, n-1], and swap the elements in slots i and j. After this is done, we may no longer have a sorted array, but the array will still be "almost sorted." Plot the average tree height as a function of n.
      3. Discuss and explain the different in the two plots.

2. Rotations are extremely important local operations that one can perform on binary trees. Rotations are used critically in all versions of binary search tree implementations in which an attempt is made to keep the tree balanced. These include AVL trees and red-black trees. Rotations are also used in the "self-adjusting" binary search trees called splay trees. There are two types of rotations: right rotation and left rotation. These are nicely illustrated at the Wikipedia page on tree rotations.
   1. Implement the right rotation and the left rotation operations as methods in the tree. class. Use the following function headers:

      	void rightRotation(Node <E> localRoot)
      	void leftRotation(Node <E> localRoot)
      

   2. The rotate-to-top tree is a data structure similar to the well-known splay tree data structure. It is just like a binary search tree, except that whenever we search for a node and find it, we bring it to the top of the tree using a sequence of rotate operations. Suppose we have found the key at a node x that is the left child of its parent y. Then performing a right rotation at y will move x up one level. This process can be repeated until x reaches the root. Such a "self-adjusting" data structure is extremely effecient when certain elements are accessed frequently because such elements will spend most of their time close to the root of the tree.

      Implement a class called rotateToTopTree which implements the data structure described above. The rotateToTopTree class is like the tree class, except that the find method behaves a bit differently. When this method finds a node x with the given key, it rotates x to the top; if find does not find a node with the given key, it takes the node y that was the last node in the search path and rotates y to the top.

3. A binary tree is said to be balanced if for every node x in the tree, the difference between the heights of the left subtree of x and the right subtree of x is 0, 1, or -1.
   1. Insert the elements 30, 20, 35, 32, 33 in that order, into an empty binary search tree. Draw the resulting tree. Is it balanced? Explain your answer.
   2. Start with the following binary search tree:

      	root = 100, left child of 100 = 80, right child of 100 = 120
      	left child of 80 = null, right child of 80 = 90
      	left child of 120 = null, right child of 120 = null 
      	left child of 90 = 85, right child of 90 = null 
      	left child of 85 = null, right child of 85 = null 
      

      Perform a left rotation at 80. Show the resulting tree. Is it balanced? Explain your answer.
   3. Start with the binary search tree given above. Perform a right rotation at 90 and show the resulting tree. Perform a left rotation at 80 and show the resulting tree. Is it balanced? Explain your answer.