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

Part 12 of data structures series. The Balancing Hero: AVL Tree!

Welcome back, brave coder! 👩‍💻 If you remember from our last adventure, we journeyed through the land of Binary Search Trees (BSTs) and uncovered the ancient secret of balancing. When a tree becomes unbalanced, it gets wobbly, inefficient, and prone to collapse, making operations like search, insert, and delete slower than waiting for the Wi-Fi to reconnect lol.

But don’t worry! Today, we meet a new hero: the AVL Tree. Named after its creators Abelson-Velsky and Landis, the AVL Tree is here to save the day and keep our lovely BSTs balanced!

Ready? Let’s dive in and explore what makes AVL Trees so cool.

---

🧠 Quick Recap on BSTs and Balancing

In a Binary Search Tree:

• Left child is smaller than the parent node.

• Right child is greater than the parent node.

But! This dream can turn into a nightmare if the tree becomes unbalanced. If the tree leans too far in one direction (either left or right), we end up with something resembling a linked list, and we lose all the benefits of a fast BST (time complexities for search, insert, and delete can degrade to O(n)). 😱

Like this one (called a degenerate tree):

       1
        \
         2
          \
           3
            \
             4
              \
               5

To keep things smooth and fast, we need balance to get this result:

        3
       / \
      2   4
     /     \
    1       5

But how did you do that ? Nice question, actually, that’s what we’re going to discover in today’s article!

---

🦸‍♂️ Meet the AVL Tree: The Balancing Hero!

AVL Trees save us from the terror of imbalance. They are self-balancing BSTs, meaning they automatically keep themselves balanced after every insertion and deletion! But how?

Well, they use a simple but powerful trick called the balance factor ✨

🏋️‍♂️ The Balance Factor

The balance factor of a node is the difference between the height of its left and right subtrees.

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

• If the balance factor is -1, 0, or +1, the tree is balanced. 👍

• If it’s anything else (like -2 or +2), the tree is unbalanced. 🚨

Think of it like the seesaw at the playground:

• If both sides are evenly weighted (balance factor = 0), everything is perfect.

• A little tilt to one side (balance factor = -1 or +1)? That’s still okay.

• But if one side tilts too much (balance factor = -2 or +2), the seesaw tips over, and we have to rebalance!

Here are representations of the different cases for a Binary Search Tree (BST):

1. Perfectly Balanced (Balance Factor = 0)

If both sides are evenly weighted (balance factor = 0), everything is perfect.

      5
     / \
    3   7
   / \ / \
  2  4 6  8

• Both left, and right subtrees are evenly distributed.

2. Slight Tilt (Balance Factor = -1 or +1)

A little tilt to one side (balance factor = -1 or +1)? That’s still okay.

      5
     / \
    3   7
   /   / \
  2   6   8

• The left side is slightly heavier (Balance Factor = -1).

3. Unbalanced (Balance Factor = -2 or +2, Requires Rebalancing)

But if one side tilts too much (balance factor = -2 or +2), we have to rebalance!

      5
     / \
    3   7
   /
  2
 /
1

The left subtree is much heavier (Balance Factor = -2). This tree needs rebalancing to maintain optimal search efficiency.

🌲 Height of the Tree?

Just to clarify: The height of a node is the number of edges on the longest path from that node to a leaf. So if a node has no children, its height is zero.

Example:

        10
       /  \
      5    15
     / \     \
    3   7    20

Node Heights:

1. Node 3: This node has no children, so its height is 0.

2. Node 7: This node also has no children, so its height is 0.

3. Node 20: This node has no children, so its height is 0.

4. Node 5: The longest path from node 5 to a leaf is either to node 3 or node 7. Each of these paths has 1 edge, so the height of node 5 is 1.

5. Node 15: The longest path from node 15 to a leaf is to node 20, which has 1 edge, so the height of node 15 is 1.

6. Node 10 (root): The longest path from node 10 to a leaf goes through node 15 to node 20, with 2 edges, so the height of node 10 is 2.

---

🛠 The Balancing Act: Rotations!

When an AVL Tree becomes unbalanced, it uses rotations to restore balance. Think of this as the tree doing some fancy gymnastics to straighten itself up. There are four types of rotations:

Not this kind of rations hahaha 😂

1. Right Rotation (Single Rotation)

Problem: The left subtree is too heavy (balance factor = +2) at node 5.

Before Right Rotation:

       5 (+2 balance factor)  <- Unbalanced node
      /
     3 (+1)
    /
   2 (0)

• The balance factor of node 5 is +2 because its left subtree has height 2 and the right subtree has height 0.

• The tree is unbalanced at node 5.

Solution: Perform a Right Rotation on node 5.

After Right Rotation:

        3 (0)
       / \
  (0) 2   5 (0)

After rotation, all nodes are now balanced. The height difference of subtrees for each node is within the acceptable range (-1, 0, +1).

2. Left Rotation (Single Rotation)

Problem: The right subtree is too heavy (balance factor = -2) at node 3.

Before Left Rotation:

     3 (-2)  <- Unbalanced node
      \
       5 (-1)
        \
         7 (0)

• The balance factor of node 3 is -2 because its left subtree has height 0 and the right subtree has height 2.

• The tree is unbalanced at node 3.

Solution: Perform a Left Rotation on node 3.

After Left Rotation:

       5 (0)
      / \
 (0) 3   7 (0)

• After rotation, all nodes are balanced with balance factors of 0.

3. Left-Right Rotation (Double Rotation)

Problem: The left subtree is too heavy (balance factor = +2) at node 5, but the imbalance is in the right subtree of node 2 (right-heavy).

Before Left-Right Rotation:

       5 (+2)  <- Unbalanced node
      /
     2 (-1)    <- Imbalance in the right subtree
      \
       3 (0)

• The balance factor of node 5 is +2, and the left subtree (rooted at node 2) is right-heavy with a balance factor of -1.

• The imbalance at node 2 requires a double rotation.

Solution: Perform a Left Rotation on node 2, then a Right Rotation on node 5.

After Left-Right Rotation:

        3 (0)
       / \
  (0) 2   5 (0)

• After rotation, all nodes have a balance factor of 0, and the tree is balanced.

4. Right-Left Rotation (Double Rotation)

Problem: The right subtree is too heavy (balance factor = -2) at node 3, but the imbalance is in the left subtree of node 7 (left-heavy).

Before Right-Left Rotation:

     3 (-2)  <- Unbalanced node
      \
       7 (+1)  <- Imbalance in the left subtree
      /
     5 (0)

• The balance factor of node 3 is -2, and the right subtree (rooted at node 7) is left-heavy with a balance factor of +1.

• The imbalance at node 7 requires a double rotation.

Solution: Perform a Right Rotation on node 7, then a Left Rotation on node 3.

After Right-Left Rotation:

      5 (0)
     / \
(0) 3   7 (0)

• After rotation, all nodes have a balance factor of 0, and the tree is balanced.

Now that we saw the 4 types of rotations, let have a practical example, to grasp the concept more!

---

🎮 Let’s Insert and Visualize a Tree!

Let’s walk through inserting some values into an AVL Tree and see how it balances itself.

Step 1: Insert 30, 20, and 40.

      30 (0)
     /  \
(0) 20   40 (0)

Everything is balanced! No need for any rotations yet.

Step 2: Insert 10.

     30
    /  \
   20   40
  /
 10

Still balanced! The balance factor of node 30 is 1 (left subtree height = 2, right subtree height = 1), so no rotations needed.

Step 3: Insert 5.

Uh-oh, now we have an imbalance!

      30 (2)
     /  \
(2) 20   40 (0)
   /
  10 (1)
 /
5 (0)

The tree is left-heavy! The balance factor of node 30 is now 2 (left subtree = 3, right subtree = 1), so we need to perform a Right Rotation at node 20.

Analyzing:

Since the left subtree of 30 is taller, we can see that:

• The imbalance is Left-Left (LL) because the left child of the left subtree (20) has a height greater than its right child (which is empty).

To balance the tree, we can perform a Right Rotation around the node 30.

Perform Right Rotation

Right Rotation around the node 30 will involve the following steps:

1. Node 20 will become the new root of the subtree.

2. Node 30 will become the right child of the new root (20).

3. Node 10 will remain as the left child of 20.

4. Node 40 will remain as the right child of 30.

Final Tree Structure After Rotation

After performing the right rotation, the tree will look like this:

        20 (0)
       /  \
 (1)  10   30 (-1)
     /      \
(0) 5        40 (0)

---

🤷‍♂️ Let’s STOP here! My brain started screaming because of rotations haha 😂

Now that you understand the importance of tree balancing, and how we can perform it using rotations, we’re ready to take the next step in our adventure. In upcoming articles (part 2), we’ll do a funny/exciting thing: which is coding an AVL Tree from scratch, haha! Yes, that’s right! I believe we’ll be having our own data structures JavaScript library after the end of this series 😂.

For now, remember this: AVL trees are a powerful version of BSTs because they’re ensuring self-balancing properties. So, operations such as insertion, deletion, and search can be performed in logarithmic time (log n), making them highly efficient for dynamic datasets.

Stay tuned for the next part of our journey, where we’ll equip you with the specific tools and algorithms to conquer the challenge of tree balancing!

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