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.

```
/*
```
```
 * C++ Program to Implement Treap
```
```
 */
```
```
#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<<endl;
```
```
        if (ptr == root)
```
```
       	    cout<<"Root->:  ";
```
```
        else
```
```
        {
```
```
            for (i = 0; i < level; i++)
```
```
                cout<<"       ";
```
```
        }
```
```
        cout<<ptr->key; 
```
```
        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<<ptr->key<<"  ";
```
```
        inorder(ptr->right);
```
```
    }
```
```
}
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    CTree ct;
```
```
    int choice, num;
```
```
    bool flag = false;
```
```
    ct.initialize();
```
```
    while (1)
```
```
    {
```

        cout<<endl<<"----------------------------"<<endl;

        cout<<endl<<"Operations on Treap"<<endl;

        cout<<endl<<"----------------------------"<<endl;

        cout<<"1.Insert Element "<<endl;

        cout<<"2.Delete Element "<<endl;

        cout<<"3.Inorder Traversal"<<endl;

        cout<<"4.Display in Order"<<endl;

```
        cout<<"5.Quit"<<endl;
```
```
        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"<<endl;

```
                continue;
```
```
	    }
```

            cout<<"Enter the number to be deleted : ";

```
            cin>>num;
```
```
            if (ct.find(root, num))
```
```
                flag = true;
```
```
            else
```

                cout<<"Element not found"<<endl;

```
            ct.remove(root, num);
```

            if (!ct.find(root, num) && flag)

                cout<<"Element Deleted"<<endl;

```
            break;
```
```
        case 3:
```
```
            if (root == nullnode)
```
```
            {
```

                cout<<"Tree is empty, insert element first"<<endl;

```
                continue;
```
```
            }
```

            cout<<"Inorder Traversal:"<<endl;

```
            ct.inorder(root);
```
```
            cout<<endl;
```
```
            break;  
```
```
        case 4:
```
```
            if (root == nullnode)
```
```
            {
```

                cout<<"Tree is empty"<<endl;

```
                continue;
```
```
            }
```

            cout<<"Display Treap:"<<endl;

```
            ct.display(root, 1);
```
```
            cout<<endl; 
```
```
            break;
```
```
        case 5:
```
```
            exit(1);
```
```
            break;
```
```
        default:
```
```
            cout<<"Wrong choice"<<endl;
```
```
        }
```
```
    }
```
```
}
```

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

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

« Prev - C++ Program to Implement Ternary Heap

» Next - C++ Program to Implement Weak Heap

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Programming Books
Apply for Computer Science Internship
Practice Computer Science MCQs
Check Data Structure Books

Recommended Articles: