AVL Trees: The Balancing Hero 🦸‍♂️ For BSTs! - Part 2

Part 14 of data structures series. Let's code an AVL Tree from scratch!

Welcome back, brave coder! 👩‍💻 If you remember from Part 1, AVL Trees are the superheroes of the Binary Search Tree (BST) world! They're always busy making sure that your tree doesn’t become inefficient! Without them, a BST can go unbalanced, leaving you stuck with long search times: from O(log n) to O(n)!

Today, we'll actually code an AVL Tree in JavaScript from scratch! But please, if you didn’t read the part 1 of the AVL Trees, kindly do so, because this article can be challenging for you without the right prerequisites.

⚠️PS: Coding without understanding the theory behind things, is like pouring water into sand, please make sure to read and understand part 1 first, then you’re welcome to come back here, and code with me 😄

---

Understanding the AVL Node Structure🌲

To begin, let's look at how the AVL Tree is structured at the node level. Each node in an AVL tree stores a value, references to its left and right children, its height, and the balance factor that helps determine if the node is unbalanced.

class Node {
    constructor(data) {
        this.value = data;  // Data stored in the node
        this.left = null;   // Left node
        this.right = null;  // Right node
        this.height = 1;    // Height is important in our balancing act.
        this.balanceFactor = 0;  // Balance factor.
    }
}

In this structure:

• value holds the data.

• left and right are pointers to child nodes.

• height represents the height of the node in the tree.

• balanceFactor helps maintain the AVL property by tracking the height difference between the left and right subtrees.

⚠️PS: if you don’t understand what a balance factor is, please check this artice about Trees Balancing!

The AVLTree Class: Core Structure

The AVLTree class manages the operations for maintaining the balanced state of the tree. Let’s start with the constructor:

class AVLTree {
    constructor(value) {
        this.root = new Node(value);  // Initialize the tree with a root node
    }
}

The tree is initialized with a root node, and as we add more nodes, the tree will adjust itself to maintain balance.

Balancing the Tree: Rotations

An essential part of AVL trees is their ability to self-balance. Whenever a new node is inserted, the balance factor of each node is updated. If any node becomes unbalanced (i.e., its balance factor becomes greater than 1 or less than -1), the tree performs rotations to restore balance.

⚠️PS: if you don’t understand what a rotation is, please check this artice about AVL Trees!

Right Rotation 🔃

A right rotation is performed when the left subtree becomes too tall relative to the right subtree (balance factor > 1). This rotation moves the left child up and the root node down to the right.

rightRotation(node) {
    const leftChild = node.left;
    node.left = leftChild.right;
    leftChild.right = node;

    // Update heights and balance factors
    this.updateNodeHBF(node);
    this.updateNodeHBF(leftChild);
    
    return leftChild;  // New root after rotation
}

Left Rotation 🔃

Conversely, a left rotation is used when the right subtree becomes too tall (balance factor < -1). This rotation moves the right child up and the root node down to the left.

leftRotation(node) {
    const rightChild = node.right;
    node.right = rightChild.left;
    rightChild.left = node;

    // Update heights and balance factors
    this.updateNodeHBF(node);
    this.updateNodeHBF(rightChild);
    
    return rightChild;  // New root after rotation
}

Left-Right and Right-Left Rotations 🔃

For more complex unbalancing situations, we need double rotations. These are combinations of two simple rotations:

• Left-Right Rotation is performed when the left subtree's right child causes the imbalance.

• Right-Left Rotation is performed when the right subtree's left child causes the imbalance.

leftRightRotation(node) {
    node.left = this.leftRotation(node.left);
    return this.rightRotation(node);
}

rightLeftRotation(node) {
    node.right = this.rightRotation(node.right);
    return this.leftRotation(node);
}

---

Maintaining Balance ⚖️: Updating Heights and Balance Factors

For an AVL Tree to work correctly, it must keep track of the height and balance factor of each node. After every insertion, we must recalculate the height and balance factor, and apply rotations if necessary.

Here’s how we can update a node's height and balance factor:

updateNodeHBF(node) {
    if (!node) return;

    const leftHeight = node.left ? node.left.height : 0;
    const rightHeight = node.right ? node.right.height : 0;

    // Update height: 1 + max height of children
    node.height = 1 + Math.max(leftHeight, rightHeight);

    // Update balance factor: difference between left and right subtree heights
    node.balanceFactor = leftHeight - rightHeight;
}

This function ensures that the node’s height and balance factor are correctly maintained as the tree grows or shrinks.

---

Insertion ➕: Adding Nodes to the Tree

When inserting a new node into the AVL Tree, we first perform a standard Binary Search Tree insertion. Once the node is inserted, we then update the heights and balance factors as we backtrack from the leaf to the root, applying rotations when necessary.

insert(value) {
    const newNode = new Node(value);
    this.root = insertNode(this.root, newNode);
}

insertNode(currentNode, newNode) {
  if (!currentNode) {
     return newNode;  // Found the correct spot, insert the node
  }

  // Go left
  if (newNode.value < currentNode.value) {
     currentNode.left = insertRecursively(currentNode.left, newNode);
  } 
  // Go right
  else if (newNode.value > currentNode.value) {
      currentNode.right = insertRecursively(currentNode.right, newNode);
  } 
  // Duplicate value case
  else {
      return currentNode;  // Duplicate values are not allowed
  }

  // Update height and balance factor
  this.updateNodeHBF(currentNode);

  // Balance the node if necessary (see code in the next section)
  return this.balance(currentNode);
}

Balancing the Tree After Insertion ⚖️

During the recursive process, the tree checks for imbalances. If the balance factor of any node exceeds 1 or drops below -1, the appropriate rotation is applied to restore balance.

balance(node) {
    if (node.balanceFactor > 1) {  // Left-heavy
        if (node.left.balanceFactor >= 0) {
            return this.rightRotation(node);  // Left-Left case
        } else {
            return this.leftRightRotation(node);  // Left-Right case
        }
    } 
    if (node.balanceFactor < -1) {  // Right-heavy
        if (node.right.balanceFactor <= 0) {
            return this.leftRotation(node);  // Right-Right case
        } else {
            return this.rightLeftRotation(node);  // Right-Left case
        }
    }
    return node;  // No rotation needed
}

Displaying the Tree Structure 🌲

To verify that the tree remains balanced after multiple insertions, we can visualize its structure. Here’s a simple method to display the tree's contents:

display(node = this.root, spaceCount = 0, spaceIncrement = 5) {
    if (!node) return;

    spaceCount += spaceIncrement;
    
    // Print right child first
    this.display(node.right, spaceCount);

    // Print current node
    console.log(" ".repeat(spaceCount - spaceIncrement) + node.value);

    // Print left child
    this.display(node.left, spaceCount);
}

---

Example Usage 📍

Let’s create an AVL Tree and insert multiple values to see the balancing in action:

let avl = new AVLTree(10);
avl.insert(5);
avl.insert(15);
avl.insert(8);
avl.insert(3);
avl.insert(12);
avl.insert(18);
avl.insert(2);

avl.display();

Output ✅

After inserting the above values, the AVL tree will be displayed in a structured manner, and you’ll be able to see how it balances itself through rotations.

            10
         /      \
       5         15
     /  \       /   \
    3    8    12    18
   /
  2

This structure represents a balanced AVL tree. If any rotations were needed to maintain balance, they would have been applied automatically during the insertion process. So it’s time to say congrats! We have a self-balancing Tree now, no need to worry anymore about the unbalance problem!

---

Congratulations🎉🎊 (I’m done, lol 😂)

In this article, we explored the practical implementation of AVL trees in JavaScript, covering essential operations such as insertion, rotation, and balancing. By maintaining height and balance factor information and applying rotations when necessary, the AVL Tree ensures logarithmic time O (log n) complexity for insertions, deletions, and lookups, making it an efficient and powerful data structure 💪.

Stay tuned for the next part of our series, where we’ll explore more advanced topics to help you elevate your skills and reach the top 1% of software engineers!

PS: I’ll be uploading all the code from these blog articles to GitHub soon, so stay tuned!

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!