C++-এ ট্রাই (Trie) ডেটা স্ট্রাকচার ইমপ্লিমেন্টেশন

এখানে আমরা C++-এ ট্রাই (Trie) ইমপ্লিমেন্টেশন নিয়ে আলোচনা করব। এটি একটি ট্রি-বেজড (tree-based) ডেটা স্ট্রাকচার, যা স্ট্রিংয়ের বড় ডেটাসেট থেকে কী (key) দ্রুত খুঁজে বের করতে ব্যবহৃত হয়।

ফাংশন ও সিউডোকোড

function insert():
    যদি কী না থাকে, তবে ট্রাইতে কী ইনসার্ট করুন। যদি কী ট্রাই নোডের প্রিফিক্স হয়, শুধু লিফ নোডটি মার্ক করুন।
end

function deleteNode():
    যদি ট্রি খালি হয়, তবে NULL রিটার্ন করুন।
    যদি কী-এর শেষ ক্যারেক্টার প্রসেস হয়, তবে সেই নোড আর স্ট্রিংয়ের শেষ নয়।
    যদি দেওয়া কী অন্য কোনো স্ট্রিংয়ের প্রিফিক্স না হয়, তবে ডিলিট করুন এবং রুট = NULL সেট করুন।
    যদি কী শেষ ক্যারেক্টার না হয়, তবে ASCII ভ্যালু ব্যবহার করে চাইল্ড নোডে রিকার্শন করুন।
    যদি রুটের কোনো চাইল্ড না থাকে এবং সেটি অন্য কোনো ওয়ার্ডের শেষ না হয়, তবে ডিলিট করুন এবং রুট = NULL সেট করুন।
end

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

const int ALPHA_SIZE = 26;

struct Trie {
    struct Trie *child[ALPHA_SIZE];
    bool endofstring; // true হলে নোডটি ওয়ার্ডের শেষ রিপ্রেজেন্ট করে
};

struct Trie *createNode(void) { // নতুন নোড তৈরি
    struct Trie *tNode = new Trie;
    tNode->endofstring = false;
    for (int i = 0; i < ALPHA_SIZE; i++)
        tNode->child[i] = NULL;
    return tNode;
}

void insert(struct Trie *root, string key) {
    struct Trie *curr = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'A';
        if (!curr->child[index])
            curr->child[index] = createNode();
        curr = curr->child[index];
    }
    curr->endofstring = true; // শেষ নোডকে লিফ হিসেবে মার্ক
}

bool search(struct Trie *root, string key) { // কী ট্রাইতে আছে কিনা চেক
    struct Trie *curr = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'A';
        if (!curr->child[index])
            return false;
        curr = curr->child[index];
    }
    return (curr != NULL && curr->endofstring);
}

bool isEmpty(Trie* root) { // রুটের চাইল্ড আছে কিনা চেক
    for (int i = 0; i < ALPHA_SIZE; i++)
        if (root->child[i])
            return false;
    return true;
}

Trie* deletion(Trie* root, string key, int depth = 0) {
    if (!root)
        return NULL;
    if (depth == key.size()) { // কী-এর শেষ ক্যারেক্টার প্রসেস হচ্ছে
        if (root->endofstring)
            root->endofstring = false; // সেটি আর স্ট্রিংয়ের শেষ নয়
        if (isEmpty(root)) { // কী অন্য স্ট্রিংয়ের প্রিফিক্স না হলে
            delete (root);
            root = NULL;
        }
        return root;
    }
    // কী শেষ ক্যারেক্টার না হলে
    int index = key[depth] - 'A';
    root->child[index] = deletion(root->child[index], key, depth + 1); // ASCII দিয়ে চাইল্ডে রিকার্শন
    if (isEmpty(root) && root->endofstring == false) { // রুটের চাইল্ড নেই এবং অন্য ওয়ার্ডের শেষ নয়
        delete (root);
        root = NULL;
    }
    return root;
}

int main() {
    string inputs[] = {"HELLOWORLD","HI","BYE", "THE","THENA"}; // ইনপুট কী (শুধু বড় হাতের A-Z)
    int n = sizeof(inputs)/sizeof(inputs[0]);
    struct Trie *root = createNode();
    for (int i = 0; i < n; i++)
        insert(root, inputs[i]);
    search(root, "HELLOWORLD")? cout << "Key is Found\n" : cout << "Key is not Found\n";
    search(root, "HE")? cout << "Key is Found\n" : cout << "Key is not Found\n";
    deletion(root, "THEN")? cout << "Key is deleted\n" : cout << "Key is not Deleted\n";
    return 0;
}

আউটপুট

Key is Found
Key is not Found
Key is deleted