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

C++ में BST का मेडियन O(n) समय और O(1) स्पेस में खोजें


कॉन्सेप्ट

दिए गए बाइनरी सर्च ट्री (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 का इनऑर्डर ट्रैवर्सल चाहिए क्योंकि यह क्रमबद्ध क्रम में होता है। समस्या यह है कि रिकर्सन और स्टैक दोनों अतिरिक्त स्पेस का उपयोग करते हैं, जो यहाँ अनुमत नहीं है।

समाधान है मॉरिस इनऑर्डर ट्रैवर्सल का उपयोग करना, जिसे किसी अतिरिक्त स्पेस की आवश्यकता नहीं होती।

मॉरिस इनऑर्डर ट्रैवर्सल चरण:

  1. current को रूट के रूप में इनिशियलाइज़ करें।
  2. जब तक current NULL न हो:
    • यदि current का बायाँ चाइल्ड नहीं है:
      • current का डेटा प्रिंट करें।
      • दाईं ओर जाएँ: current = current->right।
    • अन्यथा:
      • current के बाएँ सबट्री में सबसे दाएँ नोड (इनऑर्डर प्रीडिसेसर) ढूंढें।
      • उसके राइट चाइल्ड को current पर सेट करें।
      • बाएँ चाइल्ड पर जाएँ: current = current->left।

अंतिम कार्यान्वयन:

  1. मॉरिस इनऑर्डर ट्रैवर्सल का उपयोग करके BST में नोड्स की संख्या गिनें।
  2. फिर से मॉरिस इनऑर्डर ट्रैवर्सल करें, नोड्स गिनते हुए और जांचें कि क्या काउंट मेडियन पॉइंट के बराबर है।
  3. सम नोड्स के लिए पिछले नोड को ट्रैक करने के लिए एक अतिरिक्त पॉइंटर उपयोग करें।

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
  1. C++ में इनऑर्डर ट्रैवर्सल में n-वां नोड ढूंढना C++ में इनऑर्डर ट्रैवर्सल में n-वां नोड ढूंढना

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

  1. C++ में BST में Inorder Successor (द्वितीय संस्करण) C++ में BST में Inorder Successor (द्वितीय संस्करण)

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री में एक नोड है, हमें उस नोड का इन-ऑर्डर सक्सेसर BST में ढूंढना है। यदि कोई इन-ऑर्डर सक्सेसर नहीं है, तो null लौटाएँ। जैसा कि हम जानते हैं कि एक नोड का सक्सेसर वह नोड है जिसका कुंजी मान नोड के मान से सबसे छोटा बड़ा होता है। हमें नोड तक सीधी पहुंच होगी लेकिन ट्र

  1. Python में BST का माध्यिका O(n) समय और O(1) स्थान में ढूंढना Python में BST का माध्यिका O(n) समय और O(1) स्थान में ढूंढना

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