Advanced Trees

#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
}

#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);
        
        // Note: Full implementation would handle splits
        // when leaf->keys.size() >= ORDER
    }
    
    // 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;
}