C++ Program to Implement Weight Balanced Tree

«
»
This C++ Program demonstrates the implementation of Weight Balanced Tree.

Here is source code of the C++ Program to demonstrate the implementation of Weight Balanced Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  *  C++ Program to Implement Weight Balanced Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #define MAX_VALUE 65536
  7. using namespace std;
  8. /* Class WBTNode */
  9. class WBTNode
  10. {
  11.     public:
  12.         WBTNode *left;
  13.         WBTNode *right;
  14.         int weight, element;     
  15.  
  16.         /* Constructor */
  17.          WBTNode(int theElement, int wt, WBTNode *lt, WBTNode *rt)
  18.          {
  19.              element = theElement;
  20.              left = lt;
  21.              right = rt;
  22.              weight = wt;
  23.          }
  24.         /* Constructor */    
  25.         WBTNode(int theElement, int wt)
  26.         {
  27.             WBTNode(theElement, wt, NULL, NULL);
  28.         }
  29.  
  30. };
  31. WBTNode *nullNode;
  32. /* Class WeightBalancedTree */
  33. class WeightBalancedTree
  34. {
  35.     private: 
  36.         WBTNode *root;
  37.     public:     
  38.          /* Constructor */
  39.         WeightBalancedTree()
  40.         {
  41.             root = nullNode;
  42.         }
  43.  
  44.         /* Function to check if tree is empty */
  45.         bool isEmpty()
  46.         {
  47.             return root == nullNode;
  48.         }
  49.  
  50.         /* Make the tree logically empty */
  51.         void makeEmpty()
  52.         {
  53.             root = nullNode;
  54.         }
  55.  
  56.         /* Functions to insert data */
  57.         void insert(int x, int wt)
  58.         {
  59.             root = insert(x, wt, root);
  60.         }
  61.         WBTNode *insert(int x, int wt, WBTNode *t)
  62.         {
  63.             if (t == nullNode)
  64.                 t = new WBTNode(x, wt, nullNode, nullNode);
  65.             else if (x < t->element)
  66.             {
  67.                 t->left = insert (x, wt, t->left);
  68.                 if (t->left->weight < t->weight)
  69.                     t = rotateWithLeftChild (t);
  70.             }
  71.             else if (x > t->element)
  72.             {
  73.                 t->right = insert (x, wt, t->right);
  74.                 if (t->right->weight < t->weight)
  75.                     t = rotateWithRightChild (t);
  76.             }
  77.             return t;
  78.         }
  79.  
  80.         /* Functions to delete data */
  81.         void remove(int x)
  82.         {
  83.             if (isEmpty())
  84.                 cout<<"Tree Empty"<<endl;
  85.             else if (search(x) == false)
  86.                 cout<<x <<" is not present"<<endl;
  87.             else
  88.             {             
  89.                 root = remove (x, root);
  90.                 cout<<x <<" deleted from the tree"<<endl;
  91.             }
  92.         }     
  93.  
  94.         WBTNode *remove(int x, WBTNode *t)
  95.         {
  96.             if (t != nullNode)
  97.             {
  98.                 if (x < t->element)
  99.                     t->left = remove (x, t->left);
  100.                 else if (x > t->element)
  101.                     t->right = remove (x, t->right);
  102.                 else
  103.                 {
  104.                     if (t->left->weight == 0)
  105.                         t->left->weight = MAX_VALUE;
  106.                     if (t->right->weight == 0)
  107.                         t->right->weight = MAX_VALUE;
  108.                     if (t->left->weight < t->right->weight)
  109.                     {
  110.                         t = rotateWithLeftChild(t);
  111.                     }
  112.                     else
  113.                     {
  114.                         t = rotateWithRightChild(t);
  115.                     }
  116.                     if (t != nullNode)     
  117.                         t = remove( x, t );
  118.                     else
  119.                         t->left = nullNode;    
  120.                 }
  121.             }
  122.             return t;
  123.         }     
  124.  
  125.         /* Rotate tree node with left child  */     
  126.         WBTNode *rotateWithLeftChild (WBTNode *k2)
  127.         {
  128.             WBTNode *k1 = k2->left;
  129.             k2->left = k1->right;
  130.             k1->right = k2;
  131.             return k1;
  132.         }
  133.  
  134.         /* Rotate tree node with right child */
  135.         WBTNode *rotateWithRightChild (WBTNode *k1)
  136.         {
  137.             WBTNode *k2 = k1->right;
  138.             k1->right = k2->left;
  139.             k2->left = k1;
  140.             return k2;
  141.         }
  142.  
  143.         /* Functions to count number of nodes */
  144.         int countNodes()
  145.         {
  146.             return countNodes(root);
  147.         }
  148.  
  149.         int countNodes(WBTNode *r)
  150.         {
  151.             if (r == nullNode)
  152.                 return 0;
  153.             else
  154.             {
  155.                 int l = 1;
  156.                 l += countNodes(r->left);
  157.                 l += countNodes(r->right);
  158.                 return l;
  159.             }
  160.         }
  161.  
  162.         /* Functions to search for an element */
  163.         bool search(int val)
  164.         {
  165.             return search(root, val);
  166.         }
  167.  
  168.         bool search(WBTNode *r, int val)
  169.         {
  170.             bool found = false;
  171.             while ((r != nullNode) && !found)
  172.             {
  173.                 int rval = r->element;
  174.                 if (val < rval)
  175.                     r = r->left;
  176.                 else if (val > rval)
  177.                     r = r->right;
  178.                 else
  179.                 {
  180.                     found = true;
  181.                     break;
  182.                 }
  183.                 found = search(r, val);
  184.             }
  185.             return found;
  186.         }
  187.  
  188.         /* Function for inorder traversal */
  189.         void inorder()
  190.         {
  191.             inorder(root);
  192.         }
  193.  
  194.         void inorder(WBTNode *r)
  195.         {
  196.             if (r != nullNode)
  197.             {
  198.                 inorder(r->left);
  199.                 cout<<r->element<<"   ";
  200.                 inorder(r->right);
  201.             }
  202.         }
  203.  
  204.         /* Function for preorder traversal */
  205.         void preorder()
  206.         {
  207.             preorder(root);
  208.         }
  209.         void preorder(WBTNode *r)
  210.         {
  211.             if (r != nullNode)
  212.             {
  213.                 cout<<r->element<<"   ";
  214.                 preorder(r->left);             
  215.                 preorder(r->right);
  216.             }
  217.         }
  218.  
  219.         /* Function for postorder traversal */
  220.         void postorder()
  221.         {
  222.             postorder(root);
  223.         }
  224.  
  225.         void postorder(WBTNode *r)
  226.         {
  227.             if (r != nullNode)
  228.             {
  229.                 postorder(r->left);             
  230.                 postorder(r->right);
  231.                 cout<<r->element<<"   ";
  232.             }
  233.         }         
  234. };
  235.  
  236.  
  237. /* Main Contains Menu */
  238.  
  239. int main()
  240. {
  241.     nullNode = new WBTNode(0, MAX_VALUE);
  242.     nullNode->left = nullNode->right = nullNode;
  243.     WeightBalancedTree wbt; 
  244.     cout<<"Weight Balanced Tree Test\n";          
  245.     int choice, val, wt;
  246.     char ch;
  247.     /*  Perform tree operations  */
  248.     do    
  249.     {
  250.         cout<<"\nWeight Balanced Tree Operations\n";
  251.         cout<<"1. Insert "<<endl;
  252.         cout<<"2. Delete"<<endl;
  253.         cout<<"3. Search"<<endl;
  254.         cout<<"4. Count nodes"<<endl;
  255.         cout<<"5. Check empty"<<endl;
  256.         cout<<"6. Clear"<<endl;
  257.         cout<<"Enter Your Choice: ";
  258.         cin>>choice;
  259.         switch (choice)
  260.         {
  261.         case 1 : 
  262.             cout<<"Enter integer element to insert: "; 
  263.             cin>>val;
  264.             cout<<"Enter weight of the element in int: ";
  265.             cin>>wt;
  266.             wbt.insert(val, wt);                     
  267.             break;                          
  268.         case 2 : 
  269.             cout<<"Enter integer element to delete: ";
  270.             cin>>val;
  271.             wbt.remove(val);
  272.             break;                         
  273.         case 3 : 
  274.             cout<<"Enter integer element to search: ";
  275.             cin>>val;
  276.             if (wbt.search(val) == true)
  277.                 cout<<"Element "<<val<<" found in the tree"<<endl;
  278.             else
  279.                 cout<<"Element "<<val<<" not found in the tree"<<endl;
  280.             break;                                         
  281.         case 4 : 
  282.             cout<<"Nodes = "<< wbt.countNodes();
  283.             break;     
  284.         case 5 : 
  285.             if (wbt.isEmpty() == true)
  286.                 cout<<"Tree is empty"<<endl;
  287.             else
  288.                 cout<<"Tree is non-empty"<<endl;
  289.             break;
  290.         case 6 : 
  291.             cout<<"\nTree Cleared";
  292.             wbt.makeEmpty();
  293.             break;            
  294.         default : 
  295.             cout<<"Wrong Entry \n ";
  296.             break;   
  297.         }
  298.         /*  Display tree  */ 
  299.         cout<<"\nPost order : ";
  300.         wbt.postorder();
  301.         cout<<"\nPre order : ";
  302.         wbt.preorder();    
  303.         cout<<"\nIn order : "; 
  304.         wbt.inorder();
  305.         cout<<"\nDo you want to continue (Type y or n) \n";
  306.         cin>>ch;                        
  307.     } 
  308.     while (ch == 'Y'|| ch == 'y');               
  309.     return 0;
  310. }

$ g++ weight_balanced_tree.cpp
$ a.out
Weight Balanced Tree Test
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 1
Enter integer element to insert: 24
Enter weight of the element in int: 28
 
Post order : 24
Pre order : 24
In order : 24
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 1
Enter integer element to insert: 5
Enter weight of the element in int: 6
 
Post order : 24   5
Pre order : 5   24
In order : 5   24
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 1
Enter integer element to insert: 63
Enter weight of the element in int: 94
 
Post order : 63   24   5
Pre order : 5   24   63
In order : 5   24   63
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 1
Enter integer element to insert: 14
Enter weight of the element in int: 6
 
Post order : 63   24   14   5
Pre order : 5   14   24   63
In order : 5   14   24   63
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 1
Enter integer element to insert: 1
Enter weight of the element in int: 17
 
Post order : 1   63   24   14   5
Pre order : 5   1   14   24   63
In order : 1   5   14   24   63
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 1
Enter integer element to insert: 70
Enter weight of the element in int: 91
 
Post order : 1   63   70   24   14   5
Pre order : 5   1   14   24   70   63
In order : 1   5   14   24   63   70
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 2
Enter integer element to delete: 24
24 deleted from the tree
 
Post order : 1   63   70   14   5
Pre order : 5   1   14   70   63
In order : 1   5   14   63   70
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 3
Enter integer element to search: 1
Element 1 found in the tree
 
Post order : 1   63   70   14   5
Pre order : 5   1   14   70   63
In order : 1   5   14   63   70
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 4
Nodes = 5
Post order : 1   63   70   14   5
Pre order : 5   1   14   70   63
In order : 1   5   14   63   70
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 6
 
Tree Cleared
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
y
 
Weight Balanced Tree Operations
1. Insert
2. Delete
3. Search
4. Count nodes
5. Check empty
6. Clear
Enter Your Choice: 5
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.