कॉन्सेप्ट
दिए गए बाइनरी सर्च ट्री (BST) के संबंध में, हमारा कार्य उसका मेडियन निर्धारित करना है।
सम नोड्स के लिए: मेडियन = ((n/2वां नोड + (n+1)/2वां नोड) / 2)
विषम नोड्स के लिए: मेडियन = (n+1)/2वां नोड।
उदाहरण
विषम नोड्स वाला BST:
7
/ \
4 9
/ \ / \
2 5 8 10
इनऑर्डर: 2, 4, 5, 7, 8, 9, 10 → मेडियन = 7
सम नोड्स वाला BST:
7
/ \
4 9
/ \ /
2 5 8
इनऑर्डर: 2, 4, 5, 7, 8, 9 → मेडियन = (5+7)/2 = 6
विधि
मेडियन निर्धारित करने के लिए, हमें BST का इनऑर्डर ट्रैवर्सल चाहिए क्योंकि यह क्रमबद्ध क्रम में होता है। समस्या यह है कि रिकर्सन और स्टैक दोनों अतिरिक्त स्पेस का उपयोग करते हैं, जो यहाँ अनुमत नहीं है।
समाधान है मॉरिस इनऑर्डर ट्रैवर्सल का उपयोग करना, जिसे किसी अतिरिक्त स्पेस की आवश्यकता नहीं होती।
मॉरिस इनऑर्डर ट्रैवर्सल चरण:
currentको रूट के रूप में इनिशियलाइज़ करें।- जब तक
currentNULL न हो:- यदि
currentका बायाँ चाइल्ड नहीं है:currentका डेटा प्रिंट करें।- दाईं ओर जाएँ:
current = current->right।
- अन्यथा:
currentके बाएँ सबट्री में सबसे दाएँ नोड (इनऑर्डर प्रीडिसेसर) ढूंढें।- उसके राइट चाइल्ड को
currentपर सेट करें। - बाएँ चाइल्ड पर जाएँ:
current = current->left।
- यदि
अंतिम कार्यान्वयन:
- मॉरिस इनऑर्डर ट्रैवर्सल का उपयोग करके BST में नोड्स की संख्या गिनें।
- फिर से मॉरिस इनऑर्डर ट्रैवर्सल करें, नोड्स गिनते हुए और जांचें कि क्या काउंट मेडियन पॉइंट के बराबर है।
- सम नोड्स के लिए पिछले नोड को ट्रैक करने के लिए एक अतिरिक्त पॉइंटर उपयोग करें।
C++ कार्यान्वयन
/* C++ प्रोग्राम BST का मेडियन O(n) समय और O(1) स्पेस में खोजने के लिए */
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node *newNode(int item) {
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
Node* insert(Node* node, int key) {
if (node == NULL) return newNode(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
return node;
}
int countNodes(Node *root) {
Node *current, *pre;
int count = 0;
if (root == NULL) return count;
current = root;
while (current != NULL) {
if (current->left == NULL) {
count++;
current = current->right;
} else {
pre = current->left;
while (pre->right != NULL && pre->right != current)
pre = pre->right;
if (pre->right == NULL) {
pre->right = current;
current = current->left;
} else {
pre->right = NULL;
count++;
current = current->right;
}
}
}
return count;
}
int findMedian(Node *root) {
if (root == NULL) return 0;
int count = countNodes(root);
int currCount = 0;
Node *current = root, *pre, *prev = NULL;
while (current != NULL) {
if (current->left == NULL) {
currCount++;
if (count % 2 != 0 && currCount == (count + 1) / 2)
return current->data;
else if (count % 2 == 0 && currCount == (count / 2) + 1)
return (prev->data + current->data) / 2;
prev = current;
current = current->right;
} else {
pre = current->left;
while (pre->right != NULL && pre->right != current)
pre = pre->right;
if (pre->right == NULL) {
pre->right = current;
current = current->left;
} else {
pre->right = NULL;
prev = pre;
currCount++;
if (count % 2 != 0 && currCount == (count + 1) / 2)
return current->data;
else if (count % 2 == 0 && currCount == (count / 2) + 1)
return (prev->data + current->data) / 2;
prev = current;
current = current->right;
}
}
}
return -1; // नहीं मिला
}
int main() {
// विषम नोड्स वाला BST
Node *root1 = NULL;
root1 = insert(root1, 7);
insert(root1, 4); insert(root1, 2); insert(root1, 5);
insert(root1, 9); insert(root1, 8); insert(root1, 10);
cout << "मेडियन (विषम नोड्स): " << findMedian(root1) << endl;
// सम नोड्स वाला BST
Node *root2 = NULL;
root2 = insert(root2, 7);
insert(root2, 4); insert(root2, 2); insert(root2, 5);
insert(root2, 9); insert(root2, 8);
cout << "मेडियन (सम नोड्स): " << findMedian(root2);
return 0;
}
आउटपुट
मेडियन (विषम नोड्स): 7 मेडियन (सम नोड्स): 6