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. }

advertisement
$ 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn