With Code, Diagrams, Step-by-Step, and Examples

AVL Tree Rotations – Complete Detailed Notes

With Code, Diagrams, Step-by-Step, and Examples

1. What is an AVL Tree?

AVL Tree is a self-balancing Binary Search Tree where the difference in heights of left and right subtrees cannot exceed 1.

Balance Factor (BF)

BF(node) = height(left) - height(right)

Valid values: -1, 0, +1
If |BF| > 1 → Tree is unbalanced → Rotation required

2. Why Rotations?

To restore balance after insert or delete operations.

3. Four Types of Rotations

Rotation	Case	Fix
LL (Left-Left)	Left child → Left heavy	Right Rotation
RR (Right-Right)	Right child → Right heavy	Left Rotation
LR (Left-Right)	Left child → Right heavy	Left → Right Rotation
RL (Right-Left)	Right child → Left heavy	Right → Left Rotation

4. Node Structure

struct AVLNode {
    int data;
    struct AVLNode *left, *right;
    int height;
};

5. Helper Functions

int height(struct AVLNode* node) {
    return node ? node->height : 0;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

void updateHeight(struct AVLNode* node) {
    node->height = 1 + max(height(node->left), height(node->right));
}

int getBalance(struct AVLNode* node) {
    return node ? height(node->left) - height(node->right) : 0;
}

CASE 1: RIGHT ROTATION (LL Imbalance)

Scenario

    z
   /  
  y    
 /     
x       → Unbalanced (BF(z) = +2)

After Right Rotation

  y
 / \
x   z

Code

struct AVLNode* rightRotate(struct AVLNode* z) {
    struct AVLNode* y = z->left;
    struct AVLNode* T3 = y->right;

    // Rotate
    y->right = z;
    z->left = T3;

    // Update heights
    updateHeight(z);
    updateHeight(y);

    return y;  // New root
}

Step-by-Step Diagram

Before:
       z
      /  
     y    
    /     
   x       

After:
     y
    / \
   x   z

CASE 2: LEFT ROTATION (RR Imbalance)

Scenario

  x
   \
    y
     \
      z   → Unbalanced (BF(x) = -2)

After Left Rotation

    y
   / \
  x   z

Code

struct AVLNode* leftRotate(struct AVLNode* x) {
    struct AVLNode* y = x->right;
    struct AVLNode* T2 = y->left;

    // Rotate
    y->left = x;
    x->right = T2;

    // Update heights
    updateHeight(x);
    updateHeight(y);

    return y;  // New root
}

CASE 3: LR ROTATION (Left-Right)

Scenario

    z
   /  
  x    
   \     
    y     → BF(z) = +2, BF(x) = -1

Step 1: Left Rotate on x

Step 2: Right Rotate on z

  y
 / \
x   z

Code

struct AVLNode* lrRotate(struct AVLNode* z) {
    z->left = leftRotate(z->left);
    return rightRotate(z);
}

CASE 4: RL ROTATION (Right-Left)

Scenario

  x
   \
    z
   /     
  y       → BF(x) = -2, BF(z) = +1

Step 1: Right Rotate on z

Step 2: Left Rotate on x

    y
   / \
  x   z

Code

struct AVLNode* rlRotate(struct AVLNode* x) {
    x->right = rightRotate(x->right);
    return leftRotate(x);
}

6. Full AVL Insert with Rotations

struct AVLNode* insert(struct AVLNode* node, int key) {
    // 1. Normal BST insert
    if (node == NULL) {
        struct AVLNode* newNode = (struct AVLNode*)malloc(sizeof(struct AVLNode));
        newNode->data = key;
        newNode->left = newNode->right = NULL;
        newNode->height = 1;
        return newNode;
    }

    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key > node->data)
        node->right = insert(node->right, key);
    else
        return node;  // No duplicates

    // 2. Update height
    updateHeight(node);

    // 3. Get balance factor
    int balance = getBalance(node);

    // 4. Rotations
    // LL Case
    if (balance > 1 && key < node->left->data)
        return rightRotate(node);

    // RR Case
    if (balance < -1 && key > node->right->data)
        return leftRotate(node);

    // LR Case
    if (balance > 1 && key > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL Case
    if (balance < -1 && key < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

7. Example: Insert 10, 20, 30 (RR Case)

Step 1: Insert 10

Step 2: Insert 20

   10
    \
    20

Step 3: Insert 30

   10
    \
    20
     \
     30   → BF(10) = -2 → RR Imbalance

Left Rotate on 10

    20
   /  \
  10   30

Balanced!

8. Example: Insert 3, 2, 1 (LL Case)

After 3,2:
   3
  /
 2

After 1:
   3
  /
 2
/
1   → BF(3) = +2 → LL Imbalance

Right Rotate on 3:

  2
 / \
1   3

9. Visual Summary of All Rotations

Case	Before	After
LL	`z←y←x`	`y(x,z)`
RR	`x→y→z`	`y(x,z)`
LR	`z←x→y`	`y(x,z)`
RL	`x→z←y`	`y(x,z)`

10. Deletion in AVL (Brief)

Delete as in BST
Update heights
Check balance at every ancestor
Perform rotation if needed

Same 4 cases as insert

11. Time Complexity

Operation	Time
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Rotation	O(1)

12. Comparison: AVL vs Red-Black

Feature	AVL	Red-Black
Balance	Stricter (	BF
Insert/Delete	More rotations	Fewer rotations
Search	Slightly faster	Slightly slower
Use	Lookup-heavy	Insert/delete-heavy

13. Full Working C Code

#include <stdio.h>
#include <stdlib.h>

struct AVLNode {
    int data;
    struct AVLNode *left, *right;
    int height;
};

// Helper functions (as above)

struct AVLNode* insert(struct AVLNode* root, int key) {
    // ... full insert with 4 rotations ...
}

void inorder(struct AVLNode* root) {
    if (root) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct AVLNode* root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    printf("Inorder: ");
    inorder(root);  // 10 20 25 30 40 50
    return 0;
}

14. Practice Problems

Draw rotation for inserting 1,2,3,4,5
Implement AVL delete with rotation
Find height after sequence of inserts
Convert unbalanced BST to AVL
Count rotations in 100 random inserts

15. Key Takeaways

Insight
AVL = BST + Height Balance
Only 4 rotation cases
Rotation = O(1)
All operations O(log n)
LL/RR → Single rotation
LR/RL → Double rotation
Always update height after rotation

End of Detailed AVL Rotations