AVL Tree Implementation

Write pseudocode for the AVL tree methods Balance, RotateLeft, and RotateRight. Assume that the rest of the data structure is implemented as in the Java code here. Note you are not required to write your solution in Java, pseudocode is sufficient.

import java.util.NoSuchElementException; public class AVLTree { private Node root; public AVLTree() { this.root = null; } private static class Node { int value; Node left; Node right; int height; public Node(int value, Node left, Node right) { this.value = value; this.left = left; this.right = right; height = 0; } public Node(int value) { this(value, null, null); } } // Helper function to get the height of a node in // an AVL tree. Handles the case of null trees // having height -1 for the purposes of calculating balance private static int height(Node t) { if (t == null) { return -1; } else { return t.height; } } public boolean isEmpty() { return root == null; } public boolean contains(int value) { return contains(value, root); } private boolean contains(int value, Node t) { if (t == null) { return false; } if (value < t.value) { return contains(value, t.left); } else if (value > t.value) { return contains(value, t.right); } else { return true; } } public int findMin() { if (isEmpty()) { throw new NoSuchElementException(); } return findMin(root).value; } // An example of recursively finding the min private Node findMin(Node t) { if (t == null) { return null; } else if (t.left == null) { return t; } return findMin(t.left); } public int findMax() { if (isEmpty()) { throw new NoSuchElementException(); } return findMax(root).value; } // An example of iteratively finding the max private Node findMax(Node t) { if (t != null) { while (t.right != null) { t = t.right; } } return t; } public void insert(int value) { insert(value, root); } private Node insert(int value, Node t) { if (t == null) { return new Node(value); } if (value < t.value) { t.left = insert(value, t.left); } else if (value > t.value) { t.right = insert(value, t.right); } else { // Do nothing - nodes are unique } return balance(t); // For a plain BST this line would be "return t;" } /** * Uses tree rotation (if necessary) to re-balance the subtree rooted * at t. This operation should be O(1). At the end of this function, the * height field of node t and all of its descendants must be correct. * @param t the root of the subtree to be balanced * @return A balanced subtree containing the same nodes as the original subtree */ private Node balance(Node t) { if (t == null) { return t; } if (/* TODO: condition for subtree too tall */) { if (/* TODO: Condition for left-right case (kink case) */ ) { // TODO: Turn into left-left case (line case) } //TODO: Handle left-left case } else if (/* TODO: condition of right subtree too tall*/) { if (// TODO: Condition for right-left case (kink case)) { // TODO: Make into right-right case (line case) } // TODO - Handle right-right case (line case) } // TODO: Any extra work necessary to correct the tree return t; } private Node rotateLeft(Node t) { /* * TODO: Implement a left rotation. The diagram below illustrates an example. t x / \ / \ a x ===> t c / \ / \ b c a b */ } private Node rotateRight(Node t) { // TODO - Implement a right rotation } public int remove(int value) { return remove(value, this.root).value; } // This differs from the version we worked on in class in that it // does not use lazy deletion. private Node remove(int value, Node t) { if (t == null) { return t; } if (value < t.value) { t.left = remove(value, t.left); } else if (value > t.value) { t.right = remove(value, t.right); } else if (t.left != null && t.right != null) { t.value = findMin(t.right).value; t.right = remove(t.value, t.right); } else { t = (t.left != null) ? t.left : t.right; } return balance(t); // For a plain BST this line would be "return t;" } }