Code:
#include iostream
#include cstdlib
using namespace std;
typedef struct ctreenode *ctree;
/*
* Tree Node Declaration
*/
struct ctreenode
{
int key, fix;
ctree left, right;
};
ctree nullnode, root;
/*
* Treap Class Declaration
*/
class CTree
{
public:
void initialize();
void sigrotl(ctree &);
void sigrotr(ctree &);
void insert(ctree &, int);
void remove(ctree &, int);
void display(ctree, int);
void inorder(ctree);
bool find(ctree, int);
CTree()
{}
};
/*
* Initializing node
*/
void CTree::initialize()
{
nullnode = new ctreenode;
nullnode->left = nullnode->right = nullnode;
root = nullnode;
}
/*
* Left Rotation
*/
void CTree::sigrotl(ctree& k1)
{
ctree k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1 = k2;
}
/*
* Right Rotation
*/
void CTree::sigrotr(ctree& k1)
{
ctree k2;
k2 = k1->left;
k1->left = k2->right;
k2->right = k1;
k1 = k2;
}
/*
* Insert Element into Treap
*/
void CTree::insert(ctree& t, int x)
{
if (t == nullnode)
{
t = new ctreenode;
t->left = t->right = nullnode;
t->key = x;
t->fix = rand();
}
else
{
if (t->key == x)
{
return;
}
else
{
if (x < t->key)
{
insert(t->left, x);
if (t->left->fix > t->fix)
sigrotr(t);
}
else
{
insert(t->right, x);
if (t->right->fix > t->fix)
sigrotl(t);
}
}
}
}
/*
* Remove Element from Treap
*/
void CTree::remove(ctree& t, int x)
{
if (t == nullnode)
return;
if (x > t->key)
remove(t->right, x);
else if (x < t->key)
remove(t->left, x);
else
{
if (t->left == nullnode && t->right == nullnode)
{
delete t;
t = nullnode;
}
else if (t->left == nullnode)
{
ctree tmp = t;
t = t->right;
delete tmp;
}
else if (t->right == nullnode)
{
ctree tmp = t;
t = t->left;
delete tmp;
}
else
{
if (t->left->fix < t->right->fix)
{
sigrotl(t);
remove(t->left, x);
}
else
{
sigrotr(t);
remove(t->right, x);
}
}
}
}
/*
* Search an element in Treap
*/
bool CTree::find(ctree t,int x)
{
if (t == nullnode)
return false;
if (t->key == x)
return true;
else
{
if (x < t->key)
return find(t->left, x);
else
return find(t->right, x);
}
}
/*
* Display elements of Treap
*/
void CTree::display(ctree ptr, int level)
{
int i;
if (ptr == nullnode)
return;
if (ptr != NULL)
{
display(ptr->right, level + 1);
cout<
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0; i < level; i++)
cout<<" ";
}
cout<
display(ptr->left, level + 1);
}
}
/*
* Inorder Travesal of Treap
*/
void CTree::inorder(ctree ptr)
{
if (ptr == nullnode)
return;
if (ptr != NULL)
{
inorder(ptr->left);
cout<
inorder(ptr->right);
}
}
/*
* Main Contains Menu
*/
int main()
{
CTree ct;
int choice, num;
bool flag = false;
ct.initialize();
while (1)
{
cout<
cout<
cout<
cout<<"1.Insert Element "<
cout<<"2.Delete Element "<
cout<<"3.Inorder Traversal"<
cout<<"4.Display in Order"<
cout<<"5.Quit"<
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the number to be inserted : ";
cin>>num;
ct.insert(root, num);
break;
case 2:
if (root == nullnode)
{
cout<<"Tree is empty, nothing to delete"<
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
if (ct.find(root, num))
flag = true;
else
cout<<"Element not found"<
ct.remove(root, num);
if (!ct.find(root, num) && flag)
cout<<"Element Deleted"<
break;
case 3:
if (root == nullnode)
{
cout<<"Tree is empty, insert element first"<
continue;
}
cout<<"Inorder Traversal:"<
ct.inorder(root);
cout<
break;
case 4:
if (root == nullnode)
{
cout<<"Tree is empty"<
continue;
}
cout<<"Display Treap:"<
ct.display(root, 1);
cout<
break;
case 5:
exit(1);
break;
default:
cout<<"Wrong choice"<
}
}
}
Output:
----------------------------
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
More C++ Programs:
