C++ Programming Code Examples

C++ > Computer Graphics Code Examples

C++ Program to Implement Randomized Binary Search Tree

C++ Program to Implement Randomized Binary Search Tree

This C++ Program demonstrates the implementation of 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;

    }