# C++ Program to Implement Self Balancing Binary Search Tree

In this tutorial, We will run the script of “C++ Program to Implement Self Balancing Binary Search Tree”. Below, We can see the possibilities to perform this task. Let’s go.

## Source Code

``````/*
*  C++ Program to Implement Self Balancing Binary Search Tree
*/
#include <iostream>
#include <cstdlib>
using namespace std;

/* Class SBBSTNode */

class SBBSTNode
{
public:
int height, data;
SBBSTNode *left, *right;
/* Constructor */
SBBSTNode()
{
left = NULL;
right = NULL;
data = 0;
height = 0;
}

/* Constructor */
SBBSTNode(int n)
{
left = NULL;
right = NULL;
data = n;
height = 0;
}
};

/*
* Class SelfBalancingBinarySearchTree
*/

class SelfBalancingBinarySearchTree
{
private:
SBBSTNode *root;
public:
/* Constructor */
SelfBalancingBinarySearchTree()
{
root = NULL;
}

/* Function to check if tree is empty */
bool isEmpty()
{
return root == NULL;
}

/* Make the tree logically empty */
void makeEmpty()
{
root = NULL;
}

/* Function to insert data */
void insert(int data)
{
root = insert(data, root);
}

/* Function to get height of node */
int height(SBBSTNode *t)
{
return t == NULL ? -1 : t->height;
}

/* Function to max of left/right node */
int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}

/* Function to insert data recursively */
SBBSTNode *insert(int x, SBBSTNode *t)
{
if (t == NULL)
t = new SBBSTNode(x);
else if (x < t->data)
{
t->left = insert(x, t->left);
if (height(t->left) - height(t->right) == 2)
if (x < t->left->data)
t = rotateWithLeftChild(t);
else
t = doubleWithLeftChild(t);
}
else if (x > t->data)
{
t->right = insert(x, t->right);
if (height(t->right) - height(t->left) == 2)
if (x > t->right->data)
t = rotateWithRightChild(t);
else
t = doubleWithRightChild(t);
}
t->height = max(height(t->left), height(t->right)) + 1;
return t;
}

/* Rotate binary tree node with left child */
SBBSTNode *rotateWithLeftChild(SBBSTNode* k2)
{
SBBSTNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), k2->height) + 1;
return k1;
}

/* Rotate binary tree node with right child */
SBBSTNode *rotateWithRightChild(SBBSTNode *k1)
{
SBBSTNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->right), k1->height) + 1;
return k2;
}

/*
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child
*/
SBBSTNode *doubleWithLeftChild(SBBSTNode *k3)
{
k3->left = rotateWithRightChild(k3->left);
return rotateWithLeftChild(k3);
}

/*
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child
*/
SBBSTNode *doubleWithRightChild(SBBSTNode *k1)
{
k1->right = rotateWithLeftChild(k1->right);
return rotateWithRightChild(k1);
}

/* Functions to count number of nodes */
int countNodes()
{
return countNodes(root);
}

int countNodes(SBBSTNode *r)
{
if (r == NULL)
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(SBBSTNode *r, int val)
{
bool found = false;
while ((r != NULL) && !found)
{
int rval = r->data;
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(SBBSTNode *r)
{
if (r != NULL)
{
inorder(r->left);
cout<<r->data<<"  ";
inorder(r->right);
}
}

/* Function for preorder traversal */
void preorder()
{
preorder(root);
}
void preorder(SBBSTNode *r)
{
if (r != NULL)
{
cout<<r->data<<"  ";
preorder(r->left);
preorder(r->right);
}
}

/* Function for postorder traversal */
void postorder()
{
postorder(root);
}
void postorder(SBBSTNode *r)
{
if (r != NULL)
{
postorder(r->left);
postorder(r->right);
cout<<r->data<<"  ";
}
}
};

int main()
{
SelfBalancingBinarySearchTree sbbst;
cout<<"SelfBalancingBinarySearchTree Testn";
int val;
char ch;
/*  Perform tree operations  */
do
{
cout<<"nSelfBalancingBinarySearchTree Operationsn";
cout<<"1. Insert "<<endl;
cout<<"2. Count nodes"<<endl;
cout<<"3. Search"<<endl;
cout<<"4. Check empty"<<endl;
cout<<"5. Make empty"<<endl;
int choice;
cin>>choice;
switch (choice)
{
case 1 :
cout<<"Enter integer element to insert: ";
cin>>val;
sbbst.insert(val);
break;
case 2 :
cout<<"Nodes = " <<sbbst.countNodes()<<endl;
break;
case 3:
cout<<"Enter integer element to search: ";
cin>>val;
if (sbbst.search(val))
cout<<val<<" found in the tree"<<endl;
else
break;
case 4 :
cout<<"Empty status = ";
if (sbbst.isEmpty())
cout<<"Tree is empty"<<endl;
else
cout<<"Tree is non - empty"<<endl;
break;
case 5 :
cout<<"nTree clearedn";
sbbst.makeEmpty();
break;
default :
cout<<"Wrong Entry n ";
break;
}

/*  Display tree*/
cout<<"nPost order : ";
sbbst.postorder();
cout<<"nPre order : ";
sbbst.preorder();
cout<<"nIn order : ";
sbbst.inorder();
cout<<"nDo you want to continue (Type y or n): ";
cin>>ch;
}
while (ch == 'Y'|| ch == 'y');
return 0;
}``````