C++ Programming Code Examples C++ > Sorting Searching Code Examples Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm - Implements Order-Statistic tree. - It is an improvement in BST by adding two more key functions- rank() and select(). - The time complexity of Order-statistic tree generation is O(n+n*log(n)). - Once the tree is constructed, this algorithm takes O(log(n)) to find Kth largest number. - Construct Order-Statistic tree for the given unsorted data array. - Using the select function get the kth largest number from the given data set. - Print the result. - Exit. #include<iostream> using namespace std; static int count = 0; // A structure representing a node of a tree. struct node { int data; int rank; node *left; node *right; }; // A function creating new node of tree and assigning the data. node* CreateNode(int data) { node *newnode = new node; newnode->data = data; newnode->rank = 0; newnode->left = NULL; newnode->right = NULL; return newnode; } // A function to create binary search tree. node* Insert(node* root, int data) { // Create node using data from argument list. node *temp = CreateNode(data); node *t = new node; t = root; // If root is null, assign it to the node created. if(root == NULL) root = temp; else { // Find the position for the new node to be inserted. while(t != NULL) { if(t->data < data ) { if(t->right == NULL) { // If current node is NULL then insert the node. t->right = temp; break; } // Shift pointer to the left. t = t->right; } else if(t->data > data) { if(t->left == NULL) { // If current node is NULL then insert the node. t->left = temp; break; } // Shift pointer to the left. t = t->left; } } } return root; } // A function to assign a rank to each node of the tree. void AssignRank(node *root) { if(root->left != NULL) AssignRank(root->left); root->rank = count; count++; if(root->right != NULL) AssignRank(root->right); } // A function to search Kth smallest element from the data stored in the tree. int Select(node* root, int k) { // Search for the entered rank and shift the pointer accordingly, if rank not matched. if(root->rank == k) return root->data; else if(root->rank > k) return Select(root->left, k); else return Select(root->right, k); } // A function to take an inorder traversal of the tree and print the tree data of each node. void print(node *root) { if(root->left != NULL) print(root->left); cout<<"\n data: "<<root->data<<" rank: "<<root->rank; if(root->right != NULL) print(root->right); } int main() { char ch; int n, i, k, a[20]={40, 54, 96, 1, 9, 66, 78, 73, 36, 74, 44, 23, 35, 96, 38, 41, 49, 88, 27, 97}; node *root = new node; root = NULL; // Construct the BST. for(i = 0; i < 20; i++) root = Insert(root, a[i]); cout<<"Enter the k value: "; cin>>k; // Assign rank to each of the nodes of the Binary Search tree. AssignRank(root); // Inorder traversal of the tree and displaying the data and the rank corresponding to that data. cout<<"\nRank associated to each node:-"; print(root); // Print the result. cout<<"\n\nThe kth Largest element is: "<<Select(root, 20-k); return 0; }