यहां हम C++ प्रोग्राम के बारे में चर्चा करेंगे जो ट्राई (Trie) को कार्यान्वित करता है। यह एक ट्री-आधारित डेटा स्ट्रक्चर है, जिसका उपयोग स्ट्रिंग्स के बड़े डेटा-सेट में कुंजी की कुशल पुनर्प्राप्ति के लिए किया जाता है।
फंक्शन्स और स्यूडोकोड
function insert():
यदि कुंजी मौजूद नहीं है, तो कुंजी को ट्राई में इन्सर्ट करें।
यदि कुंजी ट्राई नोड का प्रीफिक्स है, तो बस लीफ नोड को मार्क करें।
end
function deleteNode():
यदि ट्री खाली है तो null लौटाएं।
यदि कुंजी का अंतिम कैरेक्टर प्रोसेस हो रहा है,
तो वह नोड डिलीट करने के बाद स्ट्रिंग का अंत नहीं रहेगा।
यदि दी गई कुंजी किसी अन्य स्ट्रिंग का प्रीफिक्स नहीं है, तो इसे डिलीट करें और root = NULL सेट करें।
यदि कुंजी अंतिम कैरेक्टर नहीं है,
तो ASCII मान का उपयोग करके प्राप्त होने वाले चाइल्ड के लिए रिकर्सन करें।
यदि रूट का कोई चाइल्ड नहीं बचा और यह किसी अन्य शब्द का अंत नहीं है,
तो इसे डिलीट करें और root = NULL सेट करें।
end
उदाहरण
#include <bits/stdc++.h>
using namespace std;
const int ALPHA_SIZE = 26;
struct Trie {
struct Trie *child[ALPHA_SIZE];
bool endofstring; // यह सच है यदि नोड शब्द के अंत को दर्शाता है
};
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) {
// यदि ट्री खाली है तो null लौटाएं
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
ट्राई (प्रीफिक्स ट्री) स्ट्रिंग ऑपरेशन्स जैसे खोज, इन्सर्शन, डिलीशन और प्रीफिक्स मैचिंग के लिए O(L) टाइम कॉम्प्लेक्सिटी प्रदान करता है जहां L स्ट्रिंग की लंबाई है। यह ऑटोकंप्लीट, स्पेल चेकर्स और IP रूटिंग टेबल्स में व्यापक रूप से उपयोग किया जाता है।