C++ Program to Implement Randomized Binary Search Tree

«
»
This C++ Program demonstrates the implementation of Randomized Binary Search Tree.

Here is source code of the C++ Program to demonstrate the implementation of Randomized Binary Search Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  *  C++ Program to Implement Randomized Binary Search Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <cstdlib>   
  11. #define MAX_VALUE 65536
  12. using namespace std;
  13. /*
  14.  * Class RBSTNode 
  15.  */
  16. class RBSTNode
  17. {  
  18.     public: 
  19.         RBSTNode *left, *right;
  20.         int priority, element;  
  21.         /* Constructor */
  22.         RBSTNode()
  23.         {
  24.             this->element = 0;
  25.             this->left = this;
  26.             this->right = this;
  27.             this->priority = MAX_VALUE;         
  28.         }    
  29.          /* Constructor */    
  30.         RBSTNode(int ele)
  31.         {
  32.             RBSTNode(ele, NULL, NULL);         
  33.         } 
  34.         /* Constructor */
  35.         RBSTNode(int ele, RBSTNode *left, RBSTNode *right)         
  36.         {
  37.             this->element = ele;
  38.             this->left = left;
  39.             this->right = right;
  40.             this->priority = rand() % 100 + 1;
  41.         }    
  42. };
  43.  
  44. /*
  45.  * Class RandomizedBinarySearchTree 
  46.  */
  47. class RandomizedBinarySearchTree
  48. {
  49.     private: 
  50.         RBSTNode *root;
  51.         RBSTNode *nil;
  52.     public:
  53.         /* Constructor */
  54.          RandomizedBinarySearchTree()
  55.          {
  56.              root = nil;
  57.          }
  58.          /* Function to check if tree is empty */
  59.          bool isEmpty()
  60.          {
  61.              return root == nil;
  62.          }
  63.          /* Make the tree logically empty **/
  64.          void makeEmpty()
  65.          {
  66.              root = nil;
  67.          }
  68.  
  69.          /* Functions to insert data **/
  70.          void insert(int X)
  71.          {
  72.              root = insert(X, root);
  73.          }
  74.          RBSTNode *insert(int X, RBSTNode *T)\
  75.          {
  76.              if (T == nil)
  77.                  return new RBSTNode(X, nil, nil);
  78.              else if (X < T->element)
  79.              {
  80.                  T->left = insert(X, T->left);
  81.                  if (T->left->priority < T->priority)
  82.                  {
  83.                       RBSTNode *L = T->left;
  84.                       T->left = L->right;
  85.                       L->right = T;
  86.                       return L;
  87.                   }    
  88.              }
  89.              else if (X > T->element)
  90.              {
  91.                  T->right = insert(X, T->right);
  92.                  if (T->right->priority < T->priority)
  93.                  {
  94.                      RBSTNode *R = T->right;
  95.                      T->right = R->left;
  96.                      R->left = T;
  97.                      return R;
  98.                  }
  99.              }
  100.              return T;
  101.          }
  102.          /*
  103.           * Functions to count number of nodes 
  104.           */
  105.          int countNodes()
  106.          {
  107.              return countNodes(root);
  108.          }
  109.  
  110.          int countNodes(RBSTNode *r)
  111.          {
  112.              if (r == nil)
  113.                  return 0;
  114.              else
  115.              {
  116.                  int l = 1;
  117.                  l += countNodes(r->left);
  118.                  l += countNodes(r->right);
  119.                  return l;
  120.              }
  121.          }
  122.          /*
  123.           * Functions to search for an element 
  124.           */
  125.          bool search(int val)
  126.          {
  127.              return search(root, val);
  128.          }
  129.          bool search(RBSTNode *r, int val)
  130.          {
  131.              bool found = false;
  132.              while ((r != nil) && !found)
  133.              {
  134.                  int rval = r->element;
  135.                  if (val < rval)
  136.                      r = r->left;
  137.                  else if (val > rval)
  138.                      r = r->right;
  139.                  else
  140.                  {
  141.                      found = true;
  142.                      break;
  143.                  }
  144.                  found = search(r, val);
  145.              }
  146.              return found;
  147.          }
  148.  
  149.          /*
  150.           * Function for inorder traversal 
  151.           */
  152.          void inorder()
  153.          {
  154.              inorder(root);
  155.          }
  156.  
  157.          void inorder(RBSTNode *r)
  158.          {
  159.              if (r != nil)
  160.              {
  161.                  inorder(r->left);
  162.                  cout<<r->element <<"  ";
  163.                  inorder(r->right);
  164.              }
  165.          }
  166.          /*
  167.           * Function for preorder traversal 
  168.           */
  169.          void preorder()
  170.          {
  171.              preorder(root);
  172.          }
  173.          void preorder(RBSTNode *r)
  174.          {
  175.              if (r != nil)
  176.              {
  177.                  cout<<r->element <<"  ";
  178.                  preorder(r->left);             
  179.                  preorder(r->right);
  180.              }
  181.          }
  182.  
  183.          /*
  184.           * Function for postorder traversal 
  185.           */
  186.          void postorder()
  187.          {
  188.              postorder(root);
  189.          }
  190.          void postorder(RBSTNode *r)
  191.          {
  192.              if (r != nil)
  193.              {
  194.                  postorder(r->left);             
  195.                  postorder(r->right);
  196.                  cout<<r->element <<"  ";
  197.              }
  198.          }         
  199. };     
  200.  
  201. /*
  202.  * Main Contains Menu 
  203.  */
  204.  
  205. int main()
  206. {            
  207.     RandomizedBinarySearchTree rbst; 
  208.     cout<<"Randomized Binary SearchTree Test\n";          
  209.     char ch;
  210.     int choice, item;
  211.     /*
  212.      * Perform tree operations  
  213.      */
  214.     do    
  215.     {
  216.         cout<<"\nRandomized Binary SearchTree Operations\n";
  217.         cout<<"1. Insert "<<endl;
  218.         cout<<"2. Search "<<endl;
  219.         cout<<"3. Count Nodes "<<endl;
  220.         cout<<"4. Check Empty"<<endl;
  221.         cout<<"5. Clear"<<endl;
  222.         cout<<"Enter your choice: ";
  223.         cin>>choice;            
  224.         switch (choice)
  225.         {
  226.         case 1: 
  227.             cout<<"Enter integer element to insert: ";
  228.             cin>>item;
  229.             rbst.insert(item);                     
  230.             break;                          
  231.         case 2: 
  232.             cout<<"Enter integer element to search: ";
  233.             cin>>item;
  234.             if (rbst.search(item))
  235.                 cout<<"Element "<<item<<" found in the Tree"<<endl;
  236.             else
  237.                 cout<<"Element "<<item<<" not found in the Tree"<<endl;
  238.             break;                                          
  239.         case 3: 
  240.             cout<<"Nodes = "<<rbst.countNodes()<<endl;
  241.             break;     
  242.         case 4:
  243.             if (rbst.isEmpty()) 
  244.                 cout<<"Tree is Empty"<<endl;
  245.             else
  246.                 cout<<"Tree is not Empty"<<endl;
  247.             break;
  248.         case 5: 
  249.             cout<<"\nRandomizedBinarySearchTree Cleared"<<endl;
  250.             rbst.makeEmpty();
  251.             break;            
  252.         default: 
  253.             cout<<"Wrong Entry \n ";
  254.             break;   
  255.         }
  256.  
  257.         /**  Display tree  **/ 
  258.         cout<<"\nPost order : ";
  259.         rbst.postorder();
  260.         cout<<"\nPre order : ";
  261.         rbst.preorder();    
  262.         cout<<"\nIn order : ";
  263.         rbst.inorder();
  264.         cout<<"\nDo you want to continue (Type y or n) \n";
  265.         cin>>ch;                  
  266.     } 
  267.     while (ch == 'Y'|| ch == 'y');               
  268.     return 0;
  269. }

$ g++ treap.cpp
$ a.out
 
Randomized Binary SearchTree Test
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 28
 
Post order : 28
Pre order : 28
In order : 28
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 5
 
Post order : 5  28
Pre order : 28  5
In order : 5  28
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 63
 
Post order : 5  28  63
Pre order : 63  28  5
In order : 5  28  63
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 24
 
Post order : 5  28  63  24
Pre order : 24  5  63  28
In order : 5  24  28  63
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 64
 
Post order : 5  28  64  63  24
Pre order : 24  5  63  28  64
In order : 5  24  28  63  64
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 19
 
Post order : 5  19  28  64  63  24
Pre order : 24  19  5  63  28  64
In order : 5  19  24  28  63  64
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 1
Enter integer element to insert: 94
 
Post order : 5  19  28  94  64  63  24
Pre order : 24  19  5  63  28  64  94
In order : 5  19  24  28  63  64  94
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 2
Enter integer element to search: 24
Element 24 found in the Tree
 
Post order : 5  19  28  94  64  63  24
Pre order : 24  19  5  63  28  64  94
In order : 5  19  24  28  63  64  94
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 2
Enter integer element to search: 25
Element 25 not found in the Tree
 
Post order : 5  19  28  94  64  63  24
Pre order : 24  19  5  63  28  64  94
In order : 5  19  24  28  63  64  94
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 3
Nodes = 7
 
Post order : 5  19  28  94  64  63  24
Pre order : 24  19  5  63  28  64  94
In order : 5  19  24  28  63  64  94
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 4
Tree is not Empty
 
Post order : 5  19  28  94  64  63  24
Pre order : 24  19  5  63  28  64  94
In order : 5  19  24  28  63  64  94
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 5
 
RandomizedBinarySearchTree Cleared
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
y
 
Randomized Binary SearchTree Operations
1. Insert
2. Search
3. Count Nodes
4. Check Empty
5. Clear
Enter your choice: 4
Tree is Empty
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
n
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.