ধারণা
একটি প্রদত্ত বাইনারি সার্চ ট্রি (BST) এর ক্ষেত্রে, আমাদের কাজ হল এর মধ্যম নির্ধারণ করা।
এমনকি না জন্য. নোডের মধ্যমা =((n/2ম নোড + (n+1)/2ম নোড) /2 নোডের বিজোড় সংখ্যার জন্য, মধ্যমা =(n+1)/2ম নোড।
প্রদত্ত 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.
পদ্ধতি
মধ্যমা নির্ধারণের জন্য, আমাদের বিএসটি-এর অন্তক্রম নির্ধারণ করতে হবে কারণ এর অন্তর্ক্রমটি সাজানো ক্রমে হবে এবং তারপর মধ্যমা নির্ধারণ করবে। এখানে, ধারণাটি 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
