Implements AVL Tree data structure that stores integer values. If AVL Tree becomes unbalanced, Tree will rebalance itself using single or double rotations depending on where the violation occurs.

AVL Tree

/*
 * Implements AVL Tree data structure that stores integer values. If AVL Tree becomes unbalanced,
 * Tree will rebalance itself using single or double rotations depending on where the violation occurs.
 *
 */
 
public class AVLTreeNode {

    private AVLTreeNode left;
    private AVLTreeNode right;
    private int value;
    //Flag for lazy deletion
    private boolean deleted;
    private int height;

    /**
     * Public getter for left subtree
     *
     * @return AVLTreeNode for left subtree
     */
    public AVLTreeNode getLeft() {
        return this.left;
    }

    /**
     * Public getter for right subtree
     *
     * @return AVLTreeNode for right subtree
     */
    public AVLTreeNode getRight() {
        return this.right;
    }

    /**
     * Public getter for value stored in this node
     *
     * @return value stored in this node
     */
    public int getValue() {
        return this.value;
    }

    /**
     * Constructor to initialize an AVLTreeNode with a given integer value and no children.
     *
     * @param value an integer value to store in the newly created AVLTreeNode
     */
    public AVLTreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.deleted = false;
        this.height = 0;
    }

    /**
     * Inserts a new node with value into the AVL Tree, and re-balances the tree if necessary. Does nothing
     * if a node containing value is already present in the tree.
     *
     * @param value an integer value to insert
     * @return the root of the tree after the insertion (in case the re-balancing altered the root node)
     */
    public AVLTreeNode insert(int value) {

        if (this.value == value) {
            // if value had been deleted, undelete it to show
            this.deleted = false;
            return this;
        }

        // If the subtree where the node is to be inserted is empty, then insert it
        if (this.value < value && this.right == null) {
            this.right = new AVLTreeNode(value);
        }

        // If subtree is not empty call insert with right node
        if (this.value < value){
            this.right = this.right.insert(value);
            // if unbalanced do a rotation
            if(height(this.left) - height(this.right) == -2){
                // node was inserted on the outside. Do single rotation
                if(value >= this.right.value) {
                    return singleRotationRightSide(this);
                }
                // node was inserted on the inside. Do double rotation
                else {
                    return doubleRotationRightSide(this);
                }
            }
        }

        // If the subtree where the node is to be inserted is empty, then insert it
        if (this.value > value && this.left == null) {
            this.left = new AVLTreeNode(value);
        }

        // If subtree is not empty call insert with left node
        if (this.value > value){
            this.left = this.left.insert(value);
            // if unbalanced do a rotation
            if(height(this.left) - height(this.right) == 2){
                // node was inserted on the outside. Do single rotation
                if(value <= this.left.value){
                    return singleRotationLeftSide(this);
                }
                // node was inserted on the inside. Do double rotation
                else {
                    return doubleRotationLeftSide(this);
                }
            }
        }
        this.height = Math.max(height(this.left), height(this.right)) + 1;
        return this;
    }

    /**
     * Checks to see if a node containing value is present in the AVL Tree.
     *
     * @param value an integer value to find in AVL Tree
     * @return true if value is found, else false
     */
    public boolean contains(int value) {

        if (this.value == value){
            return true;
        }
        if (this.value < value && this.right != null) {
            return this.right.contains(value);
        }
        else if (this.value > value && this.left != null){
            return this.left.contains(value);
        }
        return false;
    }

    /**
     * Searches for a node containing value and deletes it if present. Performs lazy deletion in order to preserve
     * AVL condition
     *
     * @param value an integer value to delete
     * @return true if a node was deleted, false if no node containing value was present
     */
    public boolean delete(int value) {
        if (this.value == value) {
            if(this.deleted == false) {
                this.deleted = true;
                return true;
            }
            else return false;
        }

        if (this.value < value && this.right != null){
            return this.right.delete(value);
        }

        else if (this.value > value && this.left != null){
            return this.left.delete(value);
        }
        return false;
    }

    /**
     * Determine the height of the given tree node.
     *
     * @param t AVL Tree Node to get height of
     * @return Height of the given Tree Node.
     */
    private int height (AVLTreeNode t){
        if(t == null) {
            return -1;
        }
        return t.height;
    }

    /**
     * If inserted node on the left left side creates an unbalanced tree, do a single rotation.
     * Left Child becomes New Root, and Old Root now becomes right child of New Root.
     *
     * @param t unbalanced AVL Tree
     * @return balanced AVL Tree
     */
    private static AVLTreeNode singleRotationLeftSide(AVLTreeNode t){
        AVLTreeNode newTree = t.left;
        t.left = newTree.right;
        newTree.right = t;
        return newTree;
    }

    /**
     * If inserted node on the left right side creates an unbalanced tree, do a double rotation.
     * Right child of the original Root's left child becomes the new root.
     * The old root becomes the right child of the new root.
     * The old root's left child becomes the new roots left child.
     *
     * @param t unbalanced AVL Tree
     * @return balanced AVL Tree
     */
    private static AVLTreeNode doubleRotationLeftSide(AVLTreeNode t) {
        t.left = singleRotationRightSide(t.left);
        return singleRotationLeftSide(t);
    }

    /**
     * If inserted node on the right right side creates an unbalanced tree, do a single rotation.
     * Right Child becomes New Root, and Old Root now becomes left child of New Root.
     *
     * @param t unbalanced AVL Tree
     * @return balanced AVL Tree
     */
    private static AVLTreeNode singleRotationRightSide(AVLTreeNode t){
        AVLTreeNode newTree = t.right;
        t.right = newTree.left;
        newTree.left = t;
        return newTree;
    }

    /**
     * If inserted node on the right left side creates an unbalanced tree, do a double rotation.
     * Left child of the Root's right child becomes the new root.
     * The old root becomes the left child of the new root.
     * The old root's right child becomes the new roots right child.
     *
     * @param t unbalanced AVL Tree
     * @return balanced AVL Tree
     */
    private static AVLTreeNode doubleRotationRightSide(AVLTreeNode t) {
        t.right = singleRotationLeftSide(t.right);
        return singleRotationRightSide(t);
    }

    ///////// prefix traversal ///////////
    /* Used for testing to see trees structure.
     * Prints out calling trees nodes in prefix order. Root -> left -> right traversal.
     */
    private void printTree(){
        if(this == null) {
            return;
        }
        System.out.print(this.value + " ");
        if(this.left != null) {
            this.left.printTree();
        }
        if(this.right != null) {
            this.right.printTree();
        }
    }

}