C++ Program to Implement Treap

This C++ Program demonstrates the implementation of Treap.

Here is source code of the C++ Program to demonstrate the implementation of Treap. 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 Treap
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. using namespace std;
  7.  
  8. typedef struct ctreenode *ctree;
  9. /*
  10.  * Tree Node Declaration
  11.  */
  12. struct ctreenode
  13. {
  14.     int key, fix;
  15.     ctree left, right;
  16. };
  17. ctree nullnode, root;
  18.  
  19. /*
  20.  * Treap Class Declaration
  21.  */
  22. class CTree
  23. {
  24.     public:
  25.         void initialize();
  26.         void sigrotl(ctree &);
  27.         void sigrotr(ctree &);
  28.         void insert(ctree &, int);
  29.         void remove(ctree &, int);
  30.         void display(ctree, int);
  31.         void inorder(ctree);    
  32.         bool find(ctree, int);	
  33.         CTree()
  34.         {}
  35. };
  36. /*
  37.  * Initializing node 
  38.  */
  39. void CTree::initialize()
  40. {
  41.     nullnode = new ctreenode;
  42.     nullnode->left = nullnode->right = nullnode;
  43.     root = nullnode;
  44. }
  45.  
  46. /*
  47.  * Left Rotation
  48.  */
  49. void CTree::sigrotl(ctree& k1)
  50. {
  51.     ctree k2;
  52.     k2 = k1->right;
  53.     k1->right = k2->left;
  54.     k2->left = k1;
  55.     k1 = k2;
  56. }
  57.  
  58. /*
  59.  * Right Rotation
  60.  */
  61. void CTree::sigrotr(ctree& k1)
  62. {
  63.     ctree k2;
  64.     k2 = k1->left;
  65.     k1->left = k2->right;
  66.     k2->right = k1;
  67.     k1 = k2;
  68. }
  69. /*
  70.  * Insert Element into Treap
  71.  */
  72. void CTree::insert(ctree& t, int x)
  73. {
  74.     if (t == nullnode)
  75.     {
  76.         t = new ctreenode;
  77.         t->left = t->right = nullnode;
  78.         t->key = x;
  79.         t->fix = rand();
  80.     }
  81.     else
  82.     {
  83.         if (t->key == x)
  84.         {
  85.             return;
  86. 	}
  87.         else
  88.         {
  89.             if (x < t->key)
  90.             {
  91.                 insert(t->left, x);
  92.                 if (t->left->fix > t->fix)
  93.                     sigrotr(t);
  94.             }
  95.             else
  96.             {
  97.                 insert(t->right, x);
  98.                 if (t->right->fix > t->fix)
  99.                 sigrotl(t);
  100.             }
  101.         }   
  102.     }
  103. }
  104.  
  105. /*
  106.  * Remove Element from Treap
  107.  */
  108. void CTree::remove(ctree& t, int x)
  109. {
  110.     if (t == nullnode)
  111.         return;
  112.     if (x > t->key)
  113.         remove(t->right, x);
  114.     else if (x < t->key)
  115.         remove(t->left, x);
  116.     else
  117.     {
  118.         if (t->left == nullnode && t->right == nullnode)
  119.         {
  120.             delete t;
  121.             t = nullnode;
  122.         }
  123.         else if (t->left == nullnode)
  124.         {
  125.             ctree tmp = t;
  126.             t = t->right;
  127.             delete tmp;
  128.         }
  129.         else if (t->right == nullnode)
  130.         {
  131.             ctree tmp = t;
  132.             t = t->left;
  133.             delete tmp;
  134.         }
  135.         else
  136.         {
  137.             if (t->left->fix < t->right->fix)
  138.             {
  139.                 sigrotl(t);
  140.                 remove(t->left, x);
  141.             }
  142.             else
  143.             {
  144.                 sigrotr(t);
  145.                 remove(t->right, x);
  146.             }
  147.         }
  148.     }
  149. }
  150. /*
  151.  * Search an element in Treap
  152.  */
  153. bool CTree::find(ctree t,int x)
  154. {
  155.     if (t == nullnode)
  156.         return false;
  157.     if (t->key == x)
  158.         return true;
  159.     else
  160.     {
  161.         if (x < t->key)
  162.             return find(t->left, x);
  163.         else
  164.             return find(t->right, x);
  165.     }
  166. }
  167. /*
  168.  * Display elements of Treap
  169.  */
  170. void CTree::display(ctree ptr, int level)
  171. {
  172.     int i;
  173.     if (ptr == nullnode)
  174.         return;
  175.     if (ptr != NULL)
  176.     {
  177.         display(ptr->right, level + 1);
  178.         cout<<endl;
  179.         if (ptr == root)
  180.        	    cout<<"Root->:  ";
  181.         else
  182.         {
  183.             for (i = 0; i < level; i++)
  184.                 cout<<"       ";
  185.         }
  186.         cout<<ptr->key; 
  187.         display(ptr->left, level + 1);
  188.     }
  189. }
  190. /*
  191.  * Inorder Travesal of Treap
  192.  */
  193. void CTree::inorder(ctree ptr)
  194. {
  195.     if (ptr == nullnode)
  196.         return;
  197.     if (ptr != NULL)
  198.     {
  199.         inorder(ptr->left);
  200.         cout<<ptr->key<<"  ";
  201.         inorder(ptr->right);
  202.     }
  203. }
  204. /*
  205.  * Main Contains Menu
  206.  */
  207. int main()
  208. {
  209.     CTree ct;
  210.     int choice, num;
  211.     bool flag = false;
  212.     ct.initialize();
  213.     while (1)
  214.     {
  215.         cout<<endl<<"----------------------------"<<endl;
  216.         cout<<endl<<"Operations on Treap"<<endl;
  217.         cout<<endl<<"----------------------------"<<endl;
  218.         cout<<"1.Insert Element "<<endl;
  219.         cout<<"2.Delete Element "<<endl;
  220.         cout<<"3.Inorder Traversal"<<endl;
  221.         cout<<"4.Display in Order"<<endl;
  222.         cout<<"5.Quit"<<endl;
  223.         cout<<"Enter your choice : ";
  224.         cin>>choice;
  225.         switch(choice)
  226.         {
  227.         case 1:
  228.             cout<<"Enter the number to be inserted : ";
  229.             cin>>num;
  230.             ct.insert(root, num);
  231.             break;
  232.         case 2:
  233.             if (root == nullnode)
  234.             {
  235.                 cout<<"Tree is empty, nothing to delete"<<endl;
  236.                 continue;
  237. 	    }
  238.             cout<<"Enter the number to be deleted : ";
  239.             cin>>num;
  240.             if (ct.find(root, num))
  241.                 flag = true;
  242.             else
  243.                 cout<<"Element not found"<<endl;
  244.             ct.remove(root, num);
  245.             if (!ct.find(root, num) && flag)
  246.                 cout<<"Element Deleted"<<endl;
  247.             break;
  248.         case 3:
  249.             if (root == nullnode)
  250.             {
  251.                 cout<<"Tree is empty, insert element first"<<endl;
  252.                 continue;
  253.             }
  254.             cout<<"Inorder Traversal:"<<endl;
  255.             ct.inorder(root);
  256.             cout<<endl;
  257.             break;  
  258.         case 4:
  259.             if (root == nullnode)
  260.             {
  261.                 cout<<"Tree is empty"<<endl;
  262.                 continue;
  263.             }
  264.             cout<<"Display Treap:"<<endl;
  265.             ct.display(root, 1);
  266.             cout<<endl; 
  267.             break;
  268.         case 5:
  269.             exit(1);
  270.             break;
  271.         default:
  272.             cout<<"Wrong choice"<<endl;
  273.         }
  274.     }
  275. }

$ g++ treap.cpp
$ a.out
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 1
Enter the number to be inserted : 1
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 1
Enter the number to be inserted : 2
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 1
Enter the number to be inserted : 4
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 1
Enter the number to be inserted : 3
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 1
Enter the number to be inserted : 5
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 3
Inorder Traversal:
1  2  3  4  5
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 4
Display Treap:
 
              5
                     4
Root->:  3
              2
                     1
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 2
Enter the number to be deleted : 3
Element Deleted
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 3
Inorder Traversal:
1  2  4  5
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 4
Display Treap:
 
Root->:  5
                     4
              2
                     1
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 2
Enter the number to be deleted : 5
Element Deleted
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 3
Inorder Traversal:
1  2  4
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 4
Display Treap:
 
              4
Root->:  2
              1
 
----------------------------
 
Operations on Treap
 
----------------------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Display in Order
5.Quit
Enter your choice : 5
 
------------------
(program exited with code: 1)
Press return to continue

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

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.