Self Balancing Binary Search Tree in C++

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

$ 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
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.