Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

O(n) समय में BST का माध्यिका और C++ में O(1) स्थान ज्ञात कीजिए

अवधारणा

किसी दिए गए बाइनरी सर्च ट्री (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

  1. सी++ में इनऑर्डर ट्रैवर्सल का एन-वें नोड खोजें

    इस समस्या में, हमें एक बाइनरी ट्री और एक पूर्णांक N दिया जाता है। कार्य एक बाइनरी ट्री के इन-ऑर्डर ट्रैवर्सल में n-वें नोड को खोजना है। बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं। ट्रैवर्सल एक पेड़ के सभी नोड्स पर जाने की एक प्रक्रिया है और उनके मूल्यों को

  1. सी ++ में बीएसटी II में उत्तराधिकारी उत्तराधिकारी

    मान लीजिए कि हमारे पास बाइनरी सर्च ट्री में एक नोड है, हमें बीएसटी में उस नोड के इन-ऑर्डर उत्तराधिकारी को खोजना होगा। यदि कोई इन-ऑर्डर उत्तराधिकारी नहीं है, तो अशक्त लौटें। जैसा कि हम जानते हैं कि नोड का उत्तराधिकारी वह नोड होता है जिसकी कुंजी नोड के मान से अधिक होती है। हमारे पास नोड तक सीधी पहुंच

  1. पायथन में O(n) समय और O(1) स्थान में BST का माध्यिका ज्ञात कीजिए

    मान लीजिए कि हमारे पास बाइनरी सर्च ट्री (BST) है, तो हमें इसका माध्यिका ज्ञात करना होगा। हम नोड्स की सम संख्या के लिए जानते हैं, माध्यिका =((n/2th नोड + (n+1)/2th नोड) /2 विषम संख्या में नोड्स के लिए, माध्यिका =(n+1)/2th नोड। तो, अगर इनपुट पसंद है तो आउटपुट 7 . होगा इसे हल करने के लिए, हम इन चर