CSC 17 Lab: AVL Balanced Binary Search Trees This lab will continue with the subclasses that you have been writing to implement AVL trees, which are balanced. With such a tree, the operations of search, insert and delete are all worst-case O(log n). The one disadvantage of this data structure is its difficulty in handling duplicate values, so these trees are usually used to implement sets. The principal part of the assignment is to override the procedure in the vertex superclass called 'adjust', which calls setheight after each recursive call to insert, delete and delmax (these are the procedures that can alter the tree. The new version of this procedure will need to "rotate" the tree after each insert/delete to re-balance it if necessary. However, to do this you will first have to implement several other procedures: all of these should be in your vertex subclass (extvertex). 1. Implement the following basic "rotation" procedures in the subclass of vertex (extvertex): 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 ll, lr and r represent arbitrary subtrees (left-left, left-right and right). Don't confuse the name 'LL' rotation with the lable 'll' for left-of-left. 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. 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 can construct a new vertex for the new right-subtree. HINT: The left subtree is of static type Tree. You cannot refer to left.item or left.left, left.right without type casting it first: extvertex lvert = (extvertex)left; now you can refer to lvert.item, lever.left, etc. alternatively, you can inline the type cast, for example: if (!left.empty()) y = ((extvertex)left).item There may be similar points in your code where type casting is needed: but don't type cast unless you're sure there's not going to be a runtime error. For example, you should not (and shouldn't need to) type cast right to extvertex in the LL rotation, because the right pointer could point to nil. **Your procedure should call setheight() at the end because the height at 'this' vertex may change afer the rotation (but only on the vertex the rotation was applied to - not the entre tree). /////////////// IMPORTANT: /////////////// *****Your procedure must run in O(1): constant time relative to the size of the tree. DO NOT USE LOOPS AND DO NOT MAKE LL() RECURSIVE. ****** 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 -------- 1b (Optional): it's possible to write LL() and RR() without creating a new vertex. Instead when doing LL you can reuse the vertex (extvertex) structure for the left subtree to become the right subtree. It's just a matter of swaping things carefully in the right order. This will result in better memory efficiency (less work for the memory manager). --------------------------------------------------------- AVL ALGORITHM OVERVIEW: 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 to LR (LL on the right subtree then RR on the top). 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 (height) 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 (right side is too deep), we apply RR or RL. If it's greater than 1 (left side too deep), apply LL or LR B. To determine if we must apply a LL or LR (if left side is too deep), 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. In other words, if lvert.left.height()>=lvert.right.height(), apply LL, other wise apply LR (first apply RR to lvert, then apply LL to "this"). The determination of RR or RL is analogous, when ld-rd < -1: extvertex rvert = (extvertex)right; // cast will work because rd>ld if rvert.right.height() >= rvert.left.height(), apply RR else apply RL. ================ 2. @Override the adjust() procedure to more than just set the height but to balance the tree by applying rotations if necessary. This procedure should set the height at the beginning and at the end. It should check the height balance (conveniently returned by the existing setheight function), and apply the appropritae rotation to balance the tree at that node. YOUR adjust() PROCEDURE MUST ALSO RUN IN O(1) TIME (no loops or recursive calls). ****Remember, whenever a tree's left or right sub tree changes destructively, you need to call setheight to properly adjust the height. To apply a double (LR/RL) rotation, you will want to call left.RR() and right.LL(); But here again you will need to typecast: ((extvertex)left).RR(); All three procedures, LL(), RR() and adjust(), should be in your extvertex subclass. ================ 3. Use the BstGraph program to verify that you have balanced trees. You can use the following ////////// from file "avltest.java": ////////////////////////// // use this program to test your AVL tree implementation. // Change the name of the class 'AVLTree' to that of your outer class. import java.util.Scanner; import java.awt.event.WindowEvent; public class avltest { public static void main(String[] av) { int n = 10; if (av.length>0) n = Integer.parseInt(av[0]); BinSearchTree tree; tree = new ExtBst(); // MAY HAVE TO CHANGE CLASS NAME //tree.setComparator( (x,y)->y.compareTo(x) ); // invert comparator while(n-->0) tree.add((int)(Math.random()*n*n)); System.out.println(tree); // prints in-order BstGraph W = new BstGraph(1024,768); W.draw(tree); // interactive loop Scanner scin = new Scanner(System.in); String req = ""; // user request do { System.out.print("add n or del n or quit: "); req = scin.next(); // read next token if (req.equals("add")) tree.add(scin.nextInt()); else if (req.equals("del")) tree.remove(scin.nextInt()); W.draw(tree); } while (req.equals("add") || req.equals("del")); System.out.println("size: "+tree.size()); System.out.println("height: "+tree.depth()); System.out.println("is binary search tree: "+tree.checkbst()); W.dispatchEvent(new WindowEvent(W, WindowEvent.WINDOW_CLOSING)); }//main }//avltest ///////safe to file avltest.java ///////////////////////////// 4. (maybe optional) What you have implemented can be called an "AVL Set". It stores values like a HashSet, but using different methods to insert/delete. You can also adopt your program to implement an AVLMAP, which would map keys to values like in a HashMap. The keys must be comparable and an AVLMAP cannot contain duplicate keys, but different keys can be associated with the same value. Your class should have the following outline: class AVLMap, VT> { public void set(KT key, VT val) // inserts or changes key mapping to val public VT get(KT key) // returns value associated with key, null if none public VT remove(KT key) // remove mapping for key, returns previous val } This class should NOT extend your AVL tree class, but should "adopt" it to be used like a map. You just need to store objects of the following form into your AVL "set". class kvpair implements Comparable //internal class of AVLMap { KT key; VT val; public kvpair(KT k, VT v) { key=k; val=v; } public int compareTo(kvpair other) {return key.compareTo(other.key); } public String toString() {return key+":"+val; } }//kvpair You shouldn't have to reimplement the most of the functions except for insert, because when you find a vertex with a duplicate key, you need to replace the value it maps to with a new value (set can add as well as change a key-value pair). Your class should behave similarly to java.util.TreeMap, which uses another type of balanced binary search trees underneath called "Red-Black trees." Red-black trees require fewer rotations after insert/delete, but AVL trees are more strictly balanced (with lower height values). In a Red-black tree, the depth of one subtree can be up to twice as much as the other tree. AVL trees give slightly better performance for search. AVL trees require the height balance to be stored in each vertex, therefore requiring a little more memory. It's argued that Red-black trees are faster for insert/delete but I don't believe it. It may be faster for one particular implementation but you can always fine-tune your program to perform a little faster: for example, at most one rotation (of the 4) is needed after an insert, so there's no need to check the height balances afterwards. AVL trees are found in the implementations of databases.