Java Technologies Advanced Data Structures এর বাস্তব প্রয়োগ গাইড ও নোট

Advanced Data Structures এমন ডাটা স্ট্রাকচার যা সাধারণ ডাটা স্ট্রাকচার যেমন Array, Linked List, Stack, Queue থেকে বেশি জটিল এবং শক্তিশালী। এই ডাটা স্ট্রাকচারগুলি বিশেষ করে বড় আকারের ডেটা এবং কমপ্লেক্স অপারেশন পরিচালনা করার জন্য ব্যবহৃত হয়। এগুলি সাধারণত Searching, Sorting, Dynamic Programming, Graph Algorithms, এবং Networking এর মতো সমস্যা সমাধানে ব্যবহৃত হয়।

এই টিউটোরিয়ালে, আমরা কিছু Advanced Data Structures এবং তাদের Java তে বাস্তব প্রয়োগ নিয়ে আলোচনা করব, যেমন Trie, Segment Tree, Fenwick Tree (Binary Indexed Tree), এবং Disjoint Set (Union-Find)।

1. Trie (Prefix Tree)

Trie হল একটি বিশেষ ধরনের ট্রি ডাটা স্ট্রাকচার যা স্ট্রিং সংরক্ষণ এবং অনুসন্ধানের জন্য ব্যবহৃত হয়। এটি prefix-based অনুসন্ধান সমাধানে কার্যকরী। Trie ডাটা স্ট্রাকচারটি একটি টেক্সট ডাটাবেস, অটোকমপ্লিট ফিচার এবং ডিকশনারি ইমপ্লেমেন্টেশনের জন্য অত্যন্ত জনপ্রিয়।

বাস্তব প্রয়োগ:

• Autocomplete systems (যেমন Google search suggestion)
• Dictionary implementation
• Spell checking

উদাহরণ: Trie - Word Insertion এবং Searching

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = null;
        }
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

public class TrieExample {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");

        System.out.println(trie.search("apple"));  // true
        System.out.println(trie.search("app"));    // true
        System.out.println(trie.search("appl"));   // false
        System.out.println(trie.startsWith("app"));  // true
    }
}

ব্যাখ্যা:

• insert(): একটি শব্দ ইনসার্ট করে ট্রিতে।
• search(): ট্রিতে একটি নির্দিষ্ট শব্দ খুঁজে।
• startsWith(): একটি প্রিফিক্স দিয়ে শুরু হওয়া শব্দগুলি চেক করে।

2. Segment Tree

Segment Tree একটি বাইনারি ট্রি যা অ্যারের উপর বিভিন্ন কুয়েরি (যেমন, রেঞ্জ কুয়েরি) খুব দ্রুত সমাধান করতে সাহায্য করে। এটি O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন সম্পন্ন করতে সক্ষম।

বাস্তব প্রয়োগ:

• Range queries (Sum, Minimum, Maximum)
• Interval scheduling
• Query optimization in databases

উদাহরণ: Range Sum Query with Segment Tree

class SegmentTree {
    int[] segTree;
    int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        segTree = new int[4 * n];
        build(arr, 0, 0, n - 1);
    }

    // Build the segment tree
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            segTree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
        }
    }

    // Range sum query
    public int rangeSumQuery(int l, int r) {
        return rangeSumQuery(0, 0, n - 1, l, r);
    }

    private int rangeSumQuery(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return 0;
        }
        if (l <= start && end <= r) {
            return segTree[node];
        }
        int mid = (start + end) / 2;
        int left = rangeSumQuery(2 * node + 1, start, mid, l, r);
        int right = rangeSumQuery(2 * node + 2, mid + 1, end, l, r);
        return left + right;
    }

    // Point update
    public void update(int idx, int value) {
        update(0, 0, n - 1, idx, value);
    }

    private void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            segTree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                update(2 * node + 1, start, mid, idx, value);
            } else {
                update(2 * node + 2, mid + 1, end, idx, value);
            }
            segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
        }
    }
}

public class SegmentTreeExample {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree st = new SegmentTree(arr);

        // Range sum query
        System.out.println(st.rangeSumQuery(1, 3)); // Output: 15 (3+5+7)

        // Update index 1 to value 10
        st.update(1, 10);
        System.out.println(st.rangeSumQuery(1, 3)); // Output: 22 (10+5+7)
    }
}

ব্যাখ্যা:

• build(): অ্যারের উপর একটি সেগমেন্ট ট্রি তৈরি করে।
• rangeSumQuery(): একটি নির্দিষ্ট রেঞ্জের যোগফল বের করে।
• update(): নির্দিষ্ট ইনডেক্সে মান পরিবর্তন করে।

3. Fenwick Tree (Binary Indexed Tree)

Fenwick Tree বা Binary Indexed Tree (BIT) একটি বিশেষ ডাটা স্ট্রাকচার যা কার্যকরভাবে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন সম্পন্ন করতে সক্ষম। এটি মূলত O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট করতে ব্যবহৃত হয়।

বাস্তব প্রয়োগ:

• Prefix sum queries
• Cumulative frequency tables
• Dynamic range queries

উদাহরণ: Fenwick Tree for Range Sum Query

class FenwickTree {
    int[] bit;

    public FenwickTree(int n) {
        bit = new int[n + 1];
    }

    // Update the Fenwick Tree
    public void update(int index, int delta) {
        while (index < bit.length) {
            bit[index] += delta;
            index += index & -index;  // Move to parent index
        }
    }

    // Query the sum from 1 to index
    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;  // Move to parent index
        }
        return sum;
    }

    // Range sum query from l to r
    public int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

public class FenwickTreeExample {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        FenwickTree fenwickTree = new FenwickTree(arr.length);

        // Update Fenwick Tree with initial array values
        for (int i = 0; i < arr.length; i++) {
            fenwickTree.update(i + 1, arr[i]);
        }

        // Query the sum from index 1 to 3
        System.out.println(fenwickTree.rangeQuery(1, 3)); // Output: 9 (1+3+5)

        // Update index 2 to value 10
        fenwickTree.update(2, 5);  // Incrementing index 2 by 5

        System.out.println(fenwickTree.rangeQuery(1, 3)); // Output: 14 (1+10+5)
    }
}

ব্যাখ্যা:

• update(): নির্দিষ্ট ইনডেক্সে একটি মান পরিবর্তন বা বৃদ্ধি করে।
• query(): 1 থেকে ইনডেক্স পর্যন্ত যোগফল বের করে।
• rangeQuery(): দুটি ইনডেক্সের মধ্যে যোগফল বের করে।

4. Disjoint Set (Union-Find)

Disjoint Set বা Union-Find একটি ডাটা স্ট্রাকচার যা সেটগুলির মধ্যে সংযুক্ততা পরিচালনা করার জন্য ব্যবহৃত হয়। এটি মূলত গাছের মতো কাজ করে, যেখানে প্রতিটি ইউনিয়ন অপারেশন দুটি সেটকে একত্রিত করে এবং ফাইন্ড অপারেশন সেটের উপাদানগুলি নির্ধারণ করে।

বাস্তব প্রয়োগ:

• Graph connected components (যেমন, MST এবং Kruskal’s Algorithm)
• Dynamic connectivity
• Percolation problems

উদাহরণ: Union-Find Algorithm

class UnionFind {
    int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    //

Find with path compression public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // Path compression } return parent[x]; }

// Union by rank
public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

}

public class UnionFindExample { public static void main(String[] args) { UnionFind uf = new UnionFind(5);

    uf.union(0, 1);
    uf.union(1, 2);

    System.out.println(uf.find(0) == uf.find(2)); // true
    System.out.println(uf.find(0) == uf.find(3)); // false
}

}

#### ব্যাখ্যা:
- **find()**: কোনো উপাদানটির মূল (root) খুঁজে বের করে এবং পথ সংক্ষিপ্ত করে।
- **union()**: দুটি সেটকে একত্রিত করে, এবং **rank** অনুযায়ী সেটগুলিকে যুক্ত করে।

---

### সারাংশ

**Advanced Data Structures** যেমন **Trie**, **Segment Tree**, **Fenwick Tree**, এবং **Disjoint Set** বিভিন্ন বাস্তব সমস্যার সমাধানে অত্যন্ত কার্যকরী। Java তে এই ডাটা স্ট্রাকচারগুলি ব্যবহার করে আপনি দ্রুত এবং দক্ষভাবে বিভিন্ন সমস্যা সমাধান করতে পারেন, যেমন:
- **String matching**
- **Range queries**
- **Dynamic connectivity**
- **Graph algorithms**

এই ডাটা স্ট্রাকচারগুলি **Greedy**, **Divide and Conquer**, এবং **Dynamic Programming** এর মতো অ্যালগরিদমগুলির সাথে ব্যবহার করলে, কার্যকারিতা এবং স্পিডের ক্ষেত্রে উল্লেখযোগ্য উন্নতি সাধিত হয়।