Binary Search Tree (BST) vs AVL Tree

Difference Between BST and AVL Tree Element Rotation

The key difference between a Binary Search Tree (BST) and an AVL Tree is how they handle balance.

― ― ― ― ― ― ― ― ― ―

High-Level Difference

• BST: Never rotates. The structure depends entirely on insertion order.
• AVL Tree: Automatically rotates to stay balanced after insertions and deletions.

A rotation is a restructuring of nodes that keeps the BST ordering intact while reducing the height of the tree.

― ― ― ― ― ― ― ― ― ―

Why Rotations Are Needed

Problem in a Normal BST

Insert sorted values into a BST:

Insert: 10, 20, 30, 40

The BST becomes:

10
  \
   20
     \
      30
        \
         40

This structure behaves like a linked list, causing search, insert, and delete operations to degrade from O(log n) to O(n).

BST response: No correction is made.

― ― ― ― ― ― ― ― ― ―

AVL Tree Balancing Rule

Every AVL node maintains a balance factor:

balance_factor = height(left subtree) - height(right subtree)

Valid balance factors:

-1, 0, +1

If the balance factor becomes +2 or -2, the AVL tree performs rotations to restore balance.

― ― ― ― ― ― ― ― ― ―

What Is a Rotation?

A rotation is a local tree transformation that:

• Preserves the BST property
• Reduces tree height
• Restores balance

You can think of it as pivoting nodes around a center point.

― ― ― ― ― ― ― ― ― ―

Types of AVL Rotations

1. Right Rotation (LL Case)

Occurs when a node is left-heavy and its left child is also left-heavy.

Before:
      30
     /
   20
  /
10

After Right Rotation:
      20
     /  \
   10   30

2. Left Rotation (RR Case)

Occurs when a node is right-heavy and its right child is also right-heavy.

Before:
10
  \
   20
     \
      30

After Left Rotation:
      20
     /  \
   10   30

3. Left-Right Rotation (LR Case)

Occurs when a node is left-heavy but its left child is right-heavy.

Before:
      30
     /
   10
     \
      20

Step 1: Left rotation on 10
Step 2: Right rotation on 30

After:
      20
     /  \
   10   30

4. Right-Left Rotation (RL Case)

Occurs when a node is right-heavy but its right child is left-heavy.

Before:
10
  \
   30
  /
20

Step 1: Right rotation on 30
Step 2: Left rotation on 10

After:
      20
     /  \
   10   30

― ― ― ― ― ― ― ― ― ―

BST vs AVL Tree (Rotation Comparison)

Feature	BST	AVL Tree
Self-balancing	No	Yes
Rotations	Never	Performed automatically
Balance factor	Not tracked	-1, 0, +1
Worst-case height	O(n)	O(log n)
Insert/Delete performance	Can degrade	Always O(log n)

Comparison of BST and AVL Tree

― ― ― ― ― ― ― ― ― ―

Python Rotation Examples (AVL Only)

Left Rotation

def left_rotate(z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    return y

Right Rotation

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

    y.right = z
    z.left = T3

    return y

These rotation functions are never used in a normal BST. They are what make AVL trees self-balancing.

― ― ― ― ― ― ― ― ― ―

Summary

• BST: Keeps order, ignores balance
• AVL Tree: Keeps order and enforces balance
• Rotation: Smart reshuffling without breaking sorted order