Balanced Search Trees - AVL Trees

AVL Trees 

AVL Trees are one of the most important self-balancing Binary Search Trees (BST). They were introduced by Adelson-Velsky and Landis in 1962. The primary goal of an AVL tree is to maintain the height of the tree as small as possible, thereby ensuring efficient searching, insertion, and deletion.

---

1. Why do we need AVL Trees?

A Binary Search Tree (BST) works efficiently only when it is balanced.

Consider inserting the numbers:

10, 20, 30, 40, 50

A normal BST becomes

10
  \
   20
     \
      30
        \
         40
           \
            50

Height = 5

Searching for 50 requires

10 →20 →30 →40 →50

Time = O(n)

Instead, if the tree remains balanced,

       30
      /  \
    20    40
   /        \
 10         50

Height = 3

Searching requires only about log₂5 ≈ 3 comparisons.

Hence we need a self-balancing BST.

---

2. Definition of AVL Tree

An AVL Tree is a Binary Search Tree in which

For every node, the difference between the heights of the left and right subtrees is at most 1.

Mathematically,

| Height(Left) − Height(Right) | ≤ 1

---

3. Height of a Node

Height = Number of edges in the longest path from the node to a leaf.

Example

      40
     /  \
   20    60
  / \    /
10 30  50

Heights

10 =0
30 =0
50 =0

20 =1
60 =1

40 =2

---

4. Balance Factor

The Balance Factor (BF) of a node is

BF = Height(Left Subtree) − Height(Right Subtree)

Possible values in an AVL tree

-1
0
+1

If

BF = +2
or

BF = -2

the tree becomes unbalanced.

---

Example

      40
     /  \
   20    60

Height(left)=1

Height(right)=1

BF = 1−1 =0

Balanced.

---

Another example

      30
     /
   20
  /
10

Height(left)=2
Height(right)=0

BF =2

Not balanced.

---

5. Four Types of Imbalance

Only four cases are possible.

1. LL Rotation
2. RR Rotation
3. LR Rotation
4. RL Rotation

These are decided based on where the new node is inserted.

---

6. LL Rotation (Left Left Case)

Occurs when insertion happens in

Left subtree of Left child

Example

Insert

30
20
10

Step 1

30

Step 2

   30
  /
20

Balanced.

Step 3

    30
   /
 20
 /
10

Now

BF(30)=2

Tree is unbalanced.

---

Single Right Rotation

Before

      30
     /
   20
  /
10

After rotation

     20
    /  \
  10   30

Balanced again.

---

LL Rotation Steps

Suppose

      A
     /
    B
   /
  C

Perform

1. B becomes root

2. A becomes right child

3. B's right subtree becomes A's left subtree

Result

      B
     / \
    C   A

---

Example

Insert

50
40
30

Before

    50
   /
40
/ \
30  45

After

    40
   /  \
 30   50
      /
    45

---

7. RR Rotation (Right Right)

Insertion occurs

Right subtree of Right child

Example

Insert

10
20
30

Tree

10
  \
   20
     \
      30

Unbalanced.

---

Left Rotation

After rotation

     20
    /  \
 10     30

---

RR Rotation Steps

Perform

1. B becomes root

2. A becomes left child

3. B's left subtree becomes A's right subtree

Result

Before

A
 \
  B
   \
    C

After

     B
    / \
   A   C

---

Example

Insert

20
30
40

Before

20
  \
   30
   /  \
  25    40

After

    30
   /  \
20      40
 \ 
  25  

---

8. LR Rotation (Left Right)

Insertion occurs

Right subtree of Left child

Example

Insert

30
10
20

Tree

     30
    /
  10
    \
    20

Unbalanced.

---

Solution

Needs two rotations

Step 1

Left Rotation on 10

      30
     /
    20
   /
 10

Step 2

Right Rotation on 30

     20
    /  \
 10     30

Balanced.

---

LR Rotation Summary

First Left Rotation

Then Right Rotation

---

9. RL Rotation (Right Left)

Insertion occurs

Left subtree of Right child

Example

Insert

10
30
20

Tree

10
  \
   30
   /
 20

Unbalanced.

---

Step 1

Right Rotation on 30

10
  \
   20
     \
      30

---

Step 2

Left Rotation on 10

     20
    /  \
 10     30

Balanced.

---

RL Rotation Summary

Right Rotation

Then Left Rotation

---

10. Summary of Rotations

Case	Insertion Position	Rotation
LL	Left of Left child	Right Rotation
RR	Right of Right child	Left Rotation
LR	Right of Left child	Left then Right
RL	Left of Right child	Right then Left

---

11. AVL Insertion Algorithm

1. Insert the node exactly like a BST.
2. Update heights while returning.
3. Compute balance factor.
4. If balance factor becomes ±2
5. Identify the case.
6. Perform appropriate rotation.

---

Example

Insert

50
20
70
10
30
5

Initially

       50
      /  \
    20    70
   /  \
10    30
/
5

At node 50

BF=2

LL case

After rotation

       20
      /  \
    10    50
   /      / \
  5      30 70

Balanced.

---

12. Time Complexity Analysis

Let

n = number of nodes
h = height

Search

Exactly same as BST.

Worst-case nodes visited

h

AVL height

h = O(log n)

Therefore

Search = O(log n)

---

Insertion

Steps

BST insertion

O(log n)

Updating heights

O(log n)

Rotation

O(1)

Therefore

Insertion = O(log n)

---

Deletion

Deletion

O(log n)

Updating heights

O(log n)

Multiple rotations possible

Still

O(log n)

---

Time Complexity Table

Operation	AVL Tree
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Rotation	O(1)

---

13. Why Rotations Take Constant Time

Consider

      30
     /
   20
  /
10

Right rotation only changes

20 becomes parent

30 becomes child

One subtree changes

Only three pointers are modified.

No traversal is needed.

Hence

Rotation = O(1)

---

14. Proof that AVL Height is Always O(log n)

This is the most important theoretical result.

---

Step 1

Let

N(h)

be the minimum number of nodes in an AVL tree of height h.

To obtain the tallest possible AVL tree for a given number of nodes, each node must have the minimum number of descendants while still satisfying the AVL balance condition.

---

Step 2: Base Cases

Using the convention that the height of a leaf is 0:

N(0)=1

(single node)

N(1)=2

   A
  /
 B

---

Step 3: Recurrence Relation

To minimize the number of nodes while keeping height = h,

one subtree has height

h−1

and the other

h−2

because AVL allows a maximum height difference of 1.

Therefore,

$$N(h)=1+N(h-1)+N(h-2)$$

This is almost identical to the Fibonacci recurrence.

---

Step 4: Relation with Fibonacci Numbers

It can be shown by induction that

$$N(h)\ge F_{h+3}-1$$

where $F_k$is the $k^\text{th}$ Fibonacci number.

Since Fibonacci numbers grow exponentially,

$$F_k \approx \frac{\phi^k}{\sqrt5}$$

where

$$\phi=\frac{1+\sqrt5}{2}\approx1.618$$

Hence,

$$N(h)\ge \frac{\phi^{h+3}}{\sqrt5}-1$$

Ignoring constants,

$$N(h)=\Omega(\phi^h)$$

---

Step 5: Solve for Height

From

$$n \ge c\,\phi^h$$

for some positive constant $c$,

take logarithms:

$$h \le \log_{\phi}\!\left(\frac{n}{c}\right)$$

Using the change-of-base formula,

$$h = O(\log n)$$

Thus, the height of an AVL tree grows logarithmically with the number of nodes.

---

A More Precise Bound

A commonly cited upper bound is

$$h \le 1.44\log_2(n+2)-0.328$$

This shows that an AVL tree is very close to perfectly balanced.

---

15. Intuitive Explanation

Suppose you have

Number of Nodes	Maximum AVL Height (Approx.)
10	4
100	9
1,000	14
10,000	18
1,000,000	29

Even with one million nodes, the height is only about 29, which means search, insertion, and deletion require only around 29 comparisons in the worst case.

---

16. Advantages of AVL Trees

• Guaranteed O(log n) search, insertion, and deletion.
• Better search performance than many other balanced trees because AVL trees are more strictly balanced.
• Ideal for applications with frequent searching and relatively fewer updates.

---

17. Disadvantages of AVL Trees

• Extra memory is needed to store the height or balance factor.
• Insertions and deletions require rebalancing, making updates more expensive than in a simple BST.
• More complex to implement than a standard BST.

---

18. Comparison: BST vs AVL Tree

Feature	Binary Search Tree	AVL Tree
Balanced?	No	Yes
Worst-case Height	$O(n)$	$O(\log n)$
Search	$O(n)$ worst case	$O(\log n)$
Insert	$O(n)$ worst case	$O(\log n)$
Delete	$O(n)$ worst case	$O(\log n)$
Rotations	Not required	Required when unbalanced

Key Takeaway

The strength of an AVL tree lies in its strict balance condition. By ensuring that the balance factor of every node is always −1, 0, or +1, the tree height remains Θ(log n). This logarithmic height guarantees efficient searching, insertion, and deletion, making AVL trees one of the most effective balanced binary search tree data structures for applications where search performance is critical.