Advanced Data Structures in C - A Professional Guide

1. What is a Trie?

A Trie (prefix tree) is a tree-like data structure used to store a dynamic set of strings, where each node represents a character, and paths from the root to leaves form words. It's efficient for prefix-based searches, autocompletion, and dictionary implementations.

2. What are the applications of Tries?

3. How do you implement a Trie in C?

Example: Trie for lowercase English letters with insertion and search.

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

#define ALPHABET_SIZE 26

struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};

struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) node->children[i] = NULL;
    return node;
}

void insert(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (!curr->children[index]) curr->children[index] = createNode();
        curr = curr->children[index];
    }
    curr->isEndOfWord = true;
}

bool search(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (!curr->children[index]) return false;
        curr = curr->children[index];
    }
    return curr->isEndOfWord;
}

int main() {
    struct TrieNode* root = createNode();
    insert(root, "cat");
    insert(root, "car");
    printf("%d\n", search(root, "cat")); // Output: 1 (true)
    printf("%d\n", search(root, "can")); // Output: 0 (false)
    free(root); // Note: Full cleanup requires recursive free
    return 0;
}

4. What are the time and space complexities of Trie operations?

Time Complexity:

Space Complexity: O(ALPHABET_SIZE * N * m) (N = number of words, m = average word length).

5. What are the advantages and disadvantages of Tries?

6. What is a Segment Tree?

A Segment Tree is a binary tree used to store information about intervals or segments of an array, enabling efficient range queries (sum, min, max) and point updates. It's particularly useful for problems involving range operations on static data.

7. What are the applications of Segment Trees?

8. How do you implement a Segment Tree in C?

Example: Segment Tree for range sum queries.

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

#define MAX 1000

struct SegmentTree {
    int* tree;
    int n;
};

void build(struct SegmentTree* st, int arr[], int node, int start, int end) {
    if (start == end) {
        st->tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(st, arr, 2 * node + 1, start, mid);
    build(st, arr, 2 * node + 2, mid + 1, end);
}

int query(struct SegmentTree* st, int node, int start, int end, int l, int r) {
    if (r < start || l > end || node >= 2 * st->n) return 0; // Outside range or leaf
    if (l <= start && r >= end) return st->tree[node]; // Fully within range
    int mid = (start + end) / 2;
    return query(st, 2 * node + 1, start, mid, l) + query(st, 2 * node + 2, mid + 1, end, r);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = 5;
    struct SegmentTree st;
    st.n = n;
    st.tree = (int*)malloc(4 * n * sizeof(int));
    
    build(&st, arr, 1, 0, n - 1);
    
    printf("%d\n", query(&st, 1, 0, 1, 3)); // Output: 9 (1 + 3 + 5)
    printf("%d\n", query(&st, 1, 0, 3, 4)); // Output: 12 (3 + 5 + 7)
    
    free(st.tree);
    return 0;
}

9. What are the time and space complexities of Segment Tree operations?

Time Complexity:

Space Complexity: O(4n) (tree storage).

10. What are the advantages and disadvantages of Segment Trees?

11. What is a Binary Indexed Tree (BIT)?

A Binary Indexed Tree (Fenwick Tree) is a data structure that provides efficient prefix sum queries and point updates on an array. It uses bitwise operations to achieve O(log n) time complexity for both operations.

12. What are the applications of BIT?

13. How do you implement a BIT in C?

Example: BIT for prefix sum queries.

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

#define MAX 1000

struct BIT {
    int* tree;
    int n;
};

void update(struct BIT* bit, int index, int val) {
    index++; // 1-based indexing
    while (index <= bit->n) {
        bit->tree[index] += val;
        index += index & (-index); // Move to parent
    }
}

int query(struct BIT* bit, int index) {
    int sum = 0;
    index++; // 1-based indexing
    while (index > 0) {
        sum += bit->tree[index];
        index -= index & (-index); // Move to parent
    }
    return sum;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = 5;
    struct BIT bit;
    bit.n = n;
    bit.tree = (int*)calloc(n + 1, sizeof(int));
    
    for (int i = 0; i < n; i++) update(&bit, i, arr[i]);
    
    printf("%d\n", query(&bit, 3)); // Output: 9 (1 + 3 + 5)
    printf("%d\n", query(&bit, 5)); // Output: 16 (1 + 3 + 5 + 7)
    
    free(bit.tree);
    return 0;
}

14. What are the time and space complexities of BIT operations?

Time Complexity: O(log n) (both update and query).

Space Complexity: O(n) (tree storage).

15. What are the advantages and disadvantages of BIT?

16. What is a Disjoint Set Union (DSU)?

DSU (Union-Find) is a data structure that tracks a partition of elements into disjoint sets, supporting find and union operations. It's essential for connectivity problems in graph algorithms, often implemented with path compression for near-constant time operations.

17. What are the applications of DSU?

18. How do you implement a DSU in C?

Example: DSU with path compression.

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

#define V 4

struct DSU {
    int* parent;
    int* rank;
    int n;
};

void initDSU(struct DSU* dsu, int n) {
    dsu->parent = (int*)malloc(n * sizeof(int));
    dsu->rank = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        dsu->parent[i] = i;
        dsu->rank[i] = 0;
    }
}

int find(struct DSU* dsu, int x) {
    if (dsu->parent[x] != x) dsu->parent[x] = find(dsu, dsu->parent[x]);
    return dsu->parent[x];
}

void unionSet(struct DSU* dsu, int x, int y) {
    int xroot = find(dsu, x), yroot = find(dsu, y);
    if (xroot != yroot) {
        if (dsu->rank[xroot] < dsu->rank[yroot]) dsu->parent[xroot] = yroot;
        else if (dsu->rank[xroot] > dsu->rank[yroot]) dsu->parent[yroot] = xroot;
        else {
            dsu->parent[xroot] = yroot;
            dsu->rank[xroot]++;
        }
    }
}

int main() {
    struct DSU dsu;
    initDSU(&dsu, V);
    
    unionSet(&dsu, 0, 1);
    unionSet(&dsu, 1, 2);
    unionSet(&dsu, 2, 3);
    
    printf("%d\n", find(&dsu, 0) == find(&dsu, 2)); // Output: 1 (true, same set)
    printf("%d\n", find(&dsu, 0) == find(&dsu, 3)); // Output: 0 (false, different sets)
    
    free(dsu.parent);
    free(dsu.rank);
    return 0;
}

19. What are the time and space complexities of DSU operations?

Time Complexity: Nearly O(1) (amortized, with path compression).

Space Complexity: O(n) (parent and rank arrays).

20. What are the advantages and disadvantages of DSU?

21. What is an AVL Tree?

An AVL Tree is a self-balancing binary search tree where the height difference between left and right subtrees of any node is at most 1. It ensures O(log n) time complexity for search, insertion, and deletion operations through automatic rebalancing.

22. How does an AVL Tree maintain balance?

23. What are the operations in an AVL Tree?

24. What are the time and space complexities of AVL Tree operations?

Time Complexity: O(log n) (insert, delete, search, due to balanced height).

Space Complexity: O(log n) (recursion stack).

25. What are the advantages and disadvantages of AVL Trees?

26. What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree where each node has a color (red or black), and properties ensure approximate balance, guaranteeing O(log n) time complexity for operations while requiring fewer rotations than AVL trees, making it popular in standard library implementations.

27. What are the properties of a Red-Black Tree?

28. How does a Red-Black Tree maintain balance?

29. What are the operations in a Red-Black Tree?

30. What are the time and space complexities of Red-Black Tree operations?

Time Complexity: O(log n) (insert, delete, search).

Space Complexity: O(log n) (recursion stack).

31. What are the advantages and disadvantages of Red-Black Trees?

32. How do AVL and Red-Black Trees compare?

33. How do you choose between AVL and Red-Black Trees?