অ্যাডভান্সড ডেটা স্ট্রাকচার (Advanced Data Structures)

অ্যাডভান্সড ডেটা স্ট্রাকচার হল এমন ডেটা স্ট্রাকচার যা সাধারণত প্রাথমিক ডেটা স্ট্রাকচার (যেমন অ্যারে, লিঙ্কড লিস্ট, স্ট্যাক, কিউ) থেকে আরো জটিল এবং দক্ষ। এগুলি বৃহৎ ডেটাসেট, দ্রুত অনুসন্ধান, কাস্টম ডেটা ম্যানিপুলেশন এবং অপ্টিমাইজেশন সমস্যাগুলির সমাধানে ব্যবহৃত হয়।

এই ধরনের ডেটা স্ট্রাকচারগুলি যেমন বিনারি সার্চ ট্রি (Binary Search Tree), হ্যাশ টেবিল (Hash Table), হিপ (Heap), ট্রাই (Trie), অ্যাভিএল ট্রি (AVL Tree), ফিনব্যাক্স ট্রি (Fenwick Tree), রেড-ব্ল্যাক ট্রি (Red-Black Tree), গ্রাফ (Graph) ইত্যাদি, এদের প্রতিটি নিজস্ব ব্যবহার এবং কার্যকারিতা রয়েছে।

এখানে আমরা কিছু গুরুত্বপূর্ণ অ্যাডভান্সড ডেটা স্ট্রাকচার নিয়ে আলোচনা করব যা Java তে ব্যবহার করা যায়।

1. বাইনারি সার্চ ট্রি (Binary Search Tree - BST)

বাইনারি সার্চ ট্রি (BST) একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের লেফট চাইল্ড এর মান সেই নোডের মান থেকে ছোট এবং রাইট চাইল্ড এর মান সেই নোডের মানের চেয়ে বড় থাকে। এটি দ্রুত অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশন করতে সাহায্য করে।

BST ক্লাস উদাহরণ (Java):

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    BinarySearchTree() {
        root = null;
    }

    // Insert a node into the BST
    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }

        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    // In-order traversal
    void inorder() {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    // Search a node in BST
    Node search(int key) {
        return searchRec(root, key);
    }

    Node searchRec(Node root, int key) {
        if (root == null || root.data == key)
            return root;

        if (root.data < key)
            return searchRec(root.right, key);

        return searchRec(root.left, key);
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("In-order traversal:");
        tree.inorder();

        int key = 40;
        if (tree.search(key) != null) {
            System.out.println("\nNode " + key + " found.");
        } else {
            System.out.println("\nNode " + key + " not found.");
        }
    }
}

ব্যাখ্যা:

• BST ইনসার্ট, স্যাচ, ডিলিট অপারেশন করতে সাহায্য করে, যেখানে সময় জটিলতা O(log n) হতে পারে।
• inorder traversal BST তে উপাদানগুলি সজ্জিত করে দেখানোর জন্য ব্যবহৃত হয়।

2. হ্যাশ টেবিল (Hash Table)

হ্যাশ টেবিল একটি ডেটা স্ট্রাকচার যা key-value পেয়ার সংরক্ষণ করতে ব্যবহৃত হয়। এটি হ্যাশ ফাংশন ব্যবহার করে key থেকে একটি hash value তৈরি করে এবং ডেটাকে দ্রুত অ্যাক্সেস করে।

হ্যাশ টেবিলের উদাহরণ (Java):

import java.util.HashMap;

public class HashTableExample {
    public static void main(String[] args) {
        // Creating a HashMap (Hash Table)
        HashMap<String, Integer> map = new HashMap<>();

        // Inserting key-value pairs
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // Accessing values using keys
        System.out.println("Alice's age: " + map.get("Alice"));

        // Checking if a key exists
        if (map.containsKey("Bob")) {
            System.out.println("Bob's age: " + map.get("Bob"));
        }

        // Removing a key-value pair
        map.remove("Charlie");

        System.out.println("Hash Table: " + map);
    }
}

ব্যাখ্যা:

• HashMap Java এর একটি হ্যাশ টেবিল যা key-value পেয়ার সংরক্ষণ করতে ব্যবহৃত হয়।
• এটি O(1) সময় জটিলতায় দ্রুত key থেকে value অ্যাক্সেস করতে সহায়ক।

3. হিপ (Heap)

হিপ (Heap) একটি বিশেষ ধরনের বাইনারি ট্রি যা প্রতিটি নোডের সাথে কিছু নির্দিষ্ট শর্তাবলী পূরণ করে। সাধারণত দুটি ধরনের হিপ হয়:

• মিন হিপ (Min-Heap): যেখানে প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের চেয়ে ছোট।
• ম্যাক্স হিপ (Max-Heap): যেখানে প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের চেয়ে বড়।

মিন হিপ উদাহরণ (Java):

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // Creating a Min-Heap using PriorityQueue
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Adding elements to the Min-Heap
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(5);
        minHeap.add(40);
        minHeap.add(30);

        // Removing elements from the Min-Heap (in ascending order)
        System.out.println("Min-Heap elements in ascending order:");
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }
    }
}

ব্যাখ্যা:

• PriorityQueue ক্লাস ব্যবহার করে মিন হিপ তৈরি করা হয়, যেটি স্বয়ংক্রিয়ভাবে নোডগুলিকে ছোট থেকে বড় মানে সাজায়।

4. ট্রাই (Trie)

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

ট্রাই উদাহরণ (Java):

import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

public class Trie {
    private TrieNode root;

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

    // Insert word into the Trie
    public void insert(String word) {
        TrieNode currentNode = root;
        for (char c : word.toCharArray()) {
            currentNode.children.putIfAbsent(c, new TrieNode());
            currentNode = currentNode.children.get(c);
        }
        currentNode.isEndOfWord = true;
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        TrieNode currentNode = root;
        for (char c : word.toCharArray()) {
            currentNode = currentNode.children.get(c);
            if (currentNode == null) {
                return false;
            }
        }
        return currentNode.isEndOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        trie.insert("app");

        System.out.println("Is 'apple' present? " + trie.search("apple"));  // true
        System.out.println("Is 'app' present? " + trie.search("app"));      // true
        System.out.println("Is 'appl' present? " + trie.search("appl"));    // false
    }
}

ব্যাখ্যা:

• ট্রাই (Trie) একটি স্ট্রিং সন্নিবেশিত করার জন্য prefix-based অনুসন্ধান কৌশল ব্যবহার করে। এটি দ্রুত স্ট্রিং ম্যাচিং এবং prefix search এর জন্য ব্যবহৃত হয়।

5. রেড-ব্ল্যাক ট্রি (Red-Black Tree)

রেড-ব্ল্যাক ট্রি (Red-Black Tree) একটি ব্যালান্সড বাইনারি সার্চ ট্রি যা গ্রাফের মধ্যে দ্রুত অনুসন্ধান এবং ইনসার্ট অপারেশন করে। এটি প্রতি নোডে রঙের তথ্য ধারণ করে এবং কিছু নির্দিষ্ট নিয়ম অনুসরণ করে যা ট্রি ভারসাম্য বজায় রাখে।

Red-Black Tree-এ ব্যালেন্সিং:

• সমস্ত রেড-ব্ল্যাক ট্রির মধ্যে সুনির্দিষ্ট রঙের নিয়ম রয়েছে যা ট্রি ব্যালান্স রাখে।
• এই ট্রি O(log n) সময়ে ইনসার্ট, ডিলিট এবং সঞ্চালন করতে সক্ষম।

সারাংশ

অ্যাডভান্সড ডেটা স্ট্রাকচার যেমন বিনারি সার্চ ট্রি (BST), হ্যাশ টেবিল, হিপ, ট্রাই, এবং রেড-ব্ল্যাক ট্রি অত্যন্ত কার্যকরী ডেটা ম্যানিপুলেশনের জন্য ব্যবহৃত হয়। এগুলি বিভিন্ন ধরনের অনুসন্ধান, সন্নিবেশ, ডিলিট অপারেশন এবং অপ্টিমাইজেশন সমস্যা সমাধানে ব্যবহৃত হয়। Java তে এই ডেটা স্ট্রাকচারগুলি সহজেই বাস্তবায়ন করা যায় এবং এগুলির ব্যবহার কর্মক্ষমতা উন্নত করতে সাহায্য করে, বিশেষ করে বড় ডেটাসেট বা জটিল সমস্যাগুলির সমাধানে।

Segment Tree এবং Fenwick Tree (বা Binary Indexed Tree) দুটি অত্যন্ত শক্তিশালী ডেটা স্ট্রাকচার যা বিশেষ করে রেঞ্জ কুয়েরি এবং রেঞ্জ আপডেট অপারেশনগুলির জন্য ব্যবহৃত হয়। এগুলি মূলত বড় ডেটা সেটে দ্রুত অগ্রগতির জন্য ডিজাইন করা হয়েছে, যেখানে একাধিক মানকে একটি নির্দিষ্ট রেঞ্জের মধ্যে সংরক্ষণ এবং পরিবর্তন করতে হয়।

Segment Tree

Segment Tree একটি বিশেষ ধরনের বিনামূলক গাছ (binary tree) যা একটি অ্যারে বা তালিকায় নির্দিষ্ট রেঞ্জের উপাদানগুলির উপর বিভিন্ন ধরনের অপারেশন (যেমন যোগফল, গড়, সর্বোচ্চ/সর্বনিম্ন মান) দ্রুত করতে ব্যবহৃত হয়।

Segment Tree এর গঠন:

• নোড: প্রতিটি নোড রেঞ্জের ফলাফল ধারণ করে, যেমন রেঞ্জের যোগফল বা সর্বোচ্চ মান।
• Leaves: পাতার নোডগুলোতে অ্যারের উপাদানগুলি সংরক্ষিত থাকে।
• Internal Nodes: অভ্যন্তরীণ নোডগুলো তাদের সন্তানের রেঞ্জের উপর নির্ভর করে মান ধারণ করে।

সুবিধা:

• O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন করতে পারে।
• এটি বড় আকারের ডেটাসেটের জন্য কার্যকরী, যেখানে একাধিক রেঞ্জ কুয়েরি এবং আপডেট করতে হয়।

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

ধরা যাক, আমাদের একটি অ্যারে আছে, এবং আমরা বিভিন্ন রেঞ্জের যোগফল বের করতে চাই।

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = 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) {
            tree[node] = arr[start];
        } 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];
        }
    }

    // Query the sum of range [l, r]
    public int query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    private int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return 0; // Out of range
        }
        if (l <= start && end <= r) {
            return tree[node]; // Exact match
        }
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int leftResult = query(leftChild, start, mid, l, r);
        int rightResult = query(rightChild, mid + 1, end, l, r);
        return leftResult + rightResult; // Combine results
    }

    // Update the element at index idx to val
    public void update(int idx, int val) {
        update(0, 0, n - 1, idx, val);
    }

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

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree st = new SegmentTree(arr);
        System.out.println("Sum of range (1, 3): " + st.query(1, 3)); // Output: 15
        st.update(1, 10); // Update arr[1] = 10
        System.out.println("Sum of range (1, 3) after update: " + st.query(1, 3)); // Output: 22
    }
}

উপরের কোডের কার্যকারিতা:

1. build(): Segment tree তৈরি করে।
2. query(): একটি নির্দিষ্ট রেঞ্জের যোগফল বের করে।
3. update(): নির্দিষ্ট ইনডেক্সে মান আপডেট করে।

Fenwick Tree (Binary Indexed Tree)

Fenwick Tree বা Binary Indexed Tree (BIT) একটি ডেটা স্ট্রাকচার যা সমষ্টি (sum) এবং আপডেট (update) অপারেশনকে দ্রুত করতে সক্ষম। এটি বিশেষত তখন কার্যকরী, যখন আমরা একটি অ্যারের মধ্যে রেঞ্জ কুয়েরি করতে চাই এবং তাতে পরিবর্তন (update) করতে চাই। Fenwick Tree তে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন O(log n) সময়ে করা যায়।

Fenwick Tree এর গঠন:

• এটি একটি অ্যারের মত গঠন, কিন্তু প্রতিটি পজিশনে প্রিসাম (prefix sum) সংরক্ষণ করা হয়।
• আপডেট অপারেশনে একটি নির্দিষ্ট পজিশনে মান যোগ/বিয়োগ করা হয় এবং আপডেট করা মান পরবর্তী পজিশনে প্রভাব ফেলতে থাকে।

সুবিধা:

• O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন করা সম্ভব।
• এটি সাধারণত ছোট আকারের ডেটাসেট এবং গতিশীল রেঞ্জ কুয়েরি সমস্যার জন্য কার্যকরী।

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

class FenwickTree {
    private int[] tree;
    private int n;

    public FenwickTree(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    // Update the Fenwick Tree with value at index
    public void update(int index, int value) {
        while (index <= n) {
            tree[index] += value;
            index += index & (-index); // Move to the next index
        }
    }

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

    // Query the range sum between two indices
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {0, 1, 3, 4, 8, 6, 1, 4, 2, 3};
        FenwickTree fenwickTree = new FenwickTree(arr.length);

        // Build the Fenwick Tree
        for (int i = 1; i < arr.length; i++) {
            fenwickTree.update(i, arr[i]);
        }

        // Query range sum
        System.out.println("Range sum (1, 5): " + fenwickTree.rangeQuery(1, 5)); // Output: 22

        // Update the array
        fenwickTree.update(3, 6); // arr[3] = 10

        // Query range sum again
        System.out.println("Range sum (1, 5) after update: " + fenwickTree.rangeQuery(1, 5)); // Output: 28
    }
}

উপরের কোডের কার্যকারিতা:

1. update(): একটি নির্দিষ্ট পজিশনে মান যোগ করে বা বিয়োগ করে।
2. query(): একটি নির্দিষ্ট ইনডেক্স পর্যন্ত যোগফল বের করে।
3. rangeQuery(): নির্দিষ্ট রেঞ্জের যোগফল বের করে।

সারাংশ

Segment Tree এবং Fenwick Tree দুটি শক্তিশালী ডেটা স্ট্রাকচার যা রেঞ্জ কুয়েরি এবং রেঞ্জ আপডেট অপারেশন দ্রুত করতে ব্যবহৃত হয়। Segment Tree আরও সাধারণ এবং জটিল কুয়েরি সমাধানে ব্যবহৃত হয়, যেখানে Fenwick Tree সহজ এবং ছোট আকারের রেঞ্জ কুয়েরি সমস্যা সমাধানে কার্যকরী। দুটি ডেটা স্ট্রাকচারই O(log n) সময়ে রেঞ্জ কুয়েরি এবং আপডেট অপারেশন করার ক্ষমতা রাখে, যা বড় ডেটা সেটে দ্রুত কর্মক্ষমতা প্রদান করে।

Disjoint Set Union (DSU) বা Union-Find একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা গেম থিওরি, গ্রাফ অ্যালগরিদম এবং নেটওয়ার্ক ইন্টার-কানেক্টিভিটি ইস্যুগুলিতে ব্যাপকভাবে ব্যবহৃত হয়। এটি মূলত দুটি অপারেশন সমর্থন করে:

1. Union: দুটি সেট (set) একত্রিত করা।
2. Find: কোন একটি উপাদান কোন সেটের অন্তর্ভুক্ত তা খুঁজে বের করা।

এই ডাটা স্ট্রাকচারটি সাধারণত Connected Components চিহ্নিত করতে, Cycle Detection এবং MST (Minimum Spanning Tree) নির্মাণের জন্য ব্যবহৃত হয়।

DSU / Union-Find এর মূল ধারণা

1. Union অপারেশন: দুটি সেট একত্রিত করা।
2. Find অপারেশন: কোন উপাদান কোন সেটে আছে তা খুঁজে বের করা।

Path Compression এবং Union by Rank হল দুটি অপ্টিমাইজেশন টেকনিক যা Union-Find এর কার্যকারিতা বৃদ্ধি করে:

• Path Compression: যখন একটি find অপারেশন করা হয়, তখন প্রতিটি নোডকে তার রুটের সরাসরি সন্তান বানিয়ে দেওয়া হয়। এতে পরবর্তীতে ওই নোড খুঁজে পাওয়া দ্রুত হয়।
• Union by Rank: যখন দুটি সেট একত্রিত করা হয়, তখন ছোট র্যাঙ্কের (হাইটের) সেটটি বড় র্যাঙ্কের সেটের নিচে যুক্ত করা হয়। এতে গাছের উচ্চতা কম থাকে, ফলে অপারেশনগুলো দ্রুত হয়।

Union-Find এর ইমপ্লিমেন্টেশন

১. Union-Find Data Structure Class

public class UnionFind {
    private int[] parent;
    private int[] rank;

    // কন্সট্রাক্টর
    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        
        // প্রতিটি এলিমেন্ট নিজেই একটি প্যারেন্ট
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;  // প্রাথমিকভাবে র্যাঙ্ক (হাইট) 0
        }
    }

    // Find অপারেশন: উপাদানটির মূল প্যারেন্ট খুঁজে পাওয়া
    public int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]);  // Path compression
        }
        return parent[p];
    }

    // Union অপারেশন: দুটি সেট একত্রিত করা
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        // যদি রুট প্যারেন্ট এক হয়ে যায়, তাহলে কোন কাজ করার প্রয়োজন নেই
        if (rootP == rootQ) return;

        // Union by rank: ছোট গাছকে বড় গাছের নিচে রাখা
        if (rank[rootP] > rank[rootQ]) {
            parent[rootQ] = rootP;
        } else if (rank[rootP] < rank[rootQ]) {
            parent[rootP] = rootQ;
        } else {
            parent[rootQ] = rootP;
            rank[rootP]++;  // র্যাঙ্ক বাড়ানো
        }
    }

    // Check যদি দুটি উপাদান একই সেটে থাকে
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}

২. Main Method Example

public class Main {
    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);  // ১০টি উপাদান (0-9)

        // বিভিন্ন ইউনিয়ন অপারেশন
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(4, 5);
        uf.union(6, 7);
        uf.union(8, 9);
        uf.union(1, 5);

        // উপাদানগুলি একই সেটে আছে কিনা চেক করা
        System.out.println(uf.connected(1, 3));  // true
        System.out.println(uf.connected(1, 4));  // true
        System.out.println(uf.connected(1, 9));  // false
    }
}

ব্যাখ্যা:

1. Find Operation: find(p) ফাংশন একটি উপাদান p এর মূল প্যারেন্ট খুঁজে বের করে, এবং path compression প্রযুক্তি ব্যবহার করে প্যারেন্ট লিঙ্কগুলো কমিয়ে দেয়, যাতে পরবর্তী find অপারেশনগুলো দ্রুত হয়।
2. Union Operation: union(p, q) দুটি উপাদান p এবং q এর জন্য তাদের রুট প্যারেন্ট খুঁজে বের করে, এবং যদি তারা আলাদা সেটে থাকে, তবে তাদের একটি করে একত্রিত করে। union by rank ব্যবহার করা হয় যাতে গাছের উচ্চতা কম থাকে।
3. Connected Operation: connected(p, q) চেক করে যে, p এবং q একই সেটে (একই রুট প্যারেন্টে) রয়েছে কি না।

আউটপুট:

true
true
false

সারাংশ

Union-Find বা Disjoint Set Union (DSU) একটি শক্তিশালী ডাটা স্ট্রাকচার যা বিশেষভাবে MST (Minimum Spanning Tree) অ্যালগরিদম, Cycle Detection এবং Network Connectivity সমস্যা সমাধানে ব্যবহৃত হয়। এই ডাটা স্ট্রাকচারটি দুটি প্রধান অপারেশন Union (এলিমেন্টগুলো একত্রিত করা) এবং Find (একটি উপাদান কোন সেটের অন্তর্ভুক্ত তা খুঁজে বের করা) এর জন্য ব্যবহার করা হয়।

অপটিমাইজেশন:

• Path Compression: find অপারেশনটি দ্রুত করার জন্য।
• Union by Rank: union অপারেশনটি দ্রুত করার জন্য, গাছের উচ্চতা কমানোর জন্য।

এই কৌশলটি Greedy Algorithm এবং Graph Theory এর বিভিন্ন সমস্যা সমাধানে ব্যাপকভাবে ব্যবহৃত হয়।

Treap এবং Splay Tree দুটি উদ্ভাবনী ডেটা স্ট্রাকচার যা ব্যালেন্সড বাইনারি সার্চ ট্রি (BST) এর মাধ্যমে কাজ করে, তবে সেগুলির নিজস্ব আলাদা বৈশিষ্ট্য এবং অ্যালগরিদম রয়েছে। এই ট্রি গুলি self-balancing এবং efficient সার্চ, ইনসার্ট এবং ডিলিট অপারেশন প্রদান করে। আসুন Treap এবং Splay Tree এর গঠন এবং কার্যকারিতা বুঝে দেখি এবং এগুলির সাথে সম্পর্কিত জাভা উদাহরণ দেখব।

১. Treap

Treap হল একটি বিশেষ ধরনের বাইনারি সার্চ ট্রি যা দুটি বৈশিষ্ট্য ধারণ করে:

1. Binary Search Tree (BST) Property: প্রতিটি নোডের বামদিকে তার চেয়ে ছোট মান থাকে এবং ডানদিকে তার চেয়ে বড় মান থাকে।
2. Heap Property: প্রতিটি নোডের মান তার প্যারেন্টের মানের চেয়ে ছোট বা সমান হতে হবে, যা সাধারণত একটি max-heap বা min-heap এর মতো থাকে।

Treap এ randomized balancing পদ্ধতি ব্যবহার করা হয়, যার ফলে ট্রি গুলি log(n) গভীরতায় থাকে এবং ব্যালেন্সড থাকে, যা সার্চ, ইনসার্ট এবং ডিলিট অপারেশনের জন্য O(log n) সময় জটিলতা প্রদান করে।

উদাহরণ: Treap in Java

import java.util.Random;

class Treap {
    static class Node {
        int value, priority;
        Node left, right;

        public Node(int value) {
            this.value = value;
            this.priority = new Random().nextInt();  // Random priority
            this.left = this.right = null;
        }
    }

    private Node root;

    // Rotate function to maintain heap property
    private Node rightRotate(Node node) {
        Node newRoot = node.left;
        node.left = newRoot.right;
        newRoot.right = node;
        return newRoot;
    }

    private Node leftRotate(Node node) {
        Node newRoot = node.right;
        node.right = newRoot.left;
        newRoot.left = node;
        return newRoot;
    }

    // Insert function to insert a new value
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private Node insertRec(Node node, int value) {
        if (node == null) return new Node(value);

        // BST insertion
        if (value < node.value)
            node.left = insertRec(node.left, value);
        else if (value > node.value)
            node.right = insertRec(node.right, value);
        else
            return node;  // Duplicate values are not allowed

        // Heap property adjustment
        if (node.left != null && node.left.priority > node.priority)
            node = rightRotate(node);
        if (node.right != null && node.right.priority > node.priority)
            node = leftRotate(node);

        return node;
    }

    // Preorder Traversal to print Treap
    public void preorder() {
        preorderRec(root);
    }

    private void preorderRec(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderRec(node.left);
            preorderRec(node.right);
        }
    }

    public static void main(String[] args) {
        Treap treap = new Treap();
        treap.insert(50);
        treap.insert(30);
        treap.insert(20);
        treap.insert(40);
        treap.insert(70);
        treap.insert(60);
        treap.insert(80);

        System.out.println("Treap Preorder Traversal:");
        treap.preorder();
    }
}

ব্যাখ্যা:

• rightRotate() এবং leftRotate(): ট্রি এর ব্যালেন্স বজায় রাখতে এই রোটেশন অপারেশন ব্যবহার করা হয়।
• insertRec(): BST বৈশিষ্ট্য অনুসারে ইনসার্ট করার পর, heap property বজায় রাখতে রোটেশন করা হয়।
• preorder(): ইনসার্ট করার পর, preorder traversal এর মাধ্যমে ট্রি প্রিন্ট করা হয়।

আউটপুট:

Treap Preorder Traversal:
50 30 20 40 70 60 80 

২. Splay Tree

Splay Tree হল একটি self-adjusting বাইনারি সার্চ ট্রি, যা splaying অপারেশন ব্যবহার করে কোনো উপাদান খোঁজার পর, সেই উপাদানটিকে শীর্ষে এনে ফেলে। এর মাধ্যমে, কিছু বিশেষ পরিস্থিতিতে অনুসন্ধানটি দ্রুত হতে পারে এবং ট্রি সাইজের পরিবর্তন ঘটানো সহজ হয়।

Splay Tree এর বৈশিষ্ট্য:

1. Splaying: যখন একটি উপাদান খোঁজা হয়, সেক্ষেত্রে সেটি ট্রির শীর্ষে চলে আসে।
2. Self-Balancing: এটি কোনও নির্দিষ্ট ধরনের ব্যালেন্স নিশ্চিত না করলেও, বার বার অ্যাক্সেস হওয়া উপাদানগুলোকে দ্রুত খোঁজা যায়।

উদাহরণ: Splay Tree in Java

class SplayTree {
    static class Node {
        int value;
        Node left, right;

        public Node(int value) {
            this.value = value;
            this.left = this.right = null;
        }
    }

    private Node root;

    // Splay function to bring the node to the root
    private Node splay(Node node, int value) {
        if (node == null || node.value == value) return node;

        if (node.value > value) {
            if (node.left == null) return node;
            if (node.left.value > value) {
                node.left.left = splay(node.left.left, value);
                node = rightRotate(node);
            } else if (node.left.value < value) {
                node.left.right = splay(node.left.right, value);
                if (node.left.right != null) {
                    node.left = leftRotate(node.left);
                }
            }
            return (node.left == null) ? node : rightRotate(node);
        } else {
            if (node.right == null) return node;
            if (node.right.value < value) {
                node.right.right = splay(node.right.right, value);
                node = leftRotate(node);
            } else if (node.right.value > value) {
                node.right.left = splay(node.right.left, value);
                if (node.right.left != null) {
                    node.right = rightRotate(node.right);
                }
            }
            return (node.right == null) ? node : leftRotate(node);
        }
    }

    // Right Rotation
    private Node rightRotate(Node node) {
        Node leftChild = node.left;
        node.left = leftChild.right;
        leftChild.right = node;
        return leftChild;
    }

    // Left Rotation
    private Node leftRotate(Node node) {
        Node rightChild = node.right;
        node.right = rightChild.left;
        rightChild.left = node;
        return rightChild;
    }

    // Insert function for inserting a value into Splay Tree
    public void insert(int value) {
        root = insertRec(root, value);
        root = splay(root, value); // Splay the node to root
    }

    private Node insertRec(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value)
            node.left = insertRec(node.left, value);
        else if (value > node.value)
            node.right = insertRec(node.right, value);
        return node;
    }

    // Search function for finding a value
    public boolean search(int value) {
        root = splay(root, value);
        return (root != null && root.value == value);
    }

    public void preorder() {
        preorderRec(root);
    }

    private void preorderRec(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderRec(node.left);
            preorderRec(node.right);
        }
    }

    public static void main(String[] args) {
        SplayTree tree = new SplayTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Preorder traversal after insertions:");
        tree.preorder();

        System.out.println("\nSearch 40: " + tree.search(40));

        System.out.println("Preorder traversal after search:");
        tree.preorder();
    }
}

ব্যাখ্যা:

• Splay Operation: Splay Tree এর সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্য হল, splay অপারেশনটি যে কোনও উপাদান খোঁজার পর, সেটি শীর্ষে চলে আসে। এই কাজের জন্য রোটেশন (left & right) ব্যবহার করা হয়।
• Insert and Search: প্রতিটি ইনসার্ট বা সার্চের পর, সংশ্লিষ্ট উপাদানটি শীর্ষে চলে আসে।

আউটপুট:

Preorder traversal after insertions:
50 30 20 40 70 60 80 
Search 40: true
Preorder traversal after search:
40 30 20 50 70 60 80 

সারাংশ

Treap এবং Splay Tree হল বিশেষ ধরনের ডেটা স্ট্রাকচার, যা বাইনারি সার্চ ট্রির মতো কাজ করে তবে নিজস্ব কিছু অপারেশন (রোটেশন এবং প্রোপার্টি) ব্যবহার করে এগুলি উন্নত করে।

• Treap একটি randomized BST যা heap property এবং BST property অনুসরণ করে।
• Splay Tree একটি self-adjusting BST যা splaying পদ্ধতি ব্যবহার করে যখন একটি উপাদান অ্যাক্সেস করা হয়, তখন সেটি ট্রির শীর্ষে চলে আসে।

এই দুটি ট্রি ডেটা স্ট্রাকচার পারফরম্যান্সের দিক থেকে কার্যকরী হতে পারে, তবে তাদের নিজস্ব সীমাবদ্ধতা এবং প্রয়োগ ক্ষেত্র রয়েছে।

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** এর মতো অ্যালগরিদমগুলির সাথে ব্যবহার করলে, কার্যকারিতা এবং স্পিডের ক্ষেত্রে উল্লেখযোগ্য উন্নতি সাধিত হয়।