/* CSC17 Binary Search Tree Lab Part I due 4/20 The first part of this lab will also set you up for part 2. Find and study the structure of Tree.java (interface) and Bst2020.java, which implements (unbalanced) binary search trees. The structure of this implementation differs from the one I did quickly in class mainly in that the two classes that 'implements' Tree, nil and vertex, are placed inside a wrapper class called Bst2020. In case you find the code confusing to read, the classes have the following simiplified structure: class Bst2020> { class nil implements Tree { //... } class vertex implements Tree { //... } ///// instance variables of outer class Tree root = new nil(); // pointer to root of tree, initially nil int count; // size of tree // ... ///// methods of outer Bst2020 class int size() { return size;} // don't confuse with size() in nil/vertex int depth() { .. calls root.height() .. } boolean contains(T x) { .. calls root.search(x) .. } boolean add(T x) { .. calls root=root.insert(x) .. } boolean remove(T x) { .. calls root=root.delete(x) ..} // ... } // outer class Note that except for size(), the functions/methods of the outer class have different names to those of the inner classes. ***The outer class does NOT implement Tree, only the inner classes nil and vertex do.*** The main advantage of placing nil and vertex inside the wrapper class is the outer size() function, which now takes constant time instead of O(n). Code in the inner class can access the instance variables (including count) of the outer class. You can think of an instance (object) of the outer class as containing objects of the inner classes. Besides that, there is less syntax as the parameter only needs to be declared for the outer class (but Java generics won't allow this for the interface - the Tree interface needs to be outside the outer class). Other differences between Bst2020 and the one I wrote during the lecture include: a. Using the java.util.Comparator interface in addition to Comparable: interface Comparator { int compare(T x, T y); } With this interface, you can more easily change how two T objects are compared by assigning a Comparator object to a lambda term. The outer class contains an instance variable Comparator cmp = (x,y) -> x.compareTo(y); So ***calling cmp.compare(a,b) is the same as calling a.compareTo(b)***, until the cmp object is changed to another lambda (to invert the comparison, for example). We still require > for the Bst2020 class so we can define a default cmp. b. The search method returns a T object, and not just a boolean. This is because cmp.compare(x,y)==0 doesn't necessarily mean that x.equals(y). So search(x) returns the 'item' that compares with x to zero. If search fails, null is returned. This is the only intensional use of null in this program. ============ This lab asks you to extend my implementation to have some additional/enhanced functionality. This requires you to extend both the inner and outer classes, though most of the work will be in extending the inner classes. I've written out the general structure that your program should have. You can change the names of your subclasses as you see fit. */ class ExtBst> extends Bst2020 { class extnil extends nil { //.. new/different methods // must include following: /////////////////////// public Tree insert(T x) { count++; return new extvertex(x,this,this); } } class extvertex extends vertex { public extvertex(T x, Tree l, Tree r) //constructor { super(x,l,r); } // .. new/different instance variables and methods } //// .. new/different instance variables and methods of the outer class public ExtBst() { root = new extnil(); } //constructor should look like this // .. }// outer ExtBst class public class treelab20 { public static void main(String[] argv) { BstGraph W = new BstGraph(1024,768); // graphical display of tree ExtBst mytree = new ExtBst(); // do something with mytree W.draw(mytree); // graphically render tree // perform some other tests. }//main } /* The inner superclasses nil and vertex become visible when you're extending the outer class, and can also be extended. Because an instance of a subclass is still an instance of the superclass, all existing programs that use Bst2020 should still work with your new subclass, including my BstGraph program for graphically rendering reasonably sized trees. */ /* Now for the lab: 1. Implement the public Tree makeclone() function specified in the Tree interface for both extnil and extvertex. This function should create a copy of the object so that changing one does not change the other. However, the makeclone function in nil should just { return this; } because all instances of nil are still the same. However, for vertex, you need to create a new vertex with the same item, and with *recursively cloned* left and right subtrees. Also add public ExtBst clonetree() to the outer class: this method should produce a duplicate of the wrapper class by cloning the root. 2. Consider where in a binary search tree can you find the smallest value (according to compareTo). Write a method for the *outer* class public T smallest() // that returns the smallest T stored in the tree If the tree is empty (if root is nil) then smallest can either throw an exception or return null. You can choose to write this function in several ways: i. Implement the leastitem() function in the Tree interface for nil and vertex (just vertex if the default is OK for nil) . Then in the outer smallest() function you can just call and return root.leastitem(). This approach will induce to you use recursion, which is OK because eventually we'll keep the tree balanced. ii. You can also write a standalone procedure that uses a loop to find the left-most descendant of root. This can be done without adding anything to the nil/vertex classes. However, at some point you're going to need to apply TYPE CASTING. Consider the following lines of code: vertex next; if (root.empty()) return null; else next = root; This code will not compile. Why? Because the static type of root is Tree and the static type of next is vertex. next=root doesn't type check. But you know that if root is not empty, then it must be a vertex (you know, but the compiler doesn't), so you should write the assignment like this: next = (vertex)root; Write a loop that sets next to next.left until next.left.empty(). 3. How do you know that your tree is really a binary *search* tree. If people only built the tree by calling the add function, then the we should only get a binary search tree. However, it's possible that vertexes get created some other way, with left and right subtrees that do not observe the requirements of binary search trees (even if we used 'private' instance variables and methods, there are still ways to circumvent the protection). Also, what if in the process of overriding the insert function you accidently "broke it?" How do we check that a tree is indeed a BST? The following might compile and run, but it's WRONG: public boolean isbst(Tree subtree) // call isbst on root initially { if (subtree.empty()) return true; // empty tree is vacuously a BST vertex v = (vertex)subtree; boolean leftok, rightok; if (v.left.empty()) leftok = true; else { vertex vleft = (vertex)v.left; leftok = cmp.compare(vleft.item, v.item)<0 && isbst(vleft); } if (v.right.empty()) rightok = true; else { vertex vright = (vertex)v.right; rightok = cmp.compare(vright.item, v.item)>0 && isbst(vright); } return leftok && rightok; } Why is it wrong? Trace it on the following example: 4 / \ 2 8 / \ 1 5 Is this a binary search tree? What will the above function return if called on the root? The code for the correct solution is actually much simpler: implement the boolean isBst(T min, T max) function in the Tree interface inside nil and vertex. This function should recursively check that each item is larger than min and less than max. You can call this function intially on the root with root.isBst(null,null). Use null to represent +/- infinity (negative infinity for min, positive infinity for max). Now think: how should min/max change on the recursive calls to the left and right subtrees? I can write this without any if-statements. Can you? 4. CHALLENGE. We've seen how to define the "depth" or "height" of a tree. One may also wish to know its "width". That is, what is the node farthest from the root on the left and the node farthest on the right. We can define the horizontal distance of a node to the root as follows: Each node in a tree is reachable from the root by following a sequence of left/right links. Each time we go left, we decrease the horizontal distance by one, and each time we go right we increase it by one. The root node has distance zero. The width of the tree can then be defined as the absolute value of the difference between the largest and smallest horizontal distances. Note that not all nodes on the left of the root will have negative distances, and not all nodes on the right of root will be positive. Consider the following example: 12 / \ 5 2 \ 7 \ 8 \ 9 \ 10 The horizontal distance of the node containing 10 is +3, because we go once left and four times right to reach it. The h-distance of the node containing 5 is -1. The width of this tree is Math.abs(-1 - 3) == 4. Implement the int width() function for the wrapper class. You may want to also implement the int width(int hdistance) function of the Tree interface. You may also need to add new variables to the outer or inner classes. You may implement this however you see fit. */