AVLDriver.java:

public class AVLDriver { public static void add(AVLTree tree, int value) { tree.insert(value); System.out.printf("After insert %d: ", value); tree.print(); System.out.println(""); } public static void main(String[] args) { AVLTree tree = new AVLTree(); System.out.println("Initial:"); tree.print();

// double rotation right /* add(tree, 2); add(tree, 1); add(tree, 6); add(tree, 7); add(tree, 4); add(tree, 3); add(tree, 5); */

// double rotation left: add(tree, 6); add(tree, 7); add(tree, 2); add(tree, 1); add(tree, 4); add(tree, 3); add(tree, 5); } }

AVLNode.java:

public class AVLNode { public AVLNode left = null; public AVLNode right = null; public int value = 0; public AVLNode parent = null;

public AVLNode insert(int newValue) { // perform binary-search style insertion if (newValue

return rebalance(); }

public AVLNode rebalance() { // balance the tree (if necessary) return null; }

public int getBalance() { int rightHeight = 0; if (this.right != null) { rightHeight = this.right.getHeight(); }

int leftHeight = 0; if (this.left != null) { leftHeight = this.left.getHeight(); }

return rightHeight - leftHeight; }

public void print(int depth) { if (this.right != null) { this.right.print(depth + 1); }

for (int i = 0; i

if (this.left != null) { this.left.print(depth + 1); } }

public int getHeight() { int leftHeight = 1; if (left != null) { leftHeight = left.getHeight() + 1; }

int rightHeight = 0; if (right != null) { rightHeight = right.getHeight() + 1; }

return (leftHeight > rightHeight) ? leftHeight : rightHeight; } }

AVLTree.java:

public class AVLTree { private AVLNode root = null;

public AVLTree() { this.root = null; }

public AVLTree(AVLNode root) { this.root = root; }

public void insert(int newValue) { if (root == null) { AVLNode newNode = new AVLNode(); newNode.value = newValue; this.root = newNode; } else { AVLNode newParent = this.root.insert(newValue); if (newParent != null) { this.root = newParent; } } }

public void print() { if (root == null) { System.out.println("null"); } else { System.out.printf("Balance: %d ", this.root.getBalance()); this.root.print(0); } } }

Overview In this lab assignment, we will implement the rebalancing behaviour in an AVL tree. The code implementing much of the other behaviour has been provided. Instructions Download the file lab08_base.zip, and extract as a starting point. The code includes a driver class (AVLDriver), a class for the AVL tree (AVLTree), and a class for the AVL node (AVLNode). There is arn empty function, called rebalance(), that needs to be implemented. The AVLNode class includes a getBalance) method, which returns an integer. If the integer is -2 or less, the left node is out of balance. If the integer is +2 or more, the right node is out of balance. When these two conditions occur, perform either a single or a double rotation (as described in the lecture notes and text book), as appropriate The getBalance() method returns an AVLNode only when the rebalancing occurs on the root node. The return value will be the new root node. This is already handled by the existing code. In all other cases, return null. A summary of rotations is given below. Single, left rotation: Single rotation TO T1 T2 T3 T2 T3