C++ Program to Implement Weight Balanced Tree

Here, You will know about “C++ Program to Implement Weight Balanced Tree“. Below, We will discuss how to do the task using this tutorial? Let’s move.

C++ Program to Implement Weight Balanced Tree

C++ Program to Implement Weight Balanced Tree

Source Code

/*
 *  C++ Program to Implement Weight Balanced Tree
 */
#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;
/* Class WBTNode */
class WBTNode
{
    public:
        WBTNode *left;
        WBTNode *right;
        int weight, element;     
 
        /* Constructor */
         WBTNode(int theElement, int wt, WBTNode *lt, WBTNode *rt)
         {
             element = theElement;
             left = lt;
             right = rt;
             weight = wt;
         }
        /* Constructor */    
        WBTNode(int theElement, int wt)
        {
            WBTNode(theElement, wt, NULL, NULL);
        }
 
};
WBTNode *nullNode;
/* Class WeightBalancedTree */
class WeightBalancedTree
{
    private: 
        WBTNode *root;
    public:     
         /* Constructor */
        WeightBalancedTree()
        {
            root = nullNode;
        }
 
        /* Function to check if tree is empty */
        bool isEmpty()
        {
            return root == nullNode;
        }
 
        /* Make the tree logically empty */
        void makeEmpty()
        {
            root = nullNode;
        }
 
        /* Functions to insert data */
        void insert(int x, int wt)
        {
            root = insert(x, wt, root);
        }
        WBTNode *insert(int x, int wt, WBTNode *t)
        {
            if (t == nullNode)
                t = new WBTNode(x, wt, nullNode, nullNode);
            else if (x < t->element)
            {
                t->left = insert (x, wt, t->left);
                if (t->left->weight < t->weight)
                    t = rotateWithLeftChild (t);
            }
            else if (x > t->element)
            {
                t->right = insert (x, wt, t->right);
                if (t->right->weight < t->weight)
                    t = rotateWithRightChild (t);
            }
            return t;
        }
 
        /* Functions to delete data */
        void remove(int x)
        {
            if (isEmpty())
                cout<<"Tree Empty"<<endl;
            else if (search(x) == false)
                cout<<x <<" is not present"<<endl;
            else
            {             
                root = remove (x, root);
                cout<<x <<" deleted from the tree"<<endl;
            }
        }     
 
        WBTNode *remove(int x, WBTNode *t)
        {
            if (t != nullNode)
            {
                if (x < t->element)
                    t->left = remove (x, t->left);
                else if (x > t->element)
                    t->right = remove (x, t->right);
                else
                {
                    if (t->left->weight == 0)
                        t->left->weight = MAX_VALUE;
                    if (t->right->weight == 0)
                        t->right->weight = MAX_VALUE;
                    if (t->left->weight < t->right->weight)
                    {
                        t = rotateWithLeftChild(t);
                    }
                    else
                    {
                        t = rotateWithRightChild(t);
                    }
                    if (t != nullNode)     
                        t = remove( x, t );
                    else
                        t->left = nullNode;    
                }
            }
            return t;
        }     
 
        /* Rotate tree node with left child  */     
        WBTNode *rotateWithLeftChild (WBTNode *k2)
        {
            WBTNode *k1 = k2->left;
            k2->left = k1->right;
            k1->right = k2;
            return k1;
        }
 
        /* Rotate tree node with right child */
        WBTNode *rotateWithRightChild (WBTNode *k1)
        {
            WBTNode *k2 = k1->right;
            k1->right = k2->left;
            k2->left = k1;
            return k2;
        }
 
        /* Functions to count number of nodes */
        int countNodes()
        {
            return countNodes(root);
        }
 
        int countNodes(WBTNode *r)
        {
            if (r == nullNode)
                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(WBTNode *r, int val)
        {
            bool found = false;
            while ((r != nullNode) && !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(WBTNode *r)
        {
            if (r != nullNode)
            {
                inorder(r->left);
                cout<<r->element<<"   ";
                inorder(r->right);
            }
        }
 
        /* Function for preorder traversal */
        void preorder()
        {
            preorder(root);
        }
        void preorder(WBTNode *r)
        {
            if (r != nullNode)
            {
                cout<<r->element<<"   ";
                preorder(r->left);             
                preorder(r->right);
            }
        }
 
        /* Function for postorder traversal */
        void postorder()
        {
            postorder(root);
        }
 
        void postorder(WBTNode *r)
        {
            if (r != nullNode)
            {
                postorder(r->left);             
                postorder(r->right);
                cout<<r->element<<"   ";
            }
        }         
};
 
 
/* Main Contains Menu */
 
int main()
{
    nullNode = new WBTNode(0, MAX_VALUE);
    nullNode->left = nullNode->right = nullNode;
    WeightBalancedTree wbt; 
    cout<<"Weight Balanced Tree Testn";          
    int choice, val, wt;
    char ch;
    /*  Perform tree operations  */
    do    
    {
        cout<<"nWeight Balanced Tree Operationsn";
        cout<<"1. Insert "<<endl;
        cout<<"2. Delete"<<endl;
        cout<<"3. Search"<<endl;
        cout<<"4. Count nodes"<<endl;
        cout<<"5. Check empty"<<endl;
        cout<<"6. Clear"<<endl;
        cout<<"Enter Your Choice: ";
        cin>>choice;
        switch (choice)
        {
        case 1 : 
            cout<<"Enter integer element to insert: "; 
            cin>>val;
            cout<<"Enter weight of the element in int: ";
            cin>>wt;
            wbt.insert(val, wt);                     
            break;                          
        case 2 : 
            cout<<"Enter integer element to delete: ";
            cin>>val;
            wbt.remove(val);
            break;                         
        case 3 : 
            cout<<"Enter integer element to search: ";
            cin>>val;
            if (wbt.search(val) == true)
                cout<<"Element "<<val<<" found in the tree"<<endl;
            else
                cout<<"Element "<<val<<" not found in the tree"<<endl;
            break;                                         
        case 4 : 
            cout<<"Nodes = "<< wbt.countNodes();
            break;     
        case 5 : 
            if (wbt.isEmpty() == true)
                cout<<"Tree is empty"<<endl;
            else
                cout<<"Tree is non-empty"<<endl;
            break;
        case 6 : 
            cout<<"nTree Cleared";
            wbt.makeEmpty();
            break;            
        default : 
            cout<<"Wrong Entry n ";
            break;   
        }
        /*  Display tree  */ 
        cout<<"nPost order : ";
        wbt.postorder();
        cout<<"nPre order : ";
        wbt.preorder();    
        cout<<"nIn order : "; 
        wbt.inorder();
        cout<<"nDo you want to continue (Type y or n) n";
        cin>>ch;                        
    } 
    while (ch == 'Y'|| ch == 'y');               
    return 0;
}

Final Words

We hope this article helps you to learn “C++ Program to Implement Weight Balanced Tree”. If you have any doubts about this topic then please let us know via the comment section. We will help you. Share this article with other C/C++ developers.

Share on:

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

Leave a Comment