C++ प्रोग्राम: ऑर्डर-स्टैटिस्टिक एल्गोरिदम द्वारा ith लार्जेस्ट नंबर खोजना

यह C++ प्रोग्राम ऑर्डर-स्टैटिस्टिक ट्री (Order-Statistic Tree) का उपयोग करके दी गई लिस्ट से kth लार्जेस्ट (kवां सबसे बड़ा) एलिमेंट खोजता है। प्रत्येक नोड को उसकी रैंक (इनऑर्डर ट्रैवर्सल में पोजीशन) असाइन की जाती है।

एल्गोरिदम

शुरुआत
  1. फंक्शन Insert() - BST में नोड इन्सर्ट करें
  2. फंक्शन AssignRank() - प्रत्येक नोड को रैंक असाइन करें (इनऑर्डर ट्रैवर्सल):
     - यदि लेफ्ट चाइल्ड मौजूद है, तो लेफ्ट चाइल्ड को रैंक असाइन करें
     - रैंक काउंट बढ़ाएं
     - यदि राइट चाइल्ड मौजूद है, तो राइट चाइल्ड को रैंक असाइन करें
  3. फंक्शन Select() - ट्री में संग्रहीत डेटा से kth स्मालेलस्ट खोजें:
     - यदि रैंक k के बराबर है, तो डेटा लौटाएं
     - यदि रैंक > k है, तो लेफ्ट चाइल्ड में सर्च करें
     - अन्यथा राइट चाइल्ड में सर्च करें
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

static int cnt = 0;

struct Node {
    int data;
    int rank;
    Node *left, *right;
};

Node* CreateNode(int d) {
    Node *newNode = new Node;
    newNode->data = d;
    newNode->rank = 0;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

Node* Insert(Node* root, int d) {
    Node *tmp = CreateNode(d);
    Node *t = root;
    
    if (root == nullptr)
        root = tmp;
    else {
        while (t != nullptr) {
            if (t->data < d) {
                if (t->right == nullptr) {
                    t->right = tmp;
                    break;
                }
                t = t->right;
            } else if (t->data > d) {
                if (t->left == nullptr) {
                    t->left = tmp;
                    break;
                }
                t = t->left;
            }
        }
    }
    return root;
}

void AssignRank(Node *root) {
    if (root->left != nullptr)
        AssignRank(root->left);
    root->rank = cnt++;
    if (root->right != nullptr)
        AssignRank(root->right);
}

int Select(Node* root, int k) {
    if (root->rank == k)
        return root->data;
    else if (root->rank > k)
        return Select(root->left, k);
    else
        return Select(root->right, k);
}

void display(Node *root) {
    if (root->left != nullptr)
        display(root->left);
    cout << "\nData: " << root->data << " Rank: " << root->rank;
    if (root->right != nullptr)
        display(root->right);
}

int main() {
    int k;
    int arr[10] = {4, 7, 6, 1, 10, 3, 2, 15, 16, 20};
    
    Node *root = nullptr;
    for (int i = 0; i < 10; i++)
        root = Insert(root, arr[i]);
    
    cout << "Enter the value of k (1 to 10): ";
    cin >> k;
    
    AssignRank(root);
    cout << "\nRank associated to each node:";
    display(root);
    
    // kth लार्जेस्ट = (n-k)th स्मालेलस्ट (0-आधारित रैंक)
    cout << "\n\nThe " << k << "th Largest element is: " 
         << Select(root, 10 - k);
    return 0;
}

आउटपुट

Enter the value of k (1 to 10): 7
Rank associated to each node:
Data: 1 Rank: 0
Data: 2 Rank: 1
Data: 3 Rank: 2
Data: 4 Rank: 3
Data: 6 Rank: 4
Data: 7 Rank: 5
Data: 10 Rank: 6
Data: 15 Rank: 7
Data: 16 Rank: 8
Data: 20 Rank: 9

The 7th Largest element is: 4

व्याख्या: सॉर्टेड ऐरे: [1, 2, 3, 4, 6, 7, 10, 15, 16, 20]। 7वां लार्जेस्ट = 4th स्मालेलस्ट = 4 (0-आधारित इंडेक्स 3)।

उन्नत संस्करण: ऑगमेंटेड BST (सबट्री साइज स्टोर करके) में इन्सर्ट, डिलीट, सेलेक्ट सभी O(log n) में संभव हैं।