Programming project 9

This last programming project is entirely dedicated to binary search trees. Your task is to fill in the implementation for three methods of the BinarySearchTree class in bst.scala, namely upperNeighbor, range, and split.

Do not change any of the existing methods. You can define new private methods, and you probably want to add a method that prints the tree in a nice way to help you debugging.

  1. The method upperNeighbor(x: Int) returns the upper neighbor of \(x\) in the tree (\(x\) may or may not be a key in the tree). The upper neighbor is defined as the smallest key \(y\) in the tree such that \(y > x\). If no such key exists, throw a NoSuchElementException. Your implementation must work in time \(O(h)\), where \(h\) is the height of the tree. Can you do it without recursion, using a single walk through the tree?
  2. The method range(low: Int, high: Int) returns a list of all keys \(x\) with low <= x <= high in sorted order (low and high are not necessarily keys in the tree). Your method must have running time \(O(h + k)\), where \(h\) is the height of the tree, and \(k\) is the length of the returned list.

    The public method range prepares a ListBuffer (a singly-linked list with fast append that can later be converted to a List in constant time) and calls the private method range. Fill in the implementation of this private method.

  3. The method split(x: Int) splits the tree and returns two new trees (as a pair). The first result tree contains all the elements of the tree that are less than or equal to \(x\), the second result tree contains all the elements of the tree that are larger than \(x\). The value \(x\) is not necessarily a key in the tree.

    The method must run in time \(O(h)\), where \(h\) is the height of the tree. So you cannot simply collect the elements and build two new trees: You must compose the new trees from subtrees of the original tree.

    I have already written the public method split, your task is to implement the private method split(x: Int, n: Node). It splits the subtree with root \(n\) and returns the roots of the two new trees. This can be done recursively: You need to create a new root node for one of the output trees, attach one of the subtrees of \(n\) to it, and recursively split the other subtree of \(n\). (There is also the special case x == n.key which can be handled without going into recursion.)

You can use treetest.scala to test your code (this is not a test suite, just run the object TreeTest). Here is an example output: 

$ scala TreeTest 100 13
Inserting numbers into tree.
Height of tree t is 12
Size of tree t is 99

Removing odd numbers from tree:
Height of tree is 10
Size of tree t is 49
First key: 2, last key: 98
Testing that all numbers are in the map:
Testing that numbers were deleted:
Computing ranges:
Range [-7,19] = List(2, 4, 6, 8, 10, 12, 14, 16, 18)
Range [16,23] = List(16, 18, 20, 22)
Range [345,123] = List()
Range [93,105] = List(94, 96, 98)
Upper neighbors:
Upper(99) = No such neighbor
Upper(98) = No such neighbor
Upper(-7) = 2
Upper(15) = 16
Upper(64) = 66
Splitting:
Splitting at 13:
Left size: 6, height 3, max key: 12
Right size: 43, height 10, min key: 14
Splitting at -5:
Left size: 0, height -1, max key: ?
Right size: 49, height 10, min key: 2
Splitting at 50:
Left size: 25, height 6, max key: 50
Right size: 24, height 7, min key: 52
Splitting at 98:
Left size: 49, height 10, max key: 98
Right size: 0, height -1, min key: ?
Splitting at 97:
Left size: 48, height 10, max key: 96
Right size: 1, height 0, min key: 98