Binary Search Trees – Part 3 AVL-Tree

Hi, in the third part of my tree series, I want to talk about AVL trees. In the second part, we learned what rotations are and why you need them.

What is an AVL-Tree?

An AVL tree is a self-balancing tree, which was developed by the two Soviet mathematicians Georgi Maximovich Adelson-Velski and Yevgeny Mikhailovich Landis. The AVL tree has the peculiarity that the difference in height of the two subtrees must be at most one.

AVL trees guarantee logarithmic runtimes in accesses. No tree can degenerate here.

For example, an AVL tree looks like this.

This tree is an AVL tree, because it fulfills the properties of an AVL tree. Here the height difference is at most 1. The numbers we see outside the nodes are the balance values. The balance values, is the difference, of the height of the left and right subtree of each node.

Balancefactor = height(node.leftTree) - height(node.rightTree)

Let's go through this tree with it. Nodes that have no children have a balance factor of 0.

For node 2, we have 2 child nodes. The height here for the left subtree is 1. For the right subtree, the height is also 1.

If we apply the formula, we get 0 as balance factor, because:
Balancefactor = $1 - 1 = 0$.

This means that node 2 is a balanced subtree.

If we now calculate the balance factor at node 4, we have on the left subtree, a height of 2. The right subtree has a height of 1. The same formula applied, gives a height difference of 1, since:

Balancefactor = $2 - 1 = 1$

The rule of the AVL tree is that the height difference of all subtrees must not exceed 1. Everything that goes beyond this must be corrected, otherwise the tree is considered to be unbalanced.

If we now extend our Tree class with the checkBalance method, we can turn the BST into an AVL tree.

Extending the search tree

The checkBalance method will later check the tree for balance on each insert operation. First, we extend the class with the height method to determine the height of the tree.

public int height()
{
    if(this.root == null)
        return 0;

    return height(this.root);
}

private int height(Node node)
{
    if(node == null)
        return 0;

    int left = height(node.getLeft());
    int right = height(node.getRight());
    if(left > right)
        return left + 1;

    return right + 1;
}

Here we have two methods, one is the public method which allows us to get the total height of the tree. This checks if the tree is empty, if so the tree has a height of 0. If the tree is not empty, the private method is called. Here it is checked whether the current node is a null. If it is, the height at the node is 0. If it is not, the height of both subtrees is determined recursively. At the end the maximum is returned.

What is the benefit of this method? With this method, we determine the balance factor.

Let's take a look at the checkBalance method.

private void checkBalance(Node node)
{
    if(node == null)
        return;

    if(Math.abs(height(node.getLeft()) - height(node.getRight())) > 1)
    {
        System.out.println("Unbalanced tree");
        rebalance(node);
    }

    if(node.getParent() == null)
        return;

    checkBalance(node.getParent());
}

This method checks if the balance factor at the given node is more than 1. If it is, the method rebalance is called. At the end, we check if said node has a parent node. If so, we go up one level to check for balance there as well. With this method, we simply go back up the tree from the node to the root, and just check where discrepancies occur.

The rebalance method, as the case may be, performs the rotations.

private void rebalance(Node node)
{
    if(node == null)
        return;

    if(height(node.getLeft()) - height(node.getRight()) > 1)
    {
        if(height(node.getLeft().getLeft()) > height(node.getLeft().getRight()))
        {
            node = rotateRight(node);
        }
        else
        {
            node = rotateLeftRight(node);
        }
    }
    else
    {
        if(height(node.getRight().getLeft()) > height(node.getRight().getRight()))
        {
            node = rotateRightLeft(node);
        }
        else
        {
            node = rotateLeft(node);
        }
    }

    if(node.getParent() == null)
        this.root = node;
}

Here all 4 cases are checked, which then make the appropriate rotations.

The Main looks like this:

package com.strider.dev;

public class Main {

    public static void main(String[] args) {
        Tree T = new Tree();
        T.add(4);
        T.add(3);
        T.add(2);
        T.add(5);
        T.add(1);

        System.out.println("Inorder");
        T.inorder();
        System.out.println("Preorder");
        T.preorder();
        System.out.println("Postorder ");
        T.postorder();

        System.out.println("Height: " + T.height());
    }
}

If we run this now, we see that our AVL tree actually works.

Adding Node 4
Adding Node 3
Adding Node 2
Unbalanced Tree
Adding Node 5
Adding Node 1
Inorder
1
2
3
4
5
Preorder
3
2
1
4
5
Postorder 
1
2
5
4
3
Height: 3

In Inorder, we have a small anomaly. Here we see a sorted output. The fun fact about AVL trees is that they also represent a sorting method, the AVL sort.

I hope I could give some insights in the topic AVL tree 😄