COP 3530 Section U03 Spring 2017 The AVL Trees ------------- I. The AvlNode.java Class: -------------------------- public class AvlNode> { // the fields private T element; private AvlNode left; private AvlNode right; private int height = 0; // the constructors public AvlNode(T elem) { element = elem; } // form an AVL node when we know the element and the subtrees public AvlNode(T elem, AvlNode lt, AvlNode rt) { element = elem; left = lt; right = rt; } // return the height of the node t private int height( AvlNode t) { return t == null ? -1 : t.height; } // insert a value into a subtree // x is the value to be inserted // t is the root of the subtree // return the new root of the subtree public AvlNode insert(T x, AvlNode t) { if (t == null) return new AvlNode<>(x,null,null); int compareResult = x.compareTo(t.element); if (compareResult < 0 ) t.left = insert(x,t.left); else if (compareResult > 0 ) t.right = insert(x,t.right); else ; // duplicate, do nothing return balance(t); } private static final int ALLOWED_IMBALANCE = 1; // assume that either t is balanced or within one of being balanced private AvlNode balance(AvlNode t) { if (t == null) return null; if (height (t.left ) - height(t.right) > ALLOWED_IMBALANCE ) if (height(t.left.left ) >= height(t.left.right) ) t = rotateWithLeftChild(t); else t = doubleWithLeftChild(t); else if (height (t.right ) - height(t.left) > ALLOWED_IMBALANCE ) if (height(t.right.right ) >= height(t.right.left) ) t = rotateWithRightChild(t); else t = doubleWithRightChild(t); t.height = Math.max(height(t.left), height(t.right)) + 1; return t; } // rotate binary tree with left child private AvlNode rotateWithLeftChild(AvlNode k2) { AvlNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = Math.max(height(k2.left), height(k2.right)) + 1; k1.height = Math.max(height(k1.left), k2.height) + 1; return k1; } // double rotate with left child private AvlNode doubleWithLeftChild(AvlNode k3) { k3.left = rotateWithRightChild( k3.left); return rotateWithLeftChild(k3); } // rotate binary tree with left child private AvlNode rotateWithRightChild(AvlNode k2) { AvlNode k1 = k2.right; k2.right = k1.left; k1.left = k2; k2.height = Math.max(height(k2.left), height(k2.right)) + 1; k1.height = Math.max(height(k1.right), k2.height) + 1; return k1; } // double rotate with left child private AvlNode doubleWithRightChild(AvlNode k3) { k3.right = rotateWithLeftChild( k3.right); return rotateWithRightChild(k3); } // remove x from the subtree t public AvlNode remove (T x, AvlNode t) { if (t == null) return t; // x was not found int compareResult = x.compareTo(t.element); if (compareResult < 0) t.left = remove(x, t.left); else if (compareResult > 0) t.right = remove(x, t.right); else if (t.left != null && t.right != null) // two children { t.element = findMin(t.right).element; t.right = remove(t.element, t.right); } else t = (t.left != null) ? t.left : t.right; return balance(t); } // find the node with the smallest value private AvlNode findMin(AvlNode t) { if (t == null) return null; else if (t.left == null) return t; else return findMin(t.left); } // end findMin // print in preorder public void printInOrder() { if (left != null) left.printInOrder(); System.out.println("Data = " + element + ", height = " + height); if (right != null) right.printInOrder(); } } II. The Driver: --------------- // the code is a modification of Weiss's book, pp 433-436 public class AvlTrees { // test the AVL trees public static void main(String[] args) { System.out.println("Test the AVL Trees"); System.out.println("==================\n\n"); System.out.println("Add in thid order, Ali Baba, Papa Bill, Poco Pelo, Shrek,"); System.out.println(" Papa Smurf, Geoff the Cheff, Atrevido, Papa Bill, Bruja,"); System.out.println("Tornado, Pepito, Dominatrix, Ming the Merciless"); AvlNode root = new AvlNode<>("Ali Baba"); root = root.insert("Papa Bill", root); root = root.insert("Poco Pelo", root); root = root.insert("Shrek", root); root = root.insert("Papa Smurf", root); root = root.insert("Geoff the Cheff", root); root = root.insert("Atrevido", root); root = root.insert("Papa Bill", root); root = root.insert("Bruja", root); root = root.insert("Tornado", root); root = root.insert("Pepito", root); root = root.insert("Dominatrix", root); root = root.insert("Ming the Merciless", root); System.out.println("\nAfter the insertions, the tree in inorder is: "); root.printInOrder(); // let's test delete System.out.println("\nWe delete, in this order, Geoff the Cheff, Poco Pelo," + "Papa Bill, Poco Pelo"); root = root.remove("Geoff the Cheff", root); root = root.remove("Poco Pelo", root); root = root.remove("Papa Bill", root); root = root.remove("Poco Pelo", root); System.out.println("\nAfter the deletions, the tree in inorder is: "); root.printInOrder(); } } III. The Output: ---------------- run: Test the AVL Trees ================== Add in thid order, Ali Baba, Papa Bill, Poco Pelo, Shrek, Papa Smurf, Geoff the Cheff, Atrevido, Papa Bill, Bruja, Tornado, Pepito, Dominatrix, Ming the Merciless After the insertions, the tree in inorder is: Data = Ali Baba, height = 0 Data = Atrevido, height = 1 Data = Bruja, height = 0 Data = Dominatrix, height = 2 Data = Geoff the Cheff, height = 1 Data = Ming the Merciless, height = 0 Data = Papa Bill, height = 3 Data = Papa Smurf, height = 1 Data = Pepito, height = 0 Data = Poco Pelo, height = 2 Data = Shrek, height = 1 Data = Tornado, height = 0 We delete, in this order, Geoff the Cheff, Poco Pelo,Papa Bill, Poco Pelo After the deletions, the tree in inorder is: Data = Ali Baba, height = 0 Data = Atrevido, height = 1 Data = Bruja, height = 0 Data = Dominatrix, height = 2 Data = Ming the Merciless, height = 0 Data = Papa Smurf, height = 3 Data = Pepito, height = 0 Data = Shrek, height = 1 Data = Tornado, height = 0 BUILD SUCCESSFUL (total time: 0 seconds)