W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Advanced Trees

Segment Tree, Fenwick Tree, AVL Tree, B-Tree, B+ Tree, and Huffman Coding.

Segment Tree

Build: O(n) | Query: O(log n) | Update: O(log n)

Range Queries on Intervals

Imagine a tournament bracket or a pyramid. The bottom foundation layer (leaves) contains the raw array elements. Each parent layer block above merges the answers of the two blocks sitting directly beneath it (e.g., storing their sum, minimum, or maximum).

A Segment Tree is a static tree data structure designed to query and update intervals of an array efficiently.

Why Segment Trees are Essential:

For an array of size n, a naive range query takes O(n) time. A Segment Tree speeds up range queries to logarithmic time by precomputing range metrics.

Operation	Naive Array	Segment Tree
Range Query	`O(n)`	`O(log n)`
Point Update	`O(1)`	`O(log n)`
Range Update	`O(n)`	`O(log n)` (with lazy propagation)

Structural Properties:

Leaf Nodes: Represent individual elements of the original array (arr[i]).
Internal Nodes: Represent the merged segment result of their left and right children.
Memory Footprint: Typically requires an array of size 4 * n to safely allocate all nodes in a binary tree format.

C++ Implementation — Segment Tree

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
    vector<int> tree;
    int n;
    
    // Build tree from array
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];  // Leaf node
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            
            build(arr, leftChild, start, mid);
            build(arr, rightChild, mid + 1, end);
            
            tree[node] = tree[leftChild] + tree[rightChild];
        }
    }
    
    // Range sum query [l, r]
    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) return 0;           // No overlap
        if (l <= start && end <= r) return tree[node]; // Complete overlap
        
        // Partial overlap
        int mid = (start + end) / 2;
        return query(2*node+1, start, mid, l, r) + 
               query(2*node+2, mid+1, end, l, r);
    }
    
    // Update element at index idx
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid)
                update(2*node+1, start, mid, idx, val);
            else
                update(2*node+2, mid+1, end, idx, val);
            tree[node] = tree[2*node+1] + tree[2*node+2];
        }
    }

public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n, 0);
        build(arr, 0, 0, n - 1);
    }
    
    int query(int l, int r) { return query(0, 0, n-1, l, r); }
    void update(int idx, int val) { update(0, 0, n-1, idx, val); }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree st(arr);
    
    cout << "Sum [1,3]: " << st.query(1, 3) << endl;  // 15
    st.update(1, 10);  // arr[1] = 10
    cout << "Sum [1,3]: " << st.query(1, 3) << endl;  // 22
}

Fenwick Tree (Binary Indexed Tree)

Update: O(log n) | Prefix Sum: O(log n) | Space: O(n)

Binary Indexed Space Allocations

Think of a ruler with marked increments representing powers of two. Instead of storing explicit range intervals in complex tree nodes, we can store cumulative sum metrics at indices that represent binary transitions.

A Fenwick Tree (or Binary Indexed Tree) is a compact, array-backed data structure designed to perform prefix sum queries and point updates in logarithmic time.

Comparison vs Segment Tree:

Memory Efficiency: Uses exactly n space (matching the original array size), whereas Segment Trees require 4 * n memory space.
Implementation Simplicity: Much shorter code; relies entirely on simple bitwise loops.
Update Limitations: Ideal for associative range operations (like sum, multiplication) but less flexible for dynamic range minimum/maximum queries.

Bitwise Navigation Trick:

The index traversal relies on the bitwise formula i & (-i), which isolates the lowest set bit of index i:

Update step (propagate changes up): i += i & (-i)
Query step (collect partial sums down): i -= i & (-i)

C++ Implementation — Fenwick Tree (Binary Indexed Tree)

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
    vector<int> tree;
    int n;
    
public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}
    
    // Add delta to element at index i (0-indexed)
    void update(int i, int delta) {
        i++;  // Convert to 1-indexed
        while (i <= n) {
            tree[i] += delta;
            i += i & (-i);  // Move to parent
        }
    }
    
    // Get prefix sum [0, i]
    int prefixSum(int i) {
        i++;
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i);  // Move to previous range
        }
        return sum;
    }
    
    // Get range sum [l, r]
    int rangeSum(int l, int r) {
        return prefixSum(r) - (l > 0 ? prefixSum(l - 1) : 0);
    }
};

int main() {
    FenwickTree ft(6);
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    
    for (int i = 0; i < 6; i++) 
        ft.update(i, arr[i]);
    
    cout << "Sum [1,3]: " << ft.rangeSum(1, 3) << endl;  // 15
    ft.update(1, 7);  // Add 7 to index 1
    cout << "Sum [1,3]: " << ft.rangeSum(1, 3) << endl;  // 22
}

AVL Tree (Self-Balancing BST)

Search/Insert/Delete: O(log n) guaranteed

Balancing Height Deviations

Imagine a hanging mobile sculpture. If you add too much weight to one side, the sculpture tilts. To keep it level, you must adjust the crossbars or pivot the central links.

An AVL Tree is a self-balancing Binary Search Tree where the height difference between the left and right subtrees of any node is restricted to at most 1.

Balance Factor:

For every node, the Balance Factor (BF) must fall in the range {-1, 0, 1}: BF = Height(Left Subtree) - Height(Right Subtree)

If BF falls outside this range, the node is unbalanced, and we apply one of four rotation patterns to restore balance:

Imbalance Type	Condition	Corrective Rotation
LL Case	Left subtree's left child is heavy	Single Right Rotation
RR Case	Right subtree's right child is heavy	Single Left Rotation
LR Case	Left subtree's right child is heavy	Left Rotation on child, then Right Rotation on node
RL Case	Right subtree's left child is heavy	Right Rotation on child, then Left Rotation on node

Advantages:

Guarantees strict O(log n) search, insertion, and deletion times, preventing worst-case linear skewing.
More strictly balanced than Red-Black trees, making AVL trees faster for lookup-intensive applications.

C++ Implementation — AVL Tree (Self-Balancing BST)

#include <iostream>
#include <algorithm>
using namespace std;

struct AVLNode {
    int data, height;
    AVLNode *left, *right;
    AVLNode(int val) : data(val), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
    int height(AVLNode* n) { return n ? n->height : 0; }
    int balanceFactor(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; }
    
    void updateHeight(AVLNode* n) {
        n->height = 1 + max(height(n->left), height(n->right));
    }
    
    // Right Rotation
    AVLNode* rightRotate(AVLNode* y) {
        AVLNode* x = y->left;
        AVLNode* T2 = x->right;
        x->right = y;
        y->left = T2;
        updateHeight(y);
        updateHeight(x);
        return x;
    }
    
    // Left Rotation
    AVLNode* leftRotate(AVLNode* x) {
        AVLNode* y = x->right;
        AVLNode* T2 = y->left;
        y->left = x;
        x->right = T2;
        updateHeight(x);
        updateHeight(y);
        return y;
    }
    
    AVLNode* insert(AVLNode* node, int val) {
        if (!node) return new AVLNode(val);
        
        if (val < node->data)
            node->left = insert(node->left, val);
        else if (val > node->data)
            node->right = insert(node->right, val);
        else return node;
        
        updateHeight(node);
        int bf = balanceFactor(node);
        
        // LL Case
        if (bf > 1 && val < node->left->data)
            return rightRotate(node);
        // RR Case
        if (bf < -1 && val > node->right->data)
            return leftRotate(node);
        // LR Case
        if (bf > 1 && val > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        // RL Case
        if (bf < -1 && val < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        return node;
    }
    
    AVLNode* minNode(AVLNode* n) {
        while (n->left) n = n->left;
        return n;
    }
    
    AVLNode* deleteNode(AVLNode* root, int val) {
        if (!root) return nullptr;
        
        if (val < root->data)
            root->left = deleteNode(root->left, val);
        else if (val > root->data)
            root->right = deleteNode(root->right, val);
        else {
            // Node to delete found
            if (!root->left || !root->right) {
                AVLNode* temp = root->left ? root->left : root->right;
                delete root;
                return temp;
            }
            AVLNode* temp = minNode(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
        
        updateHeight(root);
        int bf = balanceFactor(root);
        
        // Rebalance after deletion
        if (bf > 1 && balanceFactor(root->left) >= 0)
            return rightRotate(root);
        if (bf > 1 && balanceFactor(root->left) < 0) {
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }
        if (bf < -1 && balanceFactor(root->right) <= 0)
            return leftRotate(root);
        if (bf < -1 && balanceFactor(root->right) > 0) {
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }
        return root;
    }
    
    void inorder(AVLNode* n) {
        if (!n) return;
        inorder(n->left);
        cout << n->data << " ";
        inorder(n->right);
    }

public:
    AVLNode* root = nullptr;
    void insert(int val) { root = insert(root, val); }
    void remove(int val) { root = deleteNode(root, val); }
    void print() { inorder(root); cout << endl; }
};

int main() {
    AVLTree tree;
    for (int x : {10, 20, 30, 40, 50, 25}) tree.insert(x);
    cout << "After inserts: "; tree.print();
    
    tree.remove(40);
    cout << "After delete 40: "; tree.print();
}

B-Tree

Search/Insert/Delete: O(log n) | Space: O(n)

Disk-Optimized Multi-Way Trees

In external databases and block storage devices, reading a single node requires disk I/O, which is slow. Instead of binary trees (2 children), we can use a wide tree where each node holds multiple keys and points to many children, aligning perfectly with disk block sizes.

A B-Tree is a self-balancing search tree optimized for systems with block storage, keeping the tree broad and shallow.

Core Rules:

A node holds multiple keys and references up to k + 1 child nodes.
All leaf nodes must reside on the exact same depth level.
Minimum Degree (t): Except for the root, every node must contain at least t - 1 keys and have at least t children.
Split Mechanism: If a node overflows (reaches 2t - 1 keys) during insertion, the node splits in two, pushing the middle key up to its parent.

Why B-Trees:

Minimizes Disk I/O: Reading a block yields multiple keys at once, keeping height small (typically <= 3 even for millions of keys).
Application: Relational database indexes and file systems.

C++ Implementation — B-Tree

#include <iostream>
#include <vector>
using namespace std;

// B-Tree of minimum degree t
class BTreeNode {
public:
    vector<int> keys;
    vector<BTreeNode*> children;
    bool leaf;
    int t;  // Minimum degree
    
    BTreeNode(int t, bool leaf) : t(t), leaf(leaf) {}
    
    void traverse() {
        int i;
        for (i = 0; i < keys.size(); i++) {
            if (!leaf) children[i]->traverse();
            cout << keys[i] << " ";
        }
        if (!leaf) children[i]->traverse();
    }
    
    BTreeNode* search(int k) {
        int i = 0;
        while (i < keys.size() && k > keys[i]) i++;
        
        if (i < keys.size() && keys[i] == k) return this;
        if (leaf) return nullptr;
        
        return children[i]->search(k);
    }
    
    void insertNonFull(int k);
    void splitChild(int i, BTreeNode* y);
};

class BTree {
    BTreeNode* root;
    int t;
    
public:
    BTree(int t) : t(t), root(nullptr) {}
    
    void traverse() {
        if (root) root->traverse();
        cout << endl;
    }
    
    BTreeNode* search(int k) {
        return root ? root->search(k) : nullptr;
    }
    
    void insert(int k) {
        if (!root) {
            root = new BTreeNode(t, true);
            root->keys.push_back(k);
        } else {
            if (root->keys.size() == 2*t - 1) {
                BTreeNode* s = new BTreeNode(t, false);
                s->children.push_back(root);
                s->splitChild(0, root);
                
                int i = (s->keys[0] < k) ? 1 : 0;
                s->children[i]->insertNonFull(k);
                root = s;
            } else {
                root->insertNonFull(k);
            }
        }
    }
};

void BTreeNode::splitChild(int i, BTreeNode* y) {
    BTreeNode* z = new BTreeNode(y->t, y->leaf);
    
    // Copy last t-1 keys of y to z
    for (int j = 0; j < t - 1; j++)
        z->keys.push_back(y->keys[t + j]);
    
    if (!y->leaf) {
        for (int j = 0; j < t; j++)
            z->children.push_back(y->children[t + j]);
    }
    
    // Insert middle key to parent
    keys.insert(keys.begin() + i, y->keys[t - 1]);
    children.insert(children.begin() + i + 1, z);
    
    // Reduce y
    y->keys.resize(t - 1);
    if (!y->leaf) y->children.resize(t);
}

void BTreeNode::insertNonFull(int k) {
    int i = keys.size() - 1;
    
    if (leaf) {
        keys.push_back(0);
        while (i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            i--;
        }
        keys[i + 1] = k;
    } else {
        while (i >= 0 && keys[i] > k) i--;
        i++;
        
        if (children[i]->keys.size() == 2*t - 1) {
            splitChild(i, children[i]);
            if (keys[i] < k) i++;
        }
        children[i]->insertNonFull(k);
    }
}

int main() {
    BTree t(3);  // Minimum degree 3
    
    for (int x : {10, 20, 5, 6, 12, 30, 7, 17})
        t.insert(x);
    
    cout << "B-Tree traversal: ";
    t.traverse();
    
    cout << "Search 6: " << (t.search(6) ? "Found" : "Not Found") << endl;
    cout << "Search 15: " << (t.search(15) ? "Found" : "Not Found") << endl;
}

B+ Tree

Search: O(log n) | Range Query: O(log n + k) | Insert: O(log n)

Separator Keys & Leaf Chains

Imagine highway signs. The signs on the road (internal nodes) only direct you, but the actual cities and exits (data) are located on the ground floor.

A B+ Tree is an optimized variation of the B-Tree where:

Internal Nodes only store keys to guide searches; they do not hold actual record data.
Leaf Nodes store all keys along with their associated data records.
Leaf Node Chain: All leaf nodes are linked sequentially using a singly/doubly linked list, allowing fast range queries.

Structural Advantages:

Greater Fan-out: Since internal nodes store no data, they can hold more routing keys per block. This increases the branching factor and keeps the height very small.
Fast Range Queries: To perform a range query (e.g., finding values between 10 and 50), you find the start node 10 and traverse the linked list directly, avoiding expensive tree traversals.
Application: Modern database storage engines (e.g., MySQL InnoDB, PostgreSQL).

C++ Implementation — B+ Tree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int ORDER = 4;  // Max children

class BPlusNode {
public:
    bool isLeaf;
    vector<int> keys;
    vector<BPlusNode*> children;  // For internal nodes
    vector<int> values;           // For leaf nodes (data)
    BPlusNode* next;              // For leaf linked list
    
    BPlusNode(bool leaf) : isLeaf(leaf), next(nullptr) {}
};

class BPlusTree {
    BPlusNode* root;
    
    BPlusNode* findLeaf(int key) {
        BPlusNode* node = root;
        while (!node->isLeaf) {
            int i = 0;
            while (i < node->keys.size() && key >= node->keys[i]) i++;
            node = node->children[i];
        }
        return node;
    }
    
public:
    BPlusTree() {
        root = new BPlusNode(true);
    }
    
    // Search for a key
    bool search(int key) {
        BPlusNode* leaf = findLeaf(key);
        for (int k : leaf->keys) {
            if (k == key) return true;
        }
        return false;
    }
    
    // Range query [low, high]
    vector<int> rangeQuery(int low, int high) {
        vector<int> result;
        BPlusNode* leaf = findLeaf(low);
        
        while (leaf) {
            for (int i = 0; i < leaf->keys.size(); i++) {
                if (leaf->keys[i] >= low && leaf->keys[i] <= high) {
                    result.push_back(leaf->keys[i]);
                }
                if (leaf->keys[i] > high) return result;
            }
            leaf = leaf->next;  // Follow linked list
        }
        return result;
    }
    
    // Simplified insert (without full split logic for brevity)
    void insert(int key, int value) {
        BPlusNode* leaf = findLeaf(key);
        
        // Find insertion position
        auto it = lower_bound(leaf->keys.begin(), leaf->keys.end(), key);
        int pos = it - leaf->keys.begin();
        
        leaf->keys.insert(it, key);
        leaf->values.insert(leaf->values.begin() + pos, value);
    }
    
    // Print all leaves (shows linked list)
    void printLeaves() {
        BPlusNode* node = root;
        while (!node->isLeaf) node = node->children[0];
        
        cout << "Leaves: ";
        while (node) {
            cout << "[";
            for (int i = 0; i < node->keys.size(); i++) {
                cout << node->keys[i];
                if (i < node->keys.size() - 1) cout << ",";
            }
            cout << "]";
            if (node->next) cout << " -> ";
            node = node->next;
        }
        cout << endl;
    }
};

int main() {
    BPlusTree tree;
    
    // Insert some values
    for (int x : {10, 20, 5, 15, 25, 30, 35})
        tree.insert(x, x * 10);  // key, value
    
    cout << "Search 15: " << (tree.search(15) ? "Found" : "Not Found") << endl;
    cout << "Search 17: " << (tree.search(17) ? "Found" : "Not Found") << endl;
    
    cout << "Range [10,30]: ";
    for (int x : tree.rangeQuery(10, 30))
        cout << x << " ";
    cout << endl;
}

Huffman Coding Tree

Build: O(n log n) | Encode: O(n) | Decode: O(n)

Frequency-Based Compression

Think of Morse code. Letters used frequently (like 'E' or 'A') get short codes, while rare letters (like 'Q' or 'Z') get longer codes. This compresses the overall message length.

Huffman Coding is an algorithm for lossless data compression. It assigns variable-length binary codes to characters based on their frequency of occurrence.

Huffman Construction:

Count frequencies of all characters.
Add leaf nodes for each character to a Min-Heap (Priority Queue).
Extract the two lowest-frequency nodes, merge them under a parent node with a frequency equal to their sum, and insert the parent back into the heap.
Repeat until a single root node remains.

Properties:

Prefix-Free Codes: No code is a prefix of another code (e.g., if 'A' is 0, no other code starts with 0). This allows unambiguous decoding.
Application: Formats like ZIP, GZIP, and JPEG.

C++ Implementation — Huffman Coding Tree

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct HuffmanNode {
    char data;
    int freq;
    HuffmanNode *left, *right;
    
    HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

class HuffmanCoding {
    unordered_map<char, string> codes;
    
    void generateCodes(HuffmanNode* node, string code) {
        if (!node) return;
        if (!node->left && !node->right) {
            codes[node->data] = code.empty() ? "0" : code;
            return;
        }
        generateCodes(node->left, code + "0");
        generateCodes(node->right, code + "1");
    }
    
public:
    void buildTree(string text) {
        unordered_map<char, int> freq;
        for (char c : text) freq[c]++;
        
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
        for (auto& p : freq)
            pq.push(new HuffmanNode(p.first, p.second));
        
        while (pq.size() > 1) {
            HuffmanNode* left = pq.top(); pq.pop();
            HuffmanNode* right = pq.top(); pq.pop();
            
            HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
            parent->left = left;
            parent->right = right;
            pq.push(parent);
        }
        
        generateCodes(pq.top(), "");
    }
    
    void printCodes() {
        cout << "Huffman Codes:" << endl;
        for (auto& p : codes)
            cout << "  '" << p.first << "' -> " << p.second << endl;
    }
    
    string encode(string text) {
        string encoded;
        for (char c : text) encoded += codes[c];
        return encoded;
    }
};

int main() {
    HuffmanCoding hc;
    string text = "aabbbcccc";
    
    hc.buildTree(text);
    hc.printCodes();
    
    string encoded = hc.encode(text);
    cout << "\nOriginal: " << text << endl;
    cout << "Encoded: " << encoded << endl;
    cout << "Compression: " << text.length()*8 << " bits -> " 
         << encoded.length() << " bits" << endl;
}

Operation

Naive Array

Segment Tree

Range Query

O(n)

O(log n)

Point Update

O(1)

O(log n)

Range Update

O(n)

O(log n) (with lazy propagation)

#include <iostream> #include <vector> using namespace std; class SegmentTree { vector<int> tree; int n; // Build tree from array void build(vector<int>& arr, int node, int start, int end) { if (start == end) { tree[node] = arr[start]; // Leaf node } else { int mid = (start + end) / 2; int leftChild = 2 * node + 1; int rightChild = 2 * node + 2; build(arr, leftChild, start, mid); build(arr, rightChild, mid + 1, end); tree[node] = tree[leftChild] + tree[rightChild]; } } // Range sum query [l, r] int query(int node, int start, int end, int l, int r) { if (r < start || l > end) return 0; // No overlap if (l <= start && end <= r) return tree[node]; // Complete overlap // Partial overlap int mid = (start + end) / 2; return query(2*node+1, start, mid, l, r) + query(2*node+2, mid+1, end, l, r); } // Update element at index idx void update(int node, int start, int end, int idx, int val) { if (start == end) { tree[node] = val; } else { int mid = (start + end) / 2; if (idx <= mid) update(2*node+1, start, mid, idx, val); else update(2*node+2, mid+1, end, idx, val); tree[node] = tree[2*node+1] + tree[2*node+2]; } } public: SegmentTree(vector<int>& arr) { n = arr.size(); tree.resize(4 * n, 0); build(arr, 0, 0, n - 1); } int query(int l, int r) { return query(0, 0, n-1, l, r); } void update(int idx, int val) { update(0, 0, n-1, idx, val); } }; int main() { vector<int> arr = {1, 3, 5, 7, 9, 11}; SegmentTree st(arr); cout << "Sum [1,3]: " << st.query(1, 3) << endl; // 15 st.update(1, 10); // arr[1] = 10 cout << "Sum [1,3]: " << st.query(1, 3) << endl; // 22 }

#include <iostream> #include <vector> using namespace std; class FenwickTree { vector<int> tree; int n; public: FenwickTree(int size) : n(size), tree(size + 1, 0) {} // Add delta to element at index i (0-indexed) void update(int i, int delta) { i++; // Convert to 1-indexed while (i <= n) { tree[i] += delta; i += i & (-i); // Move to parent } } // Get prefix sum [0, i] int prefixSum(int i) { i++; int sum = 0; while (i > 0) { sum += tree[i]; i -= i & (-i); // Move to previous range } return sum; } // Get range sum [l, r] int rangeSum(int l, int r) { return prefixSum(r) - (l > 0 ? prefixSum(l - 1) : 0); } }; int main() { FenwickTree ft(6); vector<int> arr = {1, 3, 5, 7, 9, 11}; for (int i = 0; i < 6; i++) ft.update(i, arr[i]); cout << "Sum [1,3]: " << ft.rangeSum(1, 3) << endl; // 15 ft.update(1, 7); // Add 7 to index 1 cout << "Sum [1,3]: " << ft.rangeSum(1, 3) << endl; // 22 }

Imbalance Type

Condition

Corrective Rotation

LL Case

Left subtree's left child is heavy

Single Right Rotation

RR Case

Right subtree's right child is heavy

Single Left Rotation

LR Case

Left subtree's right child is heavy

Left Rotation on child, then Right Rotation on node

RL Case

Right subtree's left child is heavy

Right Rotation on child, then Left Rotation on node

#include <iostream> #include <algorithm> using namespace std; struct AVLNode { int data, height; AVLNode *left, *right; AVLNode(int val) : data(val), height(1), left(nullptr), right(nullptr) {} }; class AVLTree { int height(AVLNode* n) { return n ? n->height : 0; } int balanceFactor(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; } void updateHeight(AVLNode* n) { n->height = 1 + max(height(n->left), height(n->right)); } // Right Rotation AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; x->right = y; y->left = T2; updateHeight(y); updateHeight(x); return x; } // Left Rotation AVLNode* leftRotate(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; y->left = x; x->right = T2; updateHeight(x); updateHeight(y); return y; } AVLNode* insert(AVLNode* node, int val) { if (!node) return new AVLNode(val); if (val < node->data) node->left = insert(node->left, val); else if (val > node->data) node->right = insert(node->right, val); else return node; updateHeight(node); int bf = balanceFactor(node); // LL Case if (bf > 1 && val < node->left->data) return rightRotate(node); // RR Case if (bf < -1 && val > node->right->data) return leftRotate(node); // LR Case if (bf > 1 && val > node->left->data) { node->left = leftRotate(node->left); return rightRotate(node); } // RL Case if (bf < -1 && val < node->right->data) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } AVLNode* minNode(AVLNode* n) { while (n->left) n = n->left; return n; } AVLNode* deleteNode(AVLNode* root, int val) { if (!root) return nullptr; if (val < root->data) root->left = deleteNode(root->left, val); else if (val > root->data) root->right = deleteNode(root->right, val); else { // Node to delete found if (!root->left || !root->right) { AVLNode* temp = root->left ? root->left : root->right; delete root; return temp; } AVLNode* temp = minNode(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } updateHeight(root); int bf = balanceFactor(root); // Rebalance after deletion if (bf > 1 && balanceFactor(root->left) >= 0) return rightRotate(root); if (bf > 1 && balanceFactor(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } if (bf < -1 && balanceFactor(root->right) <= 0) return leftRotate(root); if (bf < -1 && balanceFactor(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } void inorder(AVLNode* n) { if (!n) return; inorder(n->left); cout << n->data << " "; inorder(n->right); } public: AVLNode* root = nullptr; void insert(int val) { root = insert(root, val); } void remove(int val) { root = deleteNode(root, val); } void print() { inorder(root); cout << endl; } }; int main() { AVLTree tree; for (int x : {10, 20, 30, 40, 50, 25}) tree.insert(x); cout << "After inserts: "; tree.print(); tree.remove(40); cout << "After delete 40: "; tree.print(); }

#include <iostream> #include <vector> using namespace std; // B-Tree of minimum degree t class BTreeNode { public: vector<int> keys; vector<BTreeNode*> children; bool leaf; int t; // Minimum degree BTreeNode(int t, bool leaf) : t(t), leaf(leaf) {} void traverse() { int i; for (i = 0; i < keys.size(); i++) { if (!leaf) children[i]->traverse(); cout << keys[i] << " "; } if (!leaf) children[i]->traverse(); } BTreeNode* search(int k) { int i = 0; while (i < keys.size() && k > keys[i]) i++; if (i < keys.size() && keys[i] == k) return this; if (leaf) return nullptr; return children[i]->search(k); } void insertNonFull(int k); void splitChild(int i, BTreeNode* y); }; class BTree { BTreeNode* root; int t; public: BTree(int t) : t(t), root(nullptr) {} void traverse() { if (root) root->traverse(); cout << endl; } BTreeNode* search(int k) { return root ? root->search(k) : nullptr; } void insert(int k) { if (!root) { root = new BTreeNode(t, true); root->keys.push_back(k); } else { if (root->keys.size() == 2*t - 1) { BTreeNode* s = new BTreeNode(t, false); s->children.push_back(root); s->splitChild(0, root); int i = (s->keys[0] < k) ? 1 : 0; s->children[i]->insertNonFull(k); root = s; } else { root->insertNonFull(k); } } } }; void BTreeNode::splitChild(int i, BTreeNode* y) { BTreeNode* z = new BTreeNode(y->t, y->leaf); // Copy last t-1 keys of y to z for (int j = 0; j < t - 1; j++) z->keys.push_back(y->keys[t + j]); if (!y->leaf) { for (int j = 0; j < t; j++) z->children.push_back(y->children[t + j]); } // Insert middle key to parent keys.insert(keys.begin() + i, y->keys[t - 1]); children.insert(children.begin() + i + 1, z); // Reduce y y->keys.resize(t - 1); if (!y->leaf) y->children.resize(t); } void BTreeNode::insertNonFull(int k) { int i = keys.size() - 1; if (leaf) { keys.push_back(0); while (i >= 0 && keys[i] > k) { keys[i + 1] = keys[i]; i--; } keys[i + 1] = k; } else { while (i >= 0 && keys[i] > k) i--; i++; if (children[i]->keys.size() == 2*t - 1) { splitChild(i, children[i]); if (keys[i] < k) i++; } children[i]->insertNonFull(k); } } int main() { BTree t(3); // Minimum degree 3 for (int x : {10, 20, 5, 6, 12, 30, 7, 17}) t.insert(x); cout << "B-Tree traversal: "; t.traverse(); cout << "Search 6: " << (t.search(6) ? "Found" : "Not Found") << endl; cout << "Search 15: " << (t.search(15) ? "Found" : "Not Found") << endl; }

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int ORDER = 4; // Max children class BPlusNode { public: bool isLeaf; vector<int> keys; vector<BPlusNode*> children; // For internal nodes vector<int> values; // For leaf nodes (data) BPlusNode* next; // For leaf linked list BPlusNode(bool leaf) : isLeaf(leaf), next(nullptr) {} }; class BPlusTree { BPlusNode* root; BPlusNode* findLeaf(int key) { BPlusNode* node = root; while (!node->isLeaf) { int i = 0; while (i < node->keys.size() && key >= node->keys[i]) i++; node = node->children[i]; } return node; } public: BPlusTree() { root = new BPlusNode(true); } // Search for a key bool search(int key) { BPlusNode* leaf = findLeaf(key); for (int k : leaf->keys) { if (k == key) return true; } return false; } // Range query [low, high] vector<int> rangeQuery(int low, int high) { vector<int> result; BPlusNode* leaf = findLeaf(low); while (leaf) { for (int i = 0; i < leaf->keys.size(); i++) { if (leaf->keys[i] >= low && leaf->keys[i] <= high) { result.push_back(leaf->keys[i]); } if (leaf->keys[i] > high) return result; } leaf = leaf->next; // Follow linked list } return result; } // Simplified insert (without full split logic for brevity) void insert(int key, int value) { BPlusNode* leaf = findLeaf(key); // Find insertion position auto it = lower_bound(leaf->keys.begin(), leaf->keys.end(), key); int pos = it - leaf->keys.begin(); leaf->keys.insert(it, key); leaf->values.insert(leaf->values.begin() + pos, value); } // Print all leaves (shows linked list) void printLeaves() { BPlusNode* node = root; while (!node->isLeaf) node = node->children[0]; cout << "Leaves: "; while (node) { cout << "["; for (int i = 0; i < node->keys.size(); i++) { cout << node->keys[i]; if (i < node->keys.size() - 1) cout << ","; } cout << "]"; if (node->next) cout << " -> "; node = node->next; } cout << endl; } }; int main() { BPlusTree tree; // Insert some values for (int x : {10, 20, 5, 15, 25, 30, 35}) tree.insert(x, x * 10); // key, value cout << "Search 15: " << (tree.search(15) ? "Found" : "Not Found") << endl; cout << "Search 17: " << (tree.search(17) ? "Found" : "Not Found") << endl; cout << "Range [10,30]: "; for (int x : tree.rangeQuery(10, 30)) cout << x << " "; cout << endl; }

#include <iostream> #include <queue> #include <unordered_map> using namespace std; struct HuffmanNode { char data; int freq; HuffmanNode *left, *right; HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {} }; struct Compare { bool operator()(HuffmanNode* a, HuffmanNode* b) { return a->freq > b->freq; } }; class HuffmanCoding { unordered_map<char, string> codes; void generateCodes(HuffmanNode* node, string code) { if (!node) return; if (!node->left && !node->right) { codes[node->data] = code.empty() ? "0" : code; return; } generateCodes(node->left, code + "0"); generateCodes(node->right, code + "1"); } public: void buildTree(string text) { unordered_map<char, int> freq; for (char c : text) freq[c]++; priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq; for (auto& p : freq) pq.push(new HuffmanNode(p.first, p.second)); while (pq.size() > 1) { HuffmanNode* left = pq.top(); pq.pop(); HuffmanNode* right = pq.top(); pq.pop(); HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq); parent->left = left; parent->right = right; pq.push(parent); } generateCodes(pq.top(), ""); } void printCodes() { cout << "Huffman Codes:" << endl; for (auto& p : codes) cout << " '" << p.first << "' -> " << p.second << endl; } string encode(string text) { string encoded; for (char c : text) encoded += codes[c]; return encoded; } }; int main() { HuffmanCoding hc; string text = "aabbbcccc"; hc.buildTree(text); hc.printCodes(); string encoded = hc.encode(text); cout << "\nOriginal: " << text << endl; cout << "Encoded: " << encoded << endl; cout << "Compression: " << text.length()*8 << " bits -> " << encoded.length() << " bits" << endl; }