C++ Program to Implement Self Balancing Binary Search Tree

«
»
This C++ Program demonstrates the implementation of Self Balancing Binary Search Tree.

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

advertisement
$ g++ self_bst.cpp
$ a.out
 
SelfBalancingBinarySearchTree Test
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 5
 
Post order : 5
Pre order : 5
In order : 5
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 8
 
Post order : 8  5
Pre order : 5  8
In order : 5  8
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 24
 
Post order : 5  24  8
Pre order : 8  5  24
In order : 5  8  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 6
 
Post order : 6  5  24  8
Pre order : 8  5  6  24
In order : 5  6  8  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 10
 
Post order : 6  5  10  24  8
Pre order : 8  5  6  24  10
In order : 5  6  8  10  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 2
Nodes = 5
 
Post order : 6  5  10  24  8
Pre order : 8  5  6  24  10
In order : 5  6  8  10  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 3
Enter integer element to search: 6
6 found in the tree
 
Post order : 6  5  10  24  8
Pre order : 8  5  6  24  10
In order : 5  6  8  10  24
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 5
 
Tree cleared
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n): y
 
SelfBalancingBinarySearchTree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 4
Empty status = 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
advertisement
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