Self-Balancing Trees
Tags: webdev, javascript, beginners, codenewbie
Published: 2020-07-26 23:39:03

After getting great feedback from my last post on [binary search trees](https://dev.to/christinamcmahon/understanding-binary-search-trees-4d90) (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:

![Unbalanced BST](https://dev-to-uploads.s3.amazonaws.com/i/ak99v8l92m6f87vvgry6.png)

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](https://www.bigocheatsheet.com/), 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]():
```javascript
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.

![BST with labeled heights](https://dev-to-uploads.s3.amazonaws.com/i/m2iszvlgsh8re27kusr0.png)

The code to calculate the height of a node looks like this:
```javascript
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:

![three balanced trees](https://dev-to-uploads.s3.amazonaws.com/i/7tn8ekh42lp2nprad950.png)

Next, let's write the code to calculate the balance factor of a node and return its state:
```javascript
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:

![Left rotation example](https://dev-to-uploads.s3.amazonaws.com/i/q156j29ngom7e4fzesci.png)

The following code exemplifies this process:
```javascript
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:

![Right rotation example](https://dev-to-uploads.s3.amazonaws.com/i/5npw4vjnh4gik2e4mwmy.png)

```javascript
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:

![left Right rotation example](https://dev-to-uploads.s3.amazonaws.com/i/qz77pvlt2q5edy65xsyv.png)

```javascript
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:

![Right left rotation example](https://dev-to-uploads.s3.amazonaws.com/i/3zmnhs1l4cv7le6m607r.png)

```javascript
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.

```javascript
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.

```javascript
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:
```javascript
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](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html) by David Galles 
- [Step-by-step Rotations](https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm) 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](https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/) by GeeksforGeeks.