/* CSC17 Binary Search Tree Lab Part I (VERSION B) In this version of the lab, the Tree interface does not contain any 'default' declarations. It's unreasonable to expect anyone to anticipate beforehand all the procedures that one might want to implement for a data structure. It is more realistic to *extend* the interface with another interface. However, doing so entails needing to type cast at strategic points in the program. To avoid confusing everybody, I've made this version of the assignment optional. First, the Tree interface should be as follows: */ interface Tree { boolean empty(); int height(); // height of tree T search(T x); // search for something .compareTo(x)==0 Tree insert(T x); // insert into tree, usages: t = t.insert(x); Tree delete(T x); // search and delete x from tree, t=t.delete(x); int size(); }// Tree interace, designed to have two subclasses (nil and vertex) // All methods that are required for the assignment should be placed in // a separate interface: interface ExtTree extends Tree // can put this in separate file { default Tree makeclone() { return null; } default T leastitem() { return null; } default int width(int hdistance) { return 0; } default boolean isBst(T min, T max) { return true; } default Object traverse() {return null;} //generic action with default } // The default implementations are not correct, and are only included // so your classes will still compile without implementing them. You may // add new declarations to this interface, but not to the original Tree. /* The superclass (including inner classes) in Bst2020.java will still compile with these modified interfaces. Read the description for the regular lab 9a concerning the structure of the Bst2020 class: 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 java.util.Comparator cmp = (x,y) -> x.compareTo(y); 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 ============ This version of the lab asks you to extend my implementation to have some additional/enhanced functionality. This requires you to implement the extended interface ExtTree extending both the inner and outer classes. Since the superclasses that you're inheriting already implements Tree, you just need to implement the new methods. As usual, you cannot touch the existing interfaces and classes, only extend them. When using inheritance this aggressively, you will evetually run into situations that require type casting. Recall the examples: Object x = "abc"; // this is ok because a String is an Object int n = x.length(); // this won't compile because Object has no .length() int n = ((String)x).length(); // this will compile and run correctly String s = x; // this won't compile: need String s = (String)x; Integer y = (Integer)x; // this compiles but will give runtime error So there are situations where you will need to type cast from a general type (like Object) to a more specific type (String or Integer), but only if you're sure that the object will have that specific type at runtime. I've written out the general structure that your program should have, as well as some critically important pieces of code that you will need, but you still need to think carefully about the static and dynamic types of each value in your program. You can change the names of your subclasses as you see fit. If you use this version, compile all relevant files together: javac treelab20b.java Bst2020.java BstGraph.java */ class ExtBst> extends Bst2020 { class extnil extends nil implements ExtTree { //.. new/different methods // must include following: /////////////////////// public Tree insert(T x) { count++; return new extvertex(x,this,this); } } class extvertex extends vertex implements ExtTree { public extvertex(T x, ExtTree l, ExtTree r) //constructor { super(x,l,r); } // .. new/different instance variables and methods, including ExtTree left() { return (ExtTree)left; } ExtTree right() { return (ExtTree)right; } // ... these methods encapsulates type casting. } //// .. 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 treelab20b { 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. Remember that if A extends B, then an object of type A *is a* object of type B. So any code written for B will still work for A. Note that in the extvertex class the left and right pointers that were inherited from vertex are of static type Tree, and not ExtTree, so we can only call Tree methods on it. However, because the constructor as written only accept ExtTree as left and right, we know that type casting them should work: (ExtTree)left will compile and run. The left() and right() methods encapsulate the required type casting. Now instead of calling something like left.makeclone(), you will instead call left().makeclone(). 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 ExtTree 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. */