Trie এর Operations (Insertion, Searching, Deletion) গাইড ও নোট

Trie (যাকে Prefix Tree বা Digital Tree বলা হয়) একটি বিশেষ ধরনের ট্রী ডাটা স্ট্রাকচার যা মূলত স্ট্রিংগুলোকে সংরক্ষণ এবং অনুসন্ধান করার জন্য ব্যবহৃত হয়। এটি মূলত অক্ষরের প্যাটার্ন অনুসারে ডেটা স্টোর করার জন্য ব্যবহৃত হয় এবং স্ট্রিং অনুসন্ধান ও ইনসার্ট করার জন্য খুবই কার্যকরী।

Trie একটি শক্তিশালী ডাটা স্ট্রাকচার, যা স্ট্রিং সংক্রান্ত অপারেশনগুলিকে দ্রুত করতে সহায়তা করে। Trie তে প্রতিটি নোড একটি অক্ষর প্রতিনিধিত্ব করে এবং এটি স্ট্রিংয়ের প্রিফিক্স ভিত্তিক স্টোরেজ এবং অনুসন্ধান পরিচালনা করে।

এই টিউটোরিয়ালে আমরা Trie এর তিনটি মৌলিক অপারেশন - Insertion, Searching, এবং Deletion সম্পর্কে আলোচনা করব।

1. Trie Data Structure

Trie হল একটি বৃক্ষ (Tree) ভিত্তিক ডাটা স্ট্রাকচার যেখানে প্রতিটি নোড একটি অক্ষর প্রতিনিধিত্ব করে এবং স্ট্রিং সংরক্ষণের জন্য একটি কমপ্যাক্ট পদ্ধতি প্রস্তাব করে। এটি একটি Prefix Tree হিসাবে কাজ করে এবং একটি স্ট্রিংয়ের প্রতিটি অক্ষরকে একটি নির্দিষ্ট স্তরে সংরক্ষণ করে।

2. Trie Node Structure

একটি Trie Node সাধারণত দুটি প্রধান অংশে বিভক্ত:

• children: একটি ডেটা স্ট্রাকচার (যেমন, Map বা Array) যা বর্তমান নোডের পুত্র (children) প্রতিনিধিত্ব করে।
• isEndOfWord: একটি বুলিয়ান মান যা চিহ্নিত করে যে এই নোডটি একটি পূর্ণ স্ট্রিংয়ের শেষ নোড কিনা।

3. Insertion in Trie

Insertion অপারেশনটি একটি নতুন স্ট্রিং Trie তে যুক্ত করার জন্য ব্যবহৃত হয়। এই প্রক্রিয়াতে স্ট্রিংটির প্রতিটি অক্ষর Trie তে ইনসার্ট করা হয় এবং isEndOfWord ফ্ল্যাগটি সেই অক্ষরের জন্য true করা হয়, যদি তা স্ট্রিংয়ের শেষ হয়।

উদাহরণ: Insertion in Trie

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();
    }

    // Insert a word into the Trie
    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;  // Mark the end of the word
    }

    // Display the Trie (optional)
    public void display() {
        displayHelper(root, "");
    }

    private void displayHelper(TrieNode node, String word) {
        if (node.isEndOfWord) {
            System.out.println(word);
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                displayHelper(node.children[i], word + (char) (i + 'a'));
            }
        }
    }
}

public class TrieExample {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        trie.insert("banana");
        
        // Display the inserted words
        trie.display();
    }
}

ব্যাখ্যা:

1. Insertion: insert() ফাংশনে প্রতিটি অক্ষরকে TrieNode তে ইনসার্ট করা হয়। শেষের নোডে isEndOfWord true করা হয়, যা নির্দেশ করে যে এটি একটি পূর্ণ স্ট্রিং।
2. display(): এটি ট্রি ডেটা স্ট্রাকচারটি প্রদর্শন করার জন্য একটি সহায়ক ফাংশন।

আউটপুট:

apple
app
banana

4. Searching in Trie

Searching অপারেশনটি স্ট্রিংটি Trie তে উপস্থিত কিনা তা যাচাই করার জন্য ব্যবহৃত হয়। এটি স্ট্রিংটির প্রতিটি অক্ষরের জন্য চেক করে এবং শেষে isEndOfWord ফ্ল্যাগটি চেক করে।

উদাহরণ: Searching in Trie

class Trie {
    private TrieNode root;

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

    // Insert a word into the Trie
    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;
    }

    // Search for a word in the Trie
    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;  // Word does not exist
            }
            node = node.children[index];
        }
        return node.isEndOfWord;  // Return true if it's the end of a word
    }
}

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

        System.out.println("Search for 'apple': " + trie.search("apple")); // true
        System.out.println("Search for 'app': " + trie.search("app")); // true
        System.out.println("Search for 'banana': " + trie.search("banana")); // false
    }
}

ব্যাখ্যা:

1. search(): এই ফাংশনটি একটি শব্দের প্রতিটি অক্ষরের জন্য ট্রি অনুসন্ধান করে এবং শেষের নোডে isEndOfWord চেক করে, যদি এটি true হয়, তবে স্ট্রিংটি পাওয়া গেছে।

আউটপুট:

Search for 'apple': true
Search for 'app': true
Search for 'banana': false

5. Deletion in Trie

Deletion অপারেশনটি একটি শব্দ Trie থেকে মুছে ফেলার জন্য ব্যবহৃত হয়। এটি একটি রিকার্সিভ অপারেশন, যেখানে আমরা প্রথমে শব্দটি খুঁজে বের করি এবং তারপর নোডগুলো থেকে প্রয়োজনীয় পরিবর্তন করি।

উদাহরণ: Deletion in Trie

class Trie {
    private TrieNode root;

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

    // Insert a word into the Trie
    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;
    }

    // Delete a word from the Trie
    public boolean delete(String word) {
        return deleteHelper(root, word, 0);
    }

    private boolean deleteHelper(TrieNode node, String word, int index) {
        if (index == word.length()) {
            if (!node.isEndOfWord) {
                return false;  // Word does not exist
            }
            node.isEndOfWord = false;  // Unmark the end of word
            return node.childrenAreEmpty();  // Check if it can be deleted
        }

        char ch = word.charAt(index);
        int childIndex = ch - 'a';
        TrieNode childNode = node.children[childIndex];

        if (childNode == null) {
            return false;  // Word does not exist
        }

        boolean canDeleteCurrentNode = deleteHelper(childNode, word, index + 1);

        if (canDeleteCurrentNode) {
            node.children[childIndex] = null;  // Delete the reference to child
            return node.childrenAreEmpty() && !node.isEndOfWord;
        }
        return false;
    }

    // Utility function to check if a node has no children
    private boolean childrenAreEmpty() {
        for (TrieNode child : children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }
}

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

        System.out.println("Delete 'apple': " + trie.delete("apple")); // true
        System.out.println("Search for 'apple': " + trie.search("apple")); // false
    }
}

ব্যাখ্যা:

1. deleteHelper(): এটি রিকার্সিভভাবে শব্দটি মুছে ফেলে, এবং যখন সমস্ত অংশ মুছে ফেলা হয়ে যায়, তখন পুরনো নোড গুলি ধীরে ধীরে মুছে ফেলে দেওয়া হয়।
2. childrenAreEmpty(): এটি একটি সহায়ক ফাংশন যা চেক করে যে কোন নোডের কোনও শিশু নেই কি না।

আউটপুট:

Delete 'apple': true
Search for 'apple': false

সারাংশ

Trie একটি কার্যকরী ডাটা স্ট্রাকচার যা স্ট্রিং সংরক্ষণের জন্য ব্যবহৃত হয় এবং এটি স্ট্রিংয়ের প্রিফিক্স অনুসারে ডেটা প্রক্রিয়াকরণ করে। এতে তিনটি মৌলিক অপারেশন হল:

1. Insertion: স্ট্রিংটি Trie তে ইনসার্ট করা হয়।
2. Searching: Trie তে স্ট্রিংটি খোঁজা হয়।
3. Deletion: Trie থেকে স্ট্রিংটি মুছে ফেলা হয়।

Java তে Trie ব্যবহারের মাধ্যমে আমরা দ্রুত স্ট্রিং অনুসন্ধান এবং সংরক্ষণ করতে পারি, এবং এটি বিভিন্ন প্রোগ্রামিং সমস্যার সমাধানে অত্যন্ত কার্যকরী।