C++ Program to Implement Randomized Binary Search Tree

You are currently viewing C++ Program to Implement Randomized Binary Search Tree

Hello developers! Do you want to clarify the topic “C++ Program to Implement Randomized Binary Search Tree“? If yes, this article helps you to clarify it clearly. Move on to the article directly.

C++ Program to Implement Randomized Binary Search Tree

Program Code

/*
 *  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 Testn";          
    char ch;
    int choice, item;
    /*
     * Perform tree operations  
     */
    do    
    {
        cout<<"nRandomized Binary SearchTree Operationsn";
        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;
}

Final Words

I hope this article helps you to clarify about “C++ Program to Implement Randomized Binary Search Tree“. If you have any doubts about this topic please let us know via the comment section. Do share this article with other developers to help them.

Ranjith

Hi, I'm Manoj a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Diksha. Here, I post about programming to help developers.

Leave a Reply