একটি বাইনারি সার্চ ট্রি (BST) এবং দুটি মান k1 ও k2 (k1 < k2) দেওয়া আছে। k1 থেকে k2 রেঞ্জের সব কী ক্রমাগত আউটপুট করুন, স্পেস কমপ্লেক্সিটি O(1) রেখে।
উদাহরণ
BST: (রুট ৬, লেফ্ট ৩, রাইট ২, ইত্যাদি)
k1 = 4, k2 = 10 → আউটপুট: 7 6 9
অ্যালগরিদম: মরিস ট্রাভার্সাল (Morris Traversal)
সাধারণ ইনঅর্ডার ট্রাভার্সালে স্ট্যাক/রিকার্শন লাগে → O(h) স্পেস। মরিস ট্রাভার্সাল থ্রেডেড বাইনারি ট্রি কনসেপ্ট ব্যবহার করে NULL পয়েন্টারগুলোর মাধ্যমে ব্যাকট্র্যাক করে, অতিরিক্ত স্পেস O(1)।
কীভাবে কাজ করে:
- কারেন্ট নোডের লেফ্ট চাইল্ড নেই → প্রসেস করুন, রাইটে যান।
- লেফ্ট চাইল্ড আছে → ইনঅর্ডার প্রিডিসেসর (লেফ্ট সাবট্রির রাইটমোস্ট নোড) খুঁজুন।
- প্রিডিসেসরের রাইট NULL → থ্রেড বানান (রাইট = কারেন্ট), লেফ্টে যান।
- প্রিডিসেসরের রাইট = কারেন্ট → থ্রেড ভাঙুন (রাইট = NULL), কারেন্ট প্রসেস করুন, রাইটে যান।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
node* insertNode(int data) {
node* temp = new node;
temp->data = data;
temp->right = temp->left = NULL;
return temp;
}
void RangeTraversal(node* root, int k1, int k2) {
if (!root) return;
node* curr = root;
while (curr) {
if (curr->left == NULL) {
if (curr->data <= k2 && curr->data >= k1)
cout << curr->data << " ";
curr = curr->right;
} else {
node* pred = curr->left;
while (pred->right != NULL && pred->right != curr)
pred = pred->right;
if (pred->right == NULL) {
pred->right = curr;
curr = curr->left;
} else {
pred->right = NULL;
if (curr->data <= k2 && curr->data >= k1)
cout << curr->data << " ";
curr = curr->right;
}
}
}
}
int main() {
node* root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(2);
root->left->left = insertNode(1);
root->left->right = insertNode(7);
root->right->right = insertNode(9);
cout << "All BST keys in the given range are \t";
RangeTraversal(root, 4, 10);
return 0;
}
আউটপুট
All BST keys in the given range are 7 6 9
মূল পয়েন্ট
- মরিস ট্রাভার্সাল থ্রেডেড বাইনারি ট্রি কনসেপ্ট ব্যবহার করে।
- কোনো স্ট্যাক, কিউ বা রিকার্শন লাগে না → O(1) এক্সট্রা স্পেস।
- ট্রি মডিফাই হয় ট্রাভার্সালের সময় কিন্তু শেষে রিস্টোর হয়ে যায়।
- BST-এ ইনঅর্ডার = সোর্টেড অর্ডার, তাই রেঞ্জ কোয়েরি সহজ।
