AVL Trees: Balance Factor and Rotations

1. What the Balance Factor (BF) means

For any node in an AVL tree:

Balance Factor (BF) = height of left child - height of right child

• Left-heavy → BF > 0
• Right-heavy → BF < 0
• Balanced → BF = 0

BF	Meaning
+1	Left child taller by 1 (ok)
0	Perfectly balanced
-1	Right child taller by 1 (ok)
+2	Too left-heavy → rotation needed
-2	Too right-heavy → rotation needed

Balance Factor Table

---

2. Example

Tree 1 (balanced)

      10
     /  \
    5    15

Heights:

5 → 0 (leaf)
15 → 0 (leaf)
10 → max(0,0)+1 = 1

BF:

10 → left 0 - right 0 = 0  (balanced)
5 → leaf → 0
15 → leaf → 0

Tree 2 (+2 → left-heavy, rotation needed)

      10
     /
    5
   /
  3

Heights:

3 → 0
5 → max(0, -1)+1 = 1
10 → max(1, -1)+1 = 2

BF:

10 → left height 1 - right height -1 = 2 (unbalanced)

Meaning: left side is 2 taller than right, so we need rotation.

Tree 3 (-2 → right-heavy, rotation needed)

    10
       \
        15
          \
           20

Heights:

20 → 0
15 → 1
10 → 2

BF:

left of 10 = None → -1
right of 10 = 15 → height 1
BF = -1 - 1 = -2 (unbalanced)

Right side too tall → rotation needed.

---

Intuition

• BF = 0 → perfectly balanced ⚖️
• BF = +1 → left side slightly heavier (ok)
• BF = -1 → right side slightly heavier (ok)
• BF = +2 → left side too heavy → rotate right
• BF = -2 → right side too heavy → rotate left

---

3. Small Python Demo

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def height(node):
    if node is None:
        return -1  # null child
    return 1 + max(height(node.left), height(node.right))

def balance_factor(node):
    return height(node.left) - height(node.right)

Every time you insert/delete a node, you recalculate BF. If BF is ±2, you rotate to fix it.

---

Step-by-step Height Calculation Example

      10
     /
    5
   /
  3

• Leaf = height 0
• Null child = height -1
• Height = 1 + max(left height, right height)
• BF = left height - right height

Node 3 → height 0, BF = 0
Node 5 → height 1, BF = 1
Node 10 → height 2, BF = 2 (unbalanced)

---

AVL Rotations

Right Rotation Formula (LL Case)

      X                     Y
     / \                   / \
    Y   C    ---->        A   X
   / \                       / \
  A   B                     B   C

Where:

• X = unbalanced node (10)
• Y = left child (5)
• A = left child of Y (3)
• B = null
• C = null

Before Rotation

      10
     /
    5
   /
  3

After Right Rotation

      5
     / \
    3   10

Heights after rotation:

3 → 0
10 → 0
5 → max(0,0)+1 = 1

Python Code for Right Rotation

def right_rotate(z):
    y = z.left
    T3 = y.right

    y.right = z
    z.left = T3

    return y  # new root after rotation

Usage:

root = Node(10)
root.left = Node(5)
root.left.left = Node(3)

root = right_rotate(root)

---

AVL Rotation Rules Summary

• Left-heavy node (BF = +2) → rotate right
• Right-heavy node (BF = -2) → rotate left
• Check child BF to decide single vs double rotation

Cases:

Left-Left (LL): single right rotation
Left-Right (LR): left rotation on child, then right rotation
Right-Right (RR): single left rotation
Right-Left (RL): right rotation on child, then left rotation

Node BF	Child BF	Case	Rotation
+2	≥0	LL	Right rotation
+2	<0	LR	Left child, then right
-2	≤0	RR	Left rotation
-2	>0	RL	Right child, then left

AVL Rotation Cases