अवधारणा
किसी दिए गए बाइनरी सर्च ट्री (BST) के संबंध में, हमारा कार्य इसका माध्यिका निर्धारित करना है।
यहां तक कि नहीं के लिए भी। नोड्स का, माध्यिका =((n/2th नोड + (n+1)/2th नोड)/2 नोड्स की विषम संख्या के लिए, माध्यिका =(n+1)/2th नोड।
दिए गए BST के लिए (नोड्स की विषम संख्या के साथ) है -
7 / \ 4 9 / \ / \ 2 5 8 10
दिए गए BST का क्रम होगा:2, 4, 5, 7, 8, 9, 10 तो, यहाँ माध्यिका 7 होगी।
दिए गए BST के लिए (नोड्स की सम संख्या के साथ) है -
7 / \ 4 9 / \ / 2 5 8
दिए गए BST के क्रम में होगा - 2, 4, 5, 7, 8, 9
तो, यहाँ माध्यिका होगी (5+7)/2 =6.
विधि
माध्यिका का निर्धारण करने के लिए, हमें BST के इनऑर्डर को निर्धारित करने की आवश्यकता है क्योंकि इसका इनऑर्डर क्रमबद्ध क्रम में होगा और फिर माध्यिका निर्धारित करेगा। यहाँ, अवधारणा O(1) अतिरिक्त स्थान का उपयोग करके BST में K'th सबसे छोटे तत्व पर आधारित है। अब, कार्य बहुत सरल है यदि हमें अतिरिक्त स्थान को लागू करने की अनुमति है लेकिन इनऑर्डर ट्रैवर्सल कार्यान्वयन रिकर्सन और स्टैक दोनों अंतरिक्ष का उपयोग करता है जिसकी यहां अनुमति नहीं है।
इसके परिणामस्वरूप, मॉरिस इनऑर्डर ट्रैवर्सल को निष्पादित करना समाधान है क्योंकि इसके लिए किसी अतिरिक्त स्थान की आवश्यकता नहीं होती है।
मॉरिस इनऑर्डर ट्रैवर्सल को निम्नलिखित तरीके से समझाया गया है -
- हम करंट को रूट के रूप में इनिशियलाइज़ करते हैं
- जबकि करंट NULL नहीं है
अगर करंट में बच्चा नहीं बचा है
- वर्तमान डेटा प्रिंट करें
- दाईं ओर ले जाएँ, यानी करंट =करंट->राइट
-
अन्य
- करंट के बाएं सबट्री में सबसे दाहिने नोड के दाहिने बच्चे के रूप में करंट का निर्माण करें
- इस बाएं बच्चे को ले जाएं, यानी, करंट =करंट->बाएं
अंतिम कार्यान्वयन पर निम्नलिखित तरीके से चर्चा की गई है -
-
हम संख्या गिनते हैं। मॉरिस इनऑर्डर ट्रैवर्सल को लागू करने वाले दिए गए बीएसटी में नोड्स की संख्या।
-
उसके बाद नोड्स की गिनती करके और यह सत्यापित करके मॉरिस इनऑर्डर ट्रैवर्सल एक बार और करें कि क्या गिनती मध्य बिंदु के बराबर है।
विचार करने के लिए भी नहीं। नोड्स के पिछले नोड की ओर इशारा करते हुए एक अतिरिक्त सूचक लागू किया गया है।
उदाहरण
/* C++ program to find the median of BST in O(n) time and O(1)
space*/
#include<bits/stdc++.h>
using namespace std;
/* Implements a binary search tree Node1 which has data, pointer
to left child and a pointer to right child */
struct Node1{
int data1;
struct Node1* left1, *right1;
};
//Shows a utility function to create a new BST node
struct Node1 *newNode(int item1){
struct Node1 *temp1 = new Node1;
temp1->data1 = item1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
/* Shows a utility function to insert a new node with
given key in BST */
struct Node1* insert(struct Node1* node1, int key1){
/* It has been seen that if the tree is empty, return a new node
*/
if (node1 == NULL) return newNode(key1);
/* Else, recur down the tree */
if (key1 < node1->data1)
node1->left1 = insert(node1->left1, key1);
else if (key1 > node1->data1)
node1->right1 = insert(node1->right1, key1);
/* return the (unchanged) node pointer */
return node1;
}
/* Shows function to count nodes in a binary search tree
using Morris Inorder traversal*/
int counNodes(struct Node1 *root1){
struct Node1 *current1, *pre1;
// Used to initialise count of nodes as 0
int count1 = 0;
if (root1 == NULL)
return count1;
current1 = root1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count node if its left is NULL
count1++;
// Go to its right
current1 = current1->right1;
} else {
/* Determine the inorder predecessor of current */
pre1 = current1->left1;
while (pre1->right1 != NULL &&
pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder predecessor */
if(pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* we have to revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
// Now increment count if the current
// node is to be visited
count1++;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
return count1;
}
/* Shows function to find median in O(n) time and O(1) space
using Morris Inorder traversal*/
int findMedian(struct Node1 *root1){
if (root1 == NULL)
return 0;
int count1 = counNodes(root1);
int currCount1 = 0;
struct Node1 *current1 = root1, *pre1, *prev1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count current node
currCount1++;
// Verify if current node is the median
// Odd case
if (count1 % 2 != 0 && currCount1 == (count1+1)/2)
return prev1->data1;
// Even case
else if (count1 % 2 == 0 && currCount1 == (count1/2)+1)
return (prev1->data1 + current1->data1)/2;
// Now update prev1 for even no. of nodes
prev1 = current1;
//Go to the right
current1 = current1->right1;
} else {
/* determine the inorder predecessor of current1 */
pre1 = current1->left1;
while (pre1->right1 != NULL && pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder
predecessor */
if (pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* We have to revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
prev1 = pre1;
// Now count current node
currCount1++;
// Verify if the current node is the median
if (count1 % 2 != 0 && currCount1 == (count1+1)/2 )
return current1->data1;
else if (count1%2==0 && currCount1 == (count1/2)+1)
return (prev1->data1+current1->data1)/2;
// Now update prev1 node for the case of even
// no. of nodes
prev1 = current1;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
}
/* Driver program to test above functions*/
int main(){
/* Let us create following BST
7
/ \
4 9
/ \ / \
2 5 8 10 */
struct Node1 *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 << "\nMedian of BST is(for odd no. of nodes) "<< findMedian(root1) <<endl;
/* Let us create following BST
7
/ \
4 9
/ \ /
2 5 8
*/
struct Node1 *root2 = NULL;
root2 = insert(root2, 7);
insert(root2, 4);
insert(root2, 2);
insert(root2, 5);
insert(root2, 9);
insert(root2, 8);
cout << "\nMedian of BST is(for even no. of nodes) "
<< findMedian(root2);
return 0;
} आउटपुट
Median of BST is(for odd no. of nodes) 7 Median of BST is(for even no. of nodes) 6