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.

```
/*
```

 *  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 Test\n";

```
    int val;
```
```
    char ch;
```
```
    /*  Perform tree operations  */
```
```
    do
```
```
    {
```

        cout<<"\nSelfBalancingBinarySearchTree Operations\n";

```
        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;
```
```
        cout<<"Enter your 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
```

                cout<<val<<" not found"<<endl;

```
            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 cleared\n";
```
```
            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;
```
```
}
```

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

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

« Prev - C++ Program to Implement Randomized Binary Search Tree

» Next - C++ Program to Implement Cartesian Tree

Related Posts:

Apply for Computer Science Internship
Practice Computer Science MCQs
Check Programming Books
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: