DSA Tutorial

🌳 AVL Trees in DSA (Using C)

An AVL Tree (Adelson-Velsky and Landis Tree) is a self-balancing binary search tree. The difference between an AVL tree and a regular binary search tree is that an AVL tree maintains a balance factor of each node, which ensures that the tree remains balanced. This helps ensure that the height of the tree remains logarithmic, ensuring faster search, insertion, and deletion operations.

🧠 What is an AVL Tree?

An AVL Tree is a type of binary search tree where the difference in heights between the left and right subtrees (called the balance factor) is at most 1 for all nodes. If the balance factor exceeds this limit, rebalancing operations like rotations are performed to restore balance.

Key Features of AVL Trees:

• Self-balancing binary search tree.
• Height-balanced at every node.
• Ensures O(log n) time complexity for search, insertion, and deletion.
• Balance factor of each node is maintained between -1 and 1.

💻 C Code: Basic AVL Tree Structure

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height;
};

// Function to get the height of the node
int height(struct Node* node) {
    if (node == NULL) return 0;
    return node->height;
}

// Function to get the balance factor of the node
int balanceFactor(struct Node* node) {
    if (node == NULL) return 0;
    return height(node->left) - height(node->right);
}

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return node;
}

int main() {
    struct Node* root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(15);

    printf("Root Node: %d\\n", root->data);
    printf("Balance Factor of Root: %d\\n", balanceFactor(root));

    return 0;
}
  

📤 Sample Output

Root Node: 10
Balance Factor of Root: 0
  

🔄 AVL Tree Operations

AVL Trees involve several key operations like insertion, deletion, and balancing through rotations. Here are the types of rotations that help maintain balance:

• Right Rotation (LL Case): Used when the left subtree is higher.
• Left Rotation (RR Case): Used when the right subtree is higher.
• Left-Right Rotation (LR Case): A combination of left and right rotations.
• Right-Left Rotation (RL Case): A combination of right and left rotations.

📜 Right Rotation (LL Case):

struct Node* rightRotate(struct Node* y) {
    struct Node* x = y->left;
    struct Node* T2 = x->right;

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

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

    // Return the new root
    return x;
}
  

📜 Left Rotation (RR Case):

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

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

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

    // Return the new root
    return y;
}
  

🌐 Insertion in AVL Tree

During insertion, after adding a node, we check the balance factor of each ancestor node, and if any node has an imbalance, we perform rotations to restore balance.

struct Node* insert(struct Node* node, int data) {
    // 1. Perform normal BST insertion
    if (node == NULL) return newNode(data);

    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else return node; // Duplicates not allowed

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

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

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

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

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

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

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

    return node; // Return the (unchanged) node pointer
}
  

🌐 Example Insertion and Balance Check

int main() {
    struct Node* root = NULL;
    
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30); // Causes imbalance and rotation

    printf("Root Node: %d\\n", root->data);
    return 0;
}
  

🔄 Deletion in AVL Tree

Similar to insertion, after deleting a node, we check for imbalance and perform necessary rotations to restore balance.