AVL TREES CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Example :

class Node {
    int data;
    Node left;
    Node right;
    int height;
    int size;
    
    public Node(int value) {
        data = value;
        left = right = null;
        height = 1;
    }
}
    
public class AVLTree {
    
    private Node leftRotate(Node rootNode){
    
        Node newRoot = rootNode.right;
        rootNode.right = rootNode.right.left;
        newRoot.left = rootNode;
        rootNode.height = setHeight(rootNode);
        rootNode.size = setSize(rootNode);
        newRoot.height = setHeight(newRoot);
        newRoot.size = setSize(newRoot);
        return newRoot;
    }
    
    private Node rightRotate(Node rootNode){
    
        Node newRoot = rootNode.left;
        rootNode.left = rootNode.left.right;
        newRoot.right = rootNode;
        rootNode.height = setHeight(rootNode);
        rootNode.size = setSize(rootNode);
        newRoot.height = setHeight(newRoot);
        newRoot.size = setSize(newRoot);
        return newRoot;
    }
    
    private int setSize(Node rootNode) {
    
        if(rootNode == null) {
            return 0;
        }
        return 1 + Math.max((rootNode.left != null ? rootNode.left.size : 0), (rootNode.right != null ? rootNode.right.size : 0));
    }
    
    public Node insert(Node rootNode, int data){
    
        if (rootNode == null) {
            rootNode = new Node(data);
            return rootNode;
        }
    
        if (data < rootNode.data)
            rootNode.left = insert(rootNode.left, data);
        else if (data > rootNode.data)
            rootNode.right = insert(rootNode.right, data);
    
    
        int balanceFactor = balance(rootNode.left, rootNode.right);
    
        if(balanceFactor > 1) {
    
            if(height(rootNode.left.left) >= height(rootNode.left.right)){
    
                rootNode = rightRotate(rootNode);
            } else {
    
                rootNode.left = leftRotate(rootNode.left);
                rootNode = rightRotate(rootNode);
            }
        } else if(balanceFactor < -1){
    
            if(height(rootNode.right.right) >= height(rootNode.right.left)){
    
                rootNode = leftRotate(rootNode);
            } else {
    
                rootNode.right = rightRotate(rootNode.right);
                rootNode = leftRotate(rootNode);
            }
        }
        else{
    
            rootNode.height = setHeight(rootNode);
            rootNode.size = setSize(rootNode);
        }
        return rootNode;
    }
    
    private int balance(Node rootNodeLeft, Node rootNodeRight){
        return height(rootNodeLeft) - height(rootNodeRight);
    }
    
    private int setHeight(Node rootNode){
    
        if(rootNode == null) {
            return 0;
        }
        return 1 + Math.max((rootNode.left != null ? rootNode.left.height : 0), (rootNode.right != null ? rootNode.right.height : 0));
    }
    
    private int height(Node rootNode) {
    
        if(rootNode == null){
            return 0;
        } else {
            return rootNode.height;
        }
    }
    
    
    public static void main(String args[]) {
    
        AVLTree avlTree = new AVLTree();
        Node root = null;
        root = avlTree.insert(root, 16);
        root = avlTree.insert(root, 10);
        root = avlTree.insert(root, 25);
        root = avlTree.insert(root, 2);
        root = avlTree.insert(root, 13);
        root = avlTree.insert(root, 18);
        root = avlTree.insert(root, 30);
        root = avlTree.insert(root, 7);
        root = avlTree.insert(root, 8);
    
        TreeTraversal tt = new TreeTraversal();
        System.out.println("Inorder Traversal : \n");
        tt.inOrder(root);
    }
}
    
class TreeTraversal {
    
    Node root;
    
    TreeTraversal() {
    
        root = null;
    }
    
    void inOrder(Node node) {
    
        if (node != null) {
    
            inOrder(node.left);
            System.out.print(node.data + "  ");
            inOrder(node.right);
        }
    }
}

Output :

Inorder Traversal :

2 7 8 10 13 16 18 25 30

So, we will constructing the below Balanced Binary Search Tree, by inserting the elements one by one.

And we have the below methods :

Node insert(Node root, int key)

This method is used to insert a new Node to the Binary Search Tree. Then balance it as per the rules of AVL Tree.
Node leftRotate(Node rootNode)

This method is used to Left Rotate the Binary Search Tree in order to balance it as per the rules of AVL Tree.
Node rightRotate(Node rootNode)

This method is used to Right Rotate the Binary Search Tree in order to balance it as per the rules of AVL Tree.
int balance(Node rootNodeLeft, Node rootNodeRight)

As the name suggests, this method is used to balance the Binary Search Tree as per the rules of AVL Tree.
int setHeight(Node rootNode) and int height(Node rootNode)

As we know an AVL Tree is a height balanced Binary Search Tree. And the 'int setHeight(...)' and 'int height(...)' are the methods where the height of the AVL Tree is calculated.

Code explanation for AVL Tree :

Firstly, we would be constructing the above Binary Search Tree, with the help of insert method.

Node root = null;
root = avlTree.insert(root, 16);

Initially, the variable 'root' is 'null'. So, we take the element i.e. 16 in this case. And pass the 'root' and the element '16' to the insert method.

Node insert(Node rootNode, int data){

    if (rootNode == null) {
        rootNode = new Node(data);
        return rootNode;
    }

    if (data < rootNode.data)
        rootNode.left = insert(rootNode.left, data);
    else if (data > rootNode.data)
        rootNode.right = insert(rootNode.right, data);


    int balanceFactor = balance(rootNode.left, rootNode.right);

    if(balanceFactor > 1) {

        if(height(rootNode.left.left) >= height(rootNode.left.right)){

            rootNode = rightRotate(rootNode);
        } else {

            rootNode.left = leftRotate(rootNode.left);
            rootNode = rightRotate(rootNode);
        }
    } else if(balanceFactor < -1){

        if(height(rootNode.right.right) >= height(rootNode.right.left)){

            rootNode = leftRotate(rootNode);
        } else {

            rootNode.right = rightRotate(rootNode.right);
            rootNode = leftRotate(rootNode);
        }
    }
    else{

        rootNode.height = setHeight(rootNode);
        rootNode.size = setSize(rootNode);
    }
    return rootNode;
}

The first line of the 'insert(...)' checks if the 'rootNode' is null or not.

if (rootNode == null) {
    rootNode = new Node(data);
    return rootNode;
}

And in this case 'rootNode' is null. So, we create a new Node object with the 'data' i.e. 16. And the Node object is created with the below constructor.

public Node(int value) {
    data = value;
    left = right = null;
    height = 1;
}

Then assign it to the 'Node' object 'root'.

And return the Node 'root'.

return root;

In the next line we try to insert the element '13' in the Binary Search Tree using the 'insert(...)' method.

    root = avlTree.insert(root, 10);

And the 'insert(...)' method is called.

And in the similar way we check,

if (data < rootNode.data)
    rootNode.left = insert(rootNode.left, data);
else if (data > rootNode.data)
    rootNode.right = insert(rootNode.right, data);

If the 'data' i.e. 13 is less than the root element 'root.data'. And the first condition matches.

if (data < rootNode.data)
    rootNode.left = insert(rootNode.left, data);

And a recursive call is made to 'insert(...)' method.

    rootNode.left = insert(rootNode.left, data);

So, the method executes and sets the value of 'rootNode.left' with this Node that contains '13'.

And since we are dealing with AVL tree, it is time to calculate the Balance Factor.

    int balanceFactor = balance(rootNode.left, rootNode.right);

And the 'balance(...)' method is called.

int balance(Node rootNodeLeft, Node rootNodeRight){
    return height(rootNodeLeft) - height(rootNodeRight);
}

And the 'balance(...)' method is quite simple to understand. It calls the 'height(...)' method for the Left Node and Right Node and calculates the difference between Left and Right Node.

And as we know, 'Balance Factor' is the difference of Left and Right Node.

And now since we got the 'Balance Factor', we need to perform Left or Right rotation if the value of 'Balance Factor' is other than -1, 0 or 1.

if(balanceFactor > 1) {

    if(height(rootNode.left.left) >= height(rootNode.left.right)){

        rootNode = rightRotate(rootNode);
    } else {

        rootNode.left = leftRotate(rootNode.left);
        rootNode = rightRotate(rootNode);
    }
} else if(balanceFactor < -1){

    if(height(rootNode.right.right) >= height(rootNode.right.left)){

        rootNode = leftRotate(rootNode);
    } else {

        rootNode.right = rightRotate(rootNode.right);
        rootNode = leftRotate(rootNode);
    }
}
else{

    rootNode.height = setHeight(rootNode);
    rootNode.size = setSize(rootNode);
}

So, if the 'Balance Factor' is greater than '1'.

if(balanceFactor > 1) {

    if(height(rootNode.left.left) >= height(rootNode.left.right)){

        rootNode = rightRotate(rootNode);
    } else {

        rootNode.left = leftRotate(rootNode.left);
        rootNode = rightRotate(rootNode);
    }
}

We go to the left child of the 'rootNode' and try checking, if the height of the left child of the left node is greater than the height of the right child of the left node.

if(height(rootNode.left.left) >= height(rootNode.left.right)){

    rootNode = rightRotate(rootNode);
}

If the above condition satisfies, then we can assume that we need to right rotate the tree.

And the 'rightRotate(...)' method is called to balance the tree.

Node rightRotate(Node rootNode){

    Node newRoot = rootNode.left;
    rootNode.left = rootNode.left.right;
    newRoot.right = rootNode;
    rootNode.height = setHeight(rootNode);
    rootNode.size = setSize(rootNode);
    newRoot.height = setHeight(newRoot);
    newRoot.size = setSize(newRoot);
    return newRoot;
}

Let us take the below example to understand the 'rightRotate(...)' method.

Say, 'rootNode' has the element '13'.

Now, we create a Node named 'newNode' and assign the Node 'rootNode.left' to it.

    Node newRoot = rootNode.left;

And as we can see in the above diagram 'rootNode.left' has the element '7' in it.

Then we take the 'rootNode.left.right' (i.e. The right child of '7', which is 'null' in the above case) and assign it to 'rootNode.left'.

    rootNode.left = rootNode.left.right;

And the below tree looks like,

Next, we take the 'rootNode' and assign it as the right child of the newly created Node 'newRoot'.

	newRoot.right = rootNode;

So, the right rotation is performed,

The rest few lines of the method is quite easy to understand.

The height is set by calling the 'setHeight(...)' method.

	rootNode.height = setHeight(rootNode);

And finally, the Node 'newRoot' is returned.

	return newRoot;

And continuing this way we get the below AVL tree.

❮❮ PREV NEXT ❯❯