Untitled

package LAB8;

public class AVLTree {

    Node rootNode;

    // Returns the height of the given treeNode
    int getHeight(Node treeNode) {
        if (treeNode == null)
            return 0;
        return treeNode.height;
    }

    // Returns the maximum of two integer values, firstValue and secondValue
    int getMax(int firstValue, int secondValue) {
        return (firstValue > secondValue) ? firstValue : secondValue;
    }

    // Performs a right rotation on the subtree rooted at the parent node
    // and returns the new root of the subtree
    Node rotateRight(Node parent) {
        Node child = parent.left;
        Node subtree = child.right;

        child.right = parent;
        parent.left = subtree;

        parent.height = getMax(getHeight(parent.left), getHeight(parent.right)) + 1;
        child.height = getMax(getHeight(child.left), getHeight(child.right)) + 1;

        return child;
    }

    // Performs a left rotation on the subtree rooted at the parent node
    // and returns the new root of the subtree
    Node rotateLeft(Node parent) {
        Node child = parent.right;
        Node subtree = child.left;

        child.left = parent;
        parent.right = subtree;

        parent.height = getMax(getHeight(parent.left), getHeight(parent.right)) + 1;
        child.height = getMax(getHeight(child.left), getHeight(child.right)) + 1;

        return child;
    }

    // Returns the balance factor of the given treeNode (difference between the
    // height of the left subtree and the height of the right subtree)
    int getBalance(Node treeNode) {
        if (treeNode == null)
            return 0;
        return getHeight(treeNode.left) - getHeight(treeNode.right);
    }

    // Inserts a new node with the given key into the AVL tree rooted at the currentNode,
    // balances the tree, and returns the new root of the subtree
    Node insert(Node currentNode, int key) {
        if (currentNode == null)
            return (new Node(key));

        if (key < currentNode.key)
            currentNode.left = insert(currentNode.left, key);
        else if (key > currentNode.key)
            currentNode.right = insert(currentNode.right, key);
        else
            return currentNode;

        currentNode.height = 1 + getMax(getHeight(currentNode.left), getHeight(currentNode.right));

        int balance = getBalance(currentNode);

        if (balance > 1 && key < currentNode.left.key)
            return rotateRight(currentNode);

        if (balance < -1 && key > currentNode.right.key)
            return rotateLeft(currentNode);

        if (balance > 1 && key > currentNode.left.key) {
            currentNode.left = rotateLeft(currentNode.left);
            return rotateRight(currentNode);
        }

        if (balance < -1 && key < currentNode.right.key) {
            currentNode.right = rotateRight(currentNode.right);
            return rotateLeft(currentNode);
        }

        return currentNode;
    }

    // Performs a pre-order traversal of the AVL tree rooted at the treeNode
    // and prints the keys of the nodes
    void preOrderTraversal(Node treeNode) {
        if (treeNode != null) {
            System.out.print(treeNode.key + " ");
            preOrderTraversal(treeNode.left);
            preOrderTraversal(treeNode.right);
        }
    }
}