C++ প্রোগ্রাম: অর্ডার-স্ট্যাটিস্টিক অ্যালগরিদম দিয়ে ith লার্জেস্ট নম্বর খুঁজে বের করা

এটি একটি C++ প্রোগ্রাম যা অর্ডার-স্ট্যাটিস্টিক অ্যালগরিদম ব্যবহার করে একটি দেওয়া লিস্ট থেকে ith লার্জেস্ট নম্বর খুঁজে বের করে।

অ্যালগরিদম

শুরু
  ফাংশন Insert() ট্রিতে নোড ইন্সার্ট করার জন্য:
    আর্গুমেন্ট:
      root, d.
    ফাংশনের বডি:
      যদি ট্রি সম্পূর্ণ null থাকে তবে নতুন নোডকে রুট হিসেবে ইন্সার্ট করুন।
      যদি d == tmp->data, সেই নির্দিষ্ট নোডের কাউন্ট বাড়ান।
      যদি d < tmp->data, tmp পয়েন্টারকে বাম চাইল্ডে সরান।
      যদি d > tmp->data, tmp পয়েন্টারকে ডান চাইল্ডে সরান।
শেষ
শুরু
  ফাংশন AssignRank() ট্রির প্রতিটি নোডে র‍্যাঙ্ক অ্যাসাইন করার জন্য:
    আর্গুমেন্ট:
      Root.
    ফাংশনের বডি:
      যদি রুটের বাম চাইল্ড null না থাকে।
        তবে রুটের বাম চাইল্ডকে র‍্যাঙ্ক অ্যাসাইন করুন।
      র‍্যাঙ্ক কাউন্ট বাড়ান।
      যদি রুটের ডান চাইল্ড null না থাকে।
        তবে রুটের ডান চাইল্ডকে র‍্যাঙ্ক অ্যাসাইন করুন।
শেষ
শুরু
  ফাংশন Select() ট্রিতে স্টোর করা ডেটা থেকে Kth স্মোলেস্ট এলিমেন্ট সার্চ করার জন্য:
    আর্গুমেন্ট:
      Root, সার্চ করা এলিমেন্ট k.
    ফাংশনের বডি:
      যদি সমান পাওয়া যায়, main-এ রিটার্ন করুন এবং রেজাল্ট প্রিন্ট করুন।
      অন্যথায় যদি এটি বড় হয় তবে
        টেম্পরারি ভেরিয়েবলকে ডান চাইল্ডে শিফ্ট করুন।
      অন্যথায়
        টেম্পরারি ভেরিয়েবলকে বাম চাইল্ডে শিফ্ট করুন।
শেষ

উদাহরণ

#include <iostream>
using namespace std;

static int cnt = 0;

struct nod { // নোড ডিক্লেয়ারেশন
    int data;
    int rank;
    nod* l;
    nod* r;
};

nod* CreateNod(int d) { // নতুন নোড তৈরি
    nod* newnod = new nod;
    newnod->data = d;
    newnod->rank = 0;
    newnod->l = NULL;
    newnod->r = NULL;
    return newnod;
}

nod* Insert(nod* root, int d) { // ইন্সারশন
    nod* tmp = CreateNod(d);
    nod* t = new nod;
    t = root;
    if (root == NULL)
        root = tmp;
    else {
        while (t != NULL) {
            if (t->data < d) {
                if (t->r == NULL) {
                    t->r = tmp;
                    break;
                }
                t = t->r;
            } else if (t->data > d) {
                if (t->l == NULL) {
                    t->l = tmp;
                    break;
                }
                t = t->l;
            }
        }
    }
    return root;
}

void AssignRank(nod* root) { // নোডগুলোর র‍্যাঙ্ক অ্যাসাইন
    if (root->l != NULL)
        AssignRank(root->l);
    root->rank = cnt;
    cnt++;
    if (root->r != NULL)
        AssignRank(root->r);
}

int Select(nod* root, int k) { // kth লার্জেস্ট এলিমেন্ট সিলেক্ট
    if (root->rank == k)
        return root->data;
    else if (root->rank > k)
        return Select(root->l, k);
    else
        return Select(root->r, k);
}

void display(nod* root) { // ট্রি ডিসপ্লে
    if (root->l != NULL)
        display(root->l);
    cout << "\n data: " << root->data << " rank: " << root->rank;
    if (root->r != NULL)
        display(root->r);
}

int main() {
    char c;
    int n, i, k, a[10] = {4,7,6,1,10,3,2,15,16,20};
    nod* root = new nod;
    root = NULL;
    for (i = 0; i < 10; i++)
        root = Insert(root, a[i]); // insert() ফাংশন কল
    cout << "Enter the value of k: ";
    cin >> k;
    AssignRank(root); // Assignrank() ফাংশন কল
    cout << "\nRank associated to each node:-";
    display(root); // display() ফাংশন কল
    cout << "\n\nThe kth Largest element is: " << Select(root, 10-k);
    return 0;
}

আউটপুট

Enter the value of k: 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 kth Largest element is: 4