Self-Balancing Trees

After getting great feedback from my last post on binary search trees (BST), I felt inspired to dive in even further by taking a look at self-balancing trees.

The Problem with Binary Search Trees

Depending on how many nodes you add to a BST, one of the edges of the tree can be very deep, as shown in the diagram below:

This can cause performance issues when manipulating or searching for a node on a particular edge of the tree. If you take a look at the Big-O Algorithm Complexity Cheat Sheet, you can see that the worst case time complexity of BST operations is O(h) where h is the height of the tree. Therefore, having the height be as small as possible is better when it comes to performing a large number of operations. That's where self-balancing binary search trees come in since their average and worst case time complexities are O(log n).

Solution: Self-Balancing Trees

In this article, we will learn about the Adelson-Velskii and Landi's tree (AVL tree) which is a self-balancing BST. This basically means that the height of the left and right subtrees of any node will differ by 1 at most. AVL trees have a worst case lookup, insert and delete time of O(log n). AVL trees are particularly helpful for quick searches of large amounts of data which is especially important in data analysis and data mining for example.

Let's begin by creating an AVLTree class which will be an extension of the BinarySearchTree class we wrote in my last blog post:

class AVLTree extends BinarySearchTree {
    constructor() {
        this.root = null;
    }
}

We will only need to overwrite the methods which will help maintain the AVL tree's balance: insert, insertNode, and removeNode. All the others will be inherited.

Before we get into writing our methods, let's review some terminology and the AVL tree's rotation operations.

Height of a Node and the Balancing Factor

As a reminder, the height of a node is defined as the maximum number of edges from the node to any of its leaf nodes.

The code to calculate the height of a node looks like this:

getNodeHeight(node) {
    if (node === null) {
        return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}

When it comes to inserting and removing nodes in an AVL tree versus a BST, the key difference is that we will need to verify its balance factor. The balance factor for a node is the difference between the height of the left and right subtrees. A binary tree is said to be balanced if the balance factor is -1, 0, or 1.

Balance Factor = Height of Left Subtree - Height of Right Subtree

Here are three examples of balanced trees with just their balance factors displayed:

Next, let's write the code to calculate the balance factor of a node and return its state:

getBalanceFactor(node) {
    const heightDif = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heigthDif) {
        case -2: 
            return BalanceFactor.UNBALANCED_RIGHT; 
        case -1: 
            return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
        case 1: 
            return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
        case 2: 
            return BalanceFactor.UNBALANCED_LEFT;
        default: 
            return BalanceFactor.BALANCED;
    }
} 

const BalanceFactor = {
    UNBALANCED_RIGHT: 1, 
    SLIGHTLY_UNBALANCED_RIGHT: 2, 
    BALANCED: 3, 
    SLIGHTLY_UNBALANCED_LEFT: 4, 
    UNBALANCED_LEFT: 5
}

We will go into detail about what each heightDif means in the subsequent sections...

Balancing Operations: AVL Rotations

After inserting or removing nodes from the AVL tree, you will need to verify whether the tree needs to be balanced. We will go over four scenarios involving two balancing processes: simple rotation and double rotation.

Left Rotation (LL)

If a tree becomes unbalanced when a node is inserted into the right subtree, you can perform a single left rotation, as shown in the diagram below:

The following code exemplifies this process:

rotationLL(node) {
    const temp = node.left;
    node.left = temp.right;
    temp.right = node;
    return temp;
}

Right Rotation (RR)

The right rotation is the inverse of the left rotation so I won't go into detail but the diagram and code will look like this:

rotationRR(node) {
    const temp = node.right;
    node.right = temp.left;
    temp.left = node;
    return temp;
}

Left Right Rotation (LR)

This case occurs when the height of the node's left child becomes greater than that of the right child's and the left child is right-heavy. We can fix this case by performing a left rotation on the left child, which produces the LL case, and then doing a right rotation on the unbalanced node. Refer to the diagram and code below:

rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
}

Right Left Rotation (RL)

Again, the right left rotation is the inverse of the left right rotation:

rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationLL(node);
}

Insert a Node in the AVL Tree

In an AVL tree, he process of inserting a node can be broken down into four steps:

1. Insert the new element using BST insertion logic.
2. Check the balance factor of every node.
3. If the balance factor of every node is 0, 1, or -1, skip step 4.
4. Otherwise, the tree is unbalanced so you will need to perform the appropriate rotation to make it balanced.

insert(data) {
    let newNode = new Node(data);

    if(this.root === null) {
        this.root = newNode;
    } else {
        this.insertNode(this.root, newNode); // helper method below
    }
}

insertNode(node, newNode) {
    // insert node as in BST tree (step 1)
    if (newNode.data < node.data) {
        if (node.left === null) {
            node.left = newNode;
        } else {
            this.insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null) {
            node.right = newNode;
        } else {
            this.insertNode(node.right, newNode);
        }
    }

    // check balance factor of every node (step 2)
    const balanceFactor = this.getBalanceFactor(node);

    // balance if necessary (steps 3 & 4)
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
        if (newNode.data < node.left.data) {
            node = this.rotationLL(node);
        } else {
            return this.rotationLR(node);
        }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
        if (newNode.data > node.right.data) {
            node = this.rotationRR(node);
        } else {
            return this.rotationRL(node);
        }
    }
    return node;
}

Remove a Node from the AVL Tree

Again, we'll break down removing a node into steps:

1. Remove the node using BST deletion logic.
2. Verify whether the tree is balanced. If it is, skip step 3.
3. Otherwise, apply the appropriate rotations.

removeNode(node, data) {
    // remove the node (step 1)
    node = super.removeNode(node, data); // from BinarySearchTree super class
    if (node === null) {
        return node; // no need to balance
    }

    // verify tree is balanced (step 2)
    const balanceFactor = this.getBalanceFactor(node);

    // balance if necessary (step 3)
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
        const balanceFactorL = this.getBalanceFactor(node.left);
        if (balanceFactorL === BalanceFactor.BALANCED || balanceFactorL === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
            return this.rotationLL(node);
        }
        if (balanceFactorL === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
            return this.rotationLR(node.left);
        }
    } else if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
        const balanceFactorR = this.getBalanceFactor(node.right);
        if (balanceFactorR === BalanceFactor.BALANCED || balanceFactorR === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
            return this.rotationRR(node);
        }
        if (balanceFactorR === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
            return this.rotationRL(node.right);
        }
    }
    return node;
}

Rotations Cheat Sheet

Here's a cheat sheet for quicker reference and as an overview of when to use the four rotation types:

if tree is right heavy {
    if right subtree is left heavy {
        Perform LR rotation
    } else {
        Perform LL rotation
    }
} else if tree is left heavy {
    if left subtree is right heavy {
        Perform RL rotation
    } else {
        Perform RR rotation
    }
}

Conclusion

I hope you found this article helpful in understanding the basics of self-balancing trees. I used the AVL tree as an example but there are other types of self-balancing trees out there to learn about if you are interested. Here are a few resources that I used to write this article and for you to continue your own studies.

• AVL Tree Visualization by David Galles
• Step-by-step Rotations from Tutorials Point

Also, if you are interested in learning about another popular type of self-balancing tree, check out this article on the Red-Black Tree by GeeksforGeeks.

Comments

[David]

Wow!! Very very detailed write-up! It’s clear you did a fairly deep dive into this. I love that you added a cheat sheet section. The implementation is non-trivial. I’m pretty blown away. Removing nodes from trees are also one of the most difficult things to think about and implement.

One thing I’ll add is to maybe add a small blurb at the top sharing the real-world applications of self-balancing trees — Quora has a bunch of great responses, and perhaps a mention of the red-black tree that it’s often compared against and why you’d select one over the other.

Major kudos!! 👏

[Christina]

Thanks, it was fun breaking this topic down and I really appreciate your enthusiasm and support!

Good thinking, I meant to mention those things originally but was focused on getting this posted by the end of the week so ran out of time. I went ahead and took your suggestions though, always appreciate the feedback!