AVL Tree Rotations – Complete Detailed Notes

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

AVL Tree Rotations – Complete Detailed Notes

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

    z
   /  
  y    
 /     
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

  x
   \
    y
     \
      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

   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)

  1. Delete as in BST
  2. Update heights
  3. Check balance at every ancestor
  4. 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

  1. Draw rotation for inserting 1,2,3,4,5
  2. Implement AVL delete with rotation
  3. Find height after sequence of inserts
  4. Convert unbalanced BST to AVL
  5. 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

Last updated: Nov 12, 2025

AVL Tree Rotations – Complete Detailed Notes

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

AVL Tree Rotations – Complete Detailed Notes

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

    z
   /  
  y    
 /     
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

  x
   \
    y
     \
      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

   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)

  1. Delete as in BST
  2. Update heights
  3. Check balance at every ancestor
  4. 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

  1. Draw rotation for inserting 1,2,3,4,5
  2. Implement AVL delete with rotation
  3. Find height after sequence of inserts
  4. Convert unbalanced BST to AVL
  5. 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

Last updated: Nov 12, 2025