AVL Tree implementation in java

         AVL Tree -A special type of binary search tree which self balance itself. The condition is the difference between heights of left and right sub trees should be less than one for all nodes.

Program implementation:

It has the following steps to implement the program.

Input : Height and balance factor of a node.

Logic:

• Read the height and balance factor.
• Rotate the tree as right side.
• Next, rotate it in the left side.
• Insert the key value according to it.
• There are four types to AVL balancing.
• Left Left Case,Right Right Case, Left Right Case, Right Left Case.
• Finally, call the inorder() function to print the tree by inorder traversal.

Java Implementation Of AVL Tree:

class AVL_Node {

    int key, ht;

    AVL_Node c_left, c_right;

    AVL_Node(int d) {

        key = d;

        ht = 1;

    }

}

class AVLTreeEg {

    AVL_Node root;

    int height(AVL_Node N) {

        return (N == null) ? 0 : N.ht;

    }

    int getBalance(AVL_Node N) {

        return (N == null) ? 0 : height(N.c_left) - height(N.c_right);

    }

    AVL_Node rightRotate(AVL_Node y) {

        AVL_Node x = y.c_left;

        AVL_Node T2 = x.c_right;

        x.c_right = y;

        y.c_left = T2;

        y.ht = Math.max(height(y.c_left), height(y.c_right)) + 1;

        x.ht = Math.max(height(x.c_left), height(x.c_right)) + 1;

        return x;

    }

    AVL_Node leftRotate(AVL_Node x) {

        AVL_Node y = x.c_right;

        AVL_Node T2 = y.c_left;

        y.c_left = x;

        x.c_right = T2;

        x.ht = Math.max(height(x.c_left), height(x.c_right)) + 1;

        y.ht = Math.max(height(y.c_left), height(y.c_right)) + 1;

        return y;

    }

    AVL_Node insert(AVL_Node node, int key) {

        if (node == null)

            return new AVL_Node(key);

        if (key < node.key)

            node.c_left = insert(node.c_left, key);

        else if (key > node.key)

            node.c_right = insert(node.c_right, key);

        else

            return node;

        node.ht = 1 + Math.max(height(node.c_left), height(node.c_right));

        int balance = getBalance(node);

        if (balance > 1 && key < node.c_left.key)

            return rightRotate(node);

        if (balance < -1 && key > node.c_right.key)

            return leftRotate(node); 

        if (balance > 1 && key > node.c_left.key) {

            node.c_left = leftRotate(node.c_left);

            return rightRotate(node);

        } 

        if (balance < -1 && key < node.c_right.key) {

            node.c_right = rightRotate(node.c_right);

            return leftRotate(node);

        }

        return node;

    }

    void inOrder(AVL_Node node) {

        if (node != null) {

            inOrder(node.c_left);

            System.out.print(node.key + " ");

            inOrder(node.c_right);

        }

    }

    public static void main(String[] args) {

        AVLTreeEg t1 = new AVLTreeEg();

        t1.root = t1.insert(t1.root, 110);

        t1.root = t1.insert(t1.root, 201);

        t1.root = t1.insert(t1.root, 320);

        t1.root = t1.insert(t1.root, 140);

        t1.root = t1.insert(t1.root, 530);

        t1.root = t1.insert(t1.root, 250);

        System.out.println("Inorder traversal of AVL tree is given below:");

        t1.inOrder(t1.root);

    }

}

Output:

C:\raji\blog>javac AVLTreeEg.java

C:\raji\blog>java AVLTreeEg

Inorder traversal of AVL tree is given below:

110 140 201 250 320 530

This is the way to implement AVL Tree in java. Keep coding!!!!!