Data Structures and Algorithms in C (DSA)

📘 Chapter: AVL Trees (Self-balancing BST)

As we learned, a standard Binary Search Tree (BST) can degenerate into a skewed tree, leading to worst-case O(n) time complexity for search, insertion, and deletion operations. To overcome this limitation, self-balancing binary search trees were introduced. Among the oldest and most well-known self-balancing BSTs is the AVL Tree, named after its inventors Adelson-Velsky and Landis. AVL trees automatically maintain their balance to ensure that all basic operations remain efficient, guaranteeing O(log n) time complexity even in the worst case.

⚖️ What is an AVL Tree? The Balance Factor

An AVL tree is a self-balancing Binary Search Tree where for every node, the height difference between its left and right subtrees is at most 1. This difference is called the Balance Factor.

• Balance Factor (BF) = height(left subtree) - height(right subtree)
• For a tree to be an AVL tree, the Balance Factor of every node must be -1, 0, or 1.
• If a node's Balance Factor becomes greater than 1 or less than -1 after an insertion or deletion, the tree is rebalanced using rotations.

Maintaining this strict balance factor constraint ensures that the tree's height remains logarithmic to the number of nodes (O(log n)), thus guaranteeing efficient operations.

🔄 AVL Rotations: Restoring Balance

When an insertion or deletion causes a node's balance factor to violate the AVL property (i.e., it becomes -2 or 2), a series of rotations are performed to restore balance. There are four types of rotations:

1. Left Rotation (LL Imbalance)

A Left Rotation is performed when a node becomes right-heavy (BF = -2) due to an insertion in its right child's right subtree. It's a single rotation to the left.

// Conceptual Left Rotation in C
struct Node* leftRotate(struct Node* x) {
    struct Node* y = x->right; // y is the new root of the rotated subtree
    struct Node* T2 = y->left; // T2 is y's left child, which becomes x's right child

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights (and balance factors) after rotation
    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    return y; // Return new root
}
  

2. Right Rotation (RR Imbalance)

A Right Rotation is performed when a node becomes left-heavy (BF = 2) due to an insertion in its left child's left subtree. It's a single rotation to the right.

// Conceptual Right Rotation in C
struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;  // x is the new root of the rotated subtree
    struct Node* T2 = x->right; // T2 is x's right child, which becomes y's left child

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights (and balance factors)
    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x; // Return new root
}
  

3. Left-Right Rotation (LR Imbalance)

This is a double rotation. It occurs when a node becomes left-heavy (BF = 2) due to an insertion in its left child's right subtree. It's resolved by performing a Left Rotation on the left child, followed by a Right Rotation on the imbalanced node.

(The code would involve calling `leftRotate` and then `rightRotate`.)

4. Right-Left Rotation (RL Imbalance)

This is also a double rotation. It occurs when a node becomes right-heavy (BF = -2) due to an insertion in its right child's left subtree. It's resolved by performing a Right Rotation on the right child, followed by a Left Rotation on the imbalanced node.

(The code would involve calling `rightRotate` and then `leftRotate`.)

📈 AVL Tree Operations (Conceptual)

The search operation in an AVL tree is identical to that in a standard BST. The complexity arises in insertion and deletion, where, after the standard BST operation, additional logic is required to check balance factors and perform rotations if necessary.

// Conceptual AVL Insert operation in C (simplified)
struct Node* insertAVL(struct Node* node, int key) {
    // 1. Perform the normal BST insertion
    if (node == NULL)
        return createNode(key);

    if (key < node->data)
        node->left = insertAVL(node->left, key);
    else if (key > node->data)
        node->right = insertAVL(node->right, key);
    else // Duplicate keys are not allowed
        return node;

    // 2. Update height of this ancestor node
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. Get the balance factor of this ancestor node to check if this node became unbalanced
    int balance = getBalance(node);

    // 4. If the node becomes unbalanced, then there are 4 cases:

    // Left Left Case (RR rotation needed)
    if (balance > 1 && key < node->left->data)
        return rightRotate(node);

    // Right Right Case (LL rotation needed)
    if (balance < -1 && key > node->right->data)
        return leftRotate(node);

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

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

    return node;
}
  

Time Complexity: For all operations (Search, Insert, Delete), the worst-case time complexity for an AVL tree is O(log n). This is because the strict balance factor ensures that the tree's height always remains logarithmic.

AVL Tree Example: Before & After Insertion/Rotation

🚀 Advantages and Disadvantages of AVL Trees

Advantages:

• Guaranteed O(log n) Performance: Ensures logarithmic time complexity for search, insertion, and deletion in all cases (best, average, and worst). This is the primary advantage over simple BSTs.
• Predictable Performance: Because of guaranteed balance, performance doesn't degrade with specific insertion orders.

Disadvantages:

• Increased Complexity: Implementation is more complex than simple BSTs due to the logic required for height tracking and rotations.
• Higher Constant Factors: The rebalancing operations add overhead, meaning that for very small trees or applications where worst-case performance is rare, a simple BST might perform slightly faster due to less overhead.
• More Memory: Each node typically needs to store its height or balance factor, adding a small memory overhead.

📌 Real-Life Example (UdaanPath)

For a dynamic and frequently updated platform like UdaanPath, AVL Trees could be beneficial in scenarios where consistent, fast performance is critical, regardless of data insertion patterns:

• Dynamic Indexing of Large Datasets: If UdaanPath maintains a large, constantly growing database of educational content, user records, or assessment results where fast lookups, additions, and removals are essential, an AVL tree could serve as an efficient in-memory index. For instance, an index of all unique keywords used across course materials to enable quick search.
• Real-time Leaderboards with Frequent Updates: While heaps are great for finding the top N, if the leaderboard also needs efficient search for individual users or ranges, and frequently updated scores, an AVL tree could maintain sorted user scores with guaranteed O(log n) updates. Every time a student's score changes, the tree rebalances, ensuring that search and rank retrieval remain fast.
• Session Management / Cache Systems: In high-traffic systems, if user sessions or frequently accessed data need to be stored in a way that allows for quick retrieval and removal (e.g., when sessions expire), an AVL tree could manage these entries, providing consistent performance under varying load.

✅ Summary: Guaranteed Performance

• An AVL Tree is a self-balancing Binary Search Tree where the balance factor (height difference of left and right subtrees) of every node is -1, 0, or 1.
• It automatically rebalances itself using rotations (Left, Right, Left-Right, Right-Left) after insertions or deletions to maintain its balanced state.
• All major operations (search, insert, delete) in an AVL tree have a guaranteed O(log n) worst-case time complexity, unlike standard BSTs.
• It offers predictable and stable performance but comes with increased implementation complexity and a slight overhead compared to unbalanced BSTs.

📤 Coming Next: Trie (Prefix Tree)

From numerical ordering in BSTs and AVL trees, we now shift our focus to structures optimized for string data. The next chapter will introduce the Trie, also known as a Prefix Tree, a specialized tree data structure used for efficient retrieval of keys in a dataset of strings, especially useful for problems involving prefixes, spell checking, and autocomplete features.