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

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

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

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn