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.

```
/*
```

 *  C++ Program to Implement Randomized Binary Search Tree

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstring>
```
```
#include <algorithm>
```
```
#include <cmath>
```
```
#include <vector>
```
```
#include <cstdlib>   
```
```
#define MAX_VALUE 65536
```
```
using namespace std;
```
```
/*
```
```
 * Class RBSTNode 
```
```
 */
```
```
class RBSTNode
```
```
{  
```
```
    public: 
```
```
        RBSTNode *left, *right;
```
```
        int priority, element;  
```
```
        /* Constructor */
```
```
        RBSTNode()
```
```
        {
```
```
            this->element = 0;
```
```
            this->left = this;
```
```
            this->right = this;
```

            this->priority = MAX_VALUE;

```
        }    
```
```
         /* Constructor */    
```
```
        RBSTNode(int ele)
```
```
        {
```

            RBSTNode(ele, NULL, NULL);

```
        } 
```
```
        /* Constructor */
```

        RBSTNode(int ele, RBSTNode *left, RBSTNode *right)

```
        {
```
```
            this->element = ele;
```
```
            this->left = left;
```
```
            this->right = right;
```

            this->priority = rand() % 100 + 1;

```
        }    
```
```
};
```
```
 
```
```
/*
```
```
 * Class RandomizedBinarySearchTree 
```
```
 */
```
```
class RandomizedBinarySearchTree
```
```
{
```
```
    private: 
```
```
        RBSTNode *root;
```
```
        RBSTNode *nil;
```
```
    public:
```
```
        /* Constructor */
```
```
         RandomizedBinarySearchTree()
```
```
         {
```
```
             root = nil;
```
```
         }
```

         /* Function to check if tree is empty */

```
         bool isEmpty()
```
```
         {
```
```
             return root == nil;
```
```
         }
```

         /* Make the tree logically empty **/

```
         void makeEmpty()
```
```
         {
```
```
             root = nil;
```
```
         }
```
```
 
```

         /* Functions to insert data **/

```
         void insert(int X)
```
```
         {
```
```
             root = insert(X, root);
```
```
         }
```

         RBSTNode *insert(int X, RBSTNode *T)\

```
         {
```
```
             if (T == nil)
```

                 return new RBSTNode(X, nil, nil);

```
             else if (X < T->element)
```
```
             {
```

                 T->left = insert(X, T->left);

                 if (T->left->priority < T->priority)

```
                 {
```

                      RBSTNode *L = T->left;

                      T->left = L->right;

```
                      L->right = T;
```
```
                      return L;
```
```
                  }    
```
```
             }
```
```
             else if (X > T->element)
```
```
             {
```

                 T->right = insert(X, T->right);

                 if (T->right->priority < T->priority)

```
                 {
```

                     RBSTNode *R = T->right;

                     T->right = R->left;

```
                     R->left = T;
```
```
                     return R;
```
```
                 }
```
```
             }
```
```
             return T;
```
```
         }
```
```
         /*
```

          * Functions to count number of nodes

```
          */
```
```
         int countNodes()
```
```
         {
```
```
             return countNodes(root);
```
```
         }
```
```
 
```
```
         int countNodes(RBSTNode *r)
```
```
         {
```
```
             if (r == nil)
```
```
                 return 0;
```
```
             else
```
```
             {
```
```
                 int l = 1;
```

                 l += countNodes(r->left);

                 l += countNodes(r->right);

```
                 return l;
```
```
             }
```
```
         }
```
```
         /*
```

          * Functions to search for an element

```
          */
```
```
         bool search(int val)
```
```
         {
```
```
             return search(root, val);
```
```
         }
```

         bool search(RBSTNode *r, int val)

```
         {
```
```
             bool found = false;
```

             while ((r != nil) && !found)

```
             {
```
```
                 int rval = r->element;
```
```
                 if (val < rval)
```
```
                     r = r->left;
```
```
                 else if (val > rval)
```
```
                     r = r->right;
```
```
                 else
```
```
                 {
```
```
                     found = true;
```
```
                     break;
```
```
                 }
```

                 found = search(r, val);

```
             }
```
```
             return found;
```
```
         }
```
```
 
```
```
         /*
```

          * Function for inorder traversal

```
          */
```
```
         void inorder()
```
```
         {
```
```
             inorder(root);
```
```
         }
```
```
 
```
```
         void inorder(RBSTNode *r)
```
```
         {
```
```
             if (r != nil)
```
```
             {
```
```
                 inorder(r->left);
```

                 cout<<r->element <<"  ";

```
                 inorder(r->right);
```
```
             }
```
```
         }
```
```
         /*
```

          * Function for preorder traversal

```
          */
```
```
         void preorder()
```
```
         {
```
```
             preorder(root);
```
```
         }
```
```
         void preorder(RBSTNode *r)
```
```
         {
```
```
             if (r != nil)
```
```
             {
```

                 cout<<r->element <<"  ";

                 preorder(r->left);

```
                 preorder(r->right);
```
```
             }
```
```
         }
```
```
 
```
```
         /*
```

          * Function for postorder traversal

```
          */
```
```
         void postorder()
```
```
         {
```
```
             postorder(root);
```
```
         }
```
```
         void postorder(RBSTNode *r)
```
```
         {
```
```
             if (r != nil)
```
```
             {
```

                 postorder(r->left);

```
                 postorder(r->right);
```

                 cout<<r->element <<"  ";

```
             }
```
```
         }         
```
```
};     
```
```
 
```
```
/*
```
```
 * Main Contains Menu 
```
```
 */
```
```
 
```
```
int main()
```
```
{            
```
```
    RandomizedBinarySearchTree rbst; 
```

    cout<<"Randomized Binary SearchTree Test\n";

```
    char ch;
```
```
    int choice, item;
```
```
    /*
```
```
     * Perform tree operations  
```
```
     */
```
```
    do    
```
```
    {
```

        cout<<"\nRandomized Binary SearchTree Operations\n";

```
        cout<<"1. Insert "<<endl;
```
```
        cout<<"2. Search "<<endl;
```
```
        cout<<"3. Count Nodes "<<endl;
```
```
        cout<<"4. Check Empty"<<endl;
```
```
        cout<<"5. Clear"<<endl;
```
```
        cout<<"Enter your choice: ";
```
```
        cin>>choice;            
```
```
        switch (choice)
```
```
        {
```
```
        case 1: 
```

            cout<<"Enter integer element to insert: ";

```
            cin>>item;
```

            rbst.insert(item);

            break;

```
        case 2: 
```

            cout<<"Enter integer element to search: ";

```
            cin>>item;
```
```
            if (rbst.search(item))
```

                cout<<"Element "<<item<<" found in the Tree"<<endl;

```
            else
```

                cout<<"Element "<<item<<" not found in the Tree"<<endl;

            break;

```
        case 3: 
```

            cout<<"Nodes = "<<rbst.countNodes()<<endl;

```
            break;     
```
```
        case 4:
```
```
            if (rbst.isEmpty()) 
```

                cout<<"Tree is Empty"<<endl;

```
            else
```

                cout<<"Tree is not Empty"<<endl;

```
            break;
```
```
        case 5: 
```

            cout<<"\nRandomizedBinarySearchTree Cleared"<<endl;

```
            rbst.makeEmpty();
```
```
            break;            
```
```
        default: 
```
```
            cout<<"Wrong Entry \n ";
```
```
            break;   
```
```
        }
```
```
 
```
```
        /**  Display tree  **/ 
```
```
        cout<<"\nPost order : ";
```
```
        rbst.postorder();
```
```
        cout<<"\nPre order : ";
```
```
        rbst.preorder();    
```
```
        cout<<"\nIn order : ";
```
```
        rbst.inorder();
```

        cout<<"\nDo you want to continue (Type y or n) \n";

```
        cin>>ch;                  
```
```
    } 
```

    while (ch == 'Y'|| ch == 'y');

```
    return 0;
```
```
}
```

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

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

« Prev - C++ Program to Implement Binary Search Tree

» Next - Self Balancing Binary Search Tree in C++

Related Posts:

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

Recommended Articles: