CSC 17 Lab: Operations on Binary Search Trees This lab will ask you to "extend" my code for unbalanced binary search trees and create AVL trees, which are balanced. For this assignment, because of its complexity, I will allow you to "extend" my code in one of two ways: 1. Litterally create subclasses of Nil and Vertex 2. Edit the code in place, if the first option is too intimidating. You may do option 2 first, which will then give you the confidence to do 1. For option 1, there are a few, but only a few methods of Nil and Vertex that you will have to *override* in your subclasses. 3. The intended way for these trees to be used is to always start with an empty tree (Nil), then only use authorized insert and delete methods to modify the tree. To help enforce this, you can optionally place your classes (but not the interface) inside a wrapper class, as I've demonstrated with some of the code I wrote in-class. You wrapper class should contain a root pointer to the root node of the tree and methods for insert/delete/search/etc. that calls the coorsponding procedures on the root. Download Bst.java, bst19.java and BstDisplay.java from the homepage. I have added a procedure setheight() that returns the depth of the tree in constant time, by keeping a height variable inside each vertex. The setheight() procedure also returns the height balance of the tree, which is (left.depth - right.depth). There is another, seemingly redundant procedure 'adjust', which calls setheight after each recursive call to insert, delete and delmax (these are the procedures that can alter the tree. 1. (warmup) As you should know, given two trees a and b, 'a=b;' only copies the pointer, not the actual tree. For the warmup, edit bst19.java directly and add the following declaration to the bst19 interface: Bst clone(); That returns the same tree cloned (clone the entire tree recursively!). Implement it in both the Nil and the Vertex classes. a = b.clone(); should then copy the entire tree (up to the level of items), not just the pointer. Devise tests that show that the code works. That is, changing one tree does not affect the other. 2. implement the following "rotation" procedures, which will be required in balancing binary search trees. Add the following methods to the Vertex class (no need to add in interface) void LL() void RR() A "LL" rotation does the following: x y / \ / \ y R ---> LL x / \ / \ LL LR LR R Here, the x, and y are values (items) stored at the nodes and the capital letters represent subtrees (pointers left and right). Think of an LL rotation as a clockwise rotation centered on the vertex containing x. Very importantly, we are guaranteed to preserve the binary-search tree property after rotation. Implement this procedure. The procedure will be called on the vertex with value x. If the vertex has an empty left subtree, then the procedure should do nothing. Otherwise it should modify the tree accordingly. HINT: Do not delete the vertex containing x, just copy y over. However, you will need to construct a new vertex for the new right-subtree. HINT: When you need to access the item of the left subtree, do not refer to left.item, you need to first typecast left, which is of static type Bst, into a Vertex: so use ((Vertex)left).item. That is, use code like this if (!left.isEmpty()) y = ((Vertex)left).item There may be similar points in your code where type casting is needed. **Your procedure should call setheight() to recalculate the heights the trees that you have created. (but for now, just setheight on the subtree being rotated - don't worry yet about adjusting the height of the entire tree). **Your procedure must run in O(1): constant time relative to the size of the tree. A "RR" rotation rotates in the opposite direction (from the second diagram to the first). Implement that too: x y / \ / \ L y ---> x RR / \ / \ RL RR L RL -------- AVL ALGORITHM REVIEW: It is possible to compose rotations. For example, given: 5 / 3 \ 4 If we do a RR rotation centered on 3, we get: 5 / 4 / 3 Then if we do a LL rotation centered on 5, we get: 4 / \ 3 5 This composition of rotations (RR on the left then LL on the top node) is called a LR "double rotation". There is also an RL double rotation that is symmetric. As you can see, these rotations can be used to rebalance a tree after it becomes unbalanced as a result of insertion or deletion. Define the "height balance" at a node to be (ld - rd), the depth of the left subtree minus the depth of the right subtree. Thus if the right side is deeper, the height balance will be negative and if the left side is deeper, it will be positive. A node is "balanced" if the absolute value of its height balance is less than 2. After inserting/deleting a node, we have to calculate the height balance at each node, from the point of insertion/deletion BACK UP TO THE ROOT. If a node is not balanced along this path, we need to apply a rotation to rebalance it. How do we know what type of rotation to apply? The algorithm is as follows: *** A. Determine if we need a LL/LR or RR/RL rotation: If the height balance is less than -1, we apply RR or RL; if it's greater than 1, apply LL or LR B. To determine if we must apply a LL or LR, we look at the height balance of the left child: if it's positive (deeper on the left again), apply LL ;if it's negative, apply LR. The determination of RR or RL is analogous (formulate it yourself). ================ 3. Fully modify the Bst implementation to be that of an AVL tree: after each recursive call to insert/delete (and delmax), recompute the height of subtrees, check the balance and apply the appropriate rotation if necessary. You can just replace all calls to setheight() with calls to a new procedure void balance() that folds in setheight, checks the balance, and apply the appropriate rotation if needed. You may need to call setheight at the beginning as well as the end of this procedure. setheight() is a constant time operation. To apply a double (LR/RL) rotation, you will want to call left.RR() and right.LL(); But here you will need to typecast: ((Vertex)left).RR(); YOUR balance() PROCEDURE MUST ALSO RUN IN O(1) TIME. If correctly implemented, your insert and delete functions will have the WORST CASE structure T(n) = T(n/2) + 1, which has solution in O(log n). ================ 4. (challenge - optional). 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 to the root from the left and the node farthest to 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. Consider the following example: 6 / \ 5 2 \ 7 \ 8 \ 9 \ 10 Note that the right-most node (10) may be on the left subtree of the root! The horizontal distance of the node containing 10 is +3, because we go once left and four times right to reach it. The width of this tree is |-1 - 3| = 4. Devise and implment an algorithm for your interfaces and classes that return the width of a tree. 4b. My BstDisplay.java program draws a graphical representation of binary trees. It takes into account the height/depth of the tree to make best use of the vertical space available. But it doesn't take into account the width: the root node is always at the middle (horizontally). If there's only 1 node on the left and several on the right, for example, then the horizontal space is not used proportionally. Rewrite the program to better use horizontal spacing (better to test this program on unbalanced trees). You will have to figure out the graphical coordinate calculations yourself.