순서 통계 알고리즘을 사용하여 주어진 목록에서 i번째 가장 큰 숫자를 찾는 C++ 프로그램

이것은 Order-Statistic Algorithm을 사용하여 주어진 목록에서 i번째로 큰 수를 찾는 C++ 프로그램입니다.

알고리즘

Begin
   function Insert() to insert nodes into the tree:
   Arguments:
      root, d.
      Body of the function:
      If tree is completely null then insert new node as root.
      If d = tmp->data, increase the count of that particular node.
      If d < tmp->data, move the tmp pointer to the left child.
      If d > tmp->data, move the tmp pointer to the right child.
End
Begin
   function AssignRank() to assign rank to each node of the tree:
   Arguments:
      Root.
      Body of the function:
      If left child of the root is not null.
         Then assign rank to the left child of the root.
      Increase the rank count.
      If right child of the root is not null.
         then assign rank to the right child of the root.
End
Begin
   function Select() to search Kth smallest element from the data stored in the tree:
   Arguments:
      Root, searched element k.
      Body of the function:
      If found to be equal, return to main and print the result.
      Else If it is greater then
         shift the temporary variable to the right child.
      Else
         shift the temporary variable to the left child.
End

예시

#include<iostream>
using namespace std;
static int cnt = 0;
struct nod //declaration of node 
{
   int data;
   int rank;
   nod *l;
   nod *r;
};
nod* CreateNod(int d) //creation of new node
{
   nod *newnod = new nod;
   newnod->data = d;
   newnod->rank = 0;
   newnod->l = NULL;
   newnod->r = NULL;
   return newnod;
}
nod* Insert(nod* root, int d) //perform insertion
{
   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) //assign rank to the nodes
{
   if(root->l!= NULL)
      AssignRank(root->l);
      root->rank = cnt;
      cnt++;
      if(root->r != NULL)
         AssignRank(root->r);
}
int Select(nod* root, int k) //select kth largest element
{
   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) //display the tree.
{
   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]); //call the function insert()
   cout<<"Enter the value of k: ";
   cin>>k;
   AssignRank(root); //call the function Assignrank()
   cout<<"\nRank associated to each node:-";
   display(root); //call the function 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