C++ Program to Perform AVL Tree Operations

This is a C++ Program to print the kind of rotation that is performed when an element is inserted or deleted from tree. In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root’s place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.

Here is source code of the C++ Program to Print the Kind of Rotation the AVL Tree is Undergoing When you Add an Element or Delete an Element. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<cstdio>
```
```
#include<sstream>
```
```
#include<algorithm>
```
```
#define pow2(n) (1 << (n))
```
```
using namespace std;
```
```
/*
```
```
 * Node Declaration
```
```
 */
```
```
struct avl_node
```
```
{
```
```
        int data;
```
```
        struct avl_node *left;
```
```
        struct avl_node *right;
```
```
}*root;
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class avlTree
```
```
{
```
```
    public:
```
```
        int height(avl_node *);
```
```
        int diff(avl_node *);
```

        avl_node *rr_rotation(avl_node *);

        avl_node *ll_rotation(avl_node *);

        avl_node *lr_rotation(avl_node *);

        avl_node *rl_rotation(avl_node *);

```
        avl_node* balance(avl_node *);
```

        avl_node* insert(avl_node *, int);

```
        void display(avl_node *, int);
```
```
        void inorder(avl_node *);
```
```
        void preorder(avl_node *);
```
```
        void postorder(avl_node *);
```
```
        avlTree()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
};
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    int choice, item;
```
```
    avlTree avl;
```
```
    while (1)
```
```
    {
```

        cout << "\n---------------------" << endl;

        cout << "AVL Tree Implementation" << endl;

        cout << "\n---------------------" << endl;

        cout << "1.Insert Element into the tree" << endl;

        cout << "2.Display Balanced AVL Tree" << endl;

        cout << "3.InOrder traversal" << endl;

        cout << "4.PreOrder traversal" << endl;

        cout << "5.PostOrder traversal" << endl;

```
        cout << "6.Exit" << endl;
```
```
        cout << "Enter your Choice: ";
```
```
        cin >> choice;
```
```
        switch (choice)
```
```
        {
```
```
            case 1:
```

                cout << "Enter value to be inserted: ";

```
                cin >> item;
```

                root = avl.insert(root, item);

```
                break;
```
```
            case 2:
```
```
                if (root == NULL)
```
```
                {
```

                    cout << "Tree is Empty" << endl;

```
                    continue;
```
```
                }
```

                cout << "Balanced AVL Tree:" << endl;

```
                avl.display(root, 1);
```
```
                break;
```
```
            case 3:
```

                cout << "Inorder Traversal:" << endl;

```
                avl.inorder(root);
```
```
                cout << endl;
```
```
                break;
```
```
            case 4:
```

                cout << "Preorder Traversal:" << endl;

```
                avl.preorder(root);
```
```
                cout << endl;
```
```
                break;
```
```
            case 5:
```

                cout << "Postorder Traversal:" << endl;

```
                avl.postorder(root);
```
```
                cout << endl;
```
```
                break;
```
```
            case 6:
```
```
                exit(1);
```
```
                break;
```
```
            default:
```

                cout << "Wrong Choice" << endl;

```
        }
```
```
    }
```
```
    return 0;
```
```
}
```
```
/*
```
```
 * Height of AVL Tree
```
```
 */
```
```
int avlTree::height(avl_node *temp)
```
```
{
```
```
    int h = 0;
```
```
    if (temp != NULL)
```
```
    {
```

        int l_height = height(temp->left);

        int r_height = height(temp->right);

        int max_height = max(l_height, r_height);

```
        h = max_height + 1;
```
```
    }
```
```
    return h;
```
```
}
```
```
/*
```
```
 * Height Difference
```
```
 */
```
```
int avlTree::diff(avl_node *temp)
```
```
{
```
```
    int l_height = height(temp->left);
```
```
    int r_height = height(temp->right);
```
```
    int b_factor = l_height - r_height;
```
```
    return b_factor;
```
```
}
```
```
/*
```
```
 * Right- Right Rotation
```
```
 */
```

avl_node *avlTree::rr_rotation(avl_node *parent)

```
{
```
```
    avl_node *temp;
```
```
    temp = parent->right;
```
```
    parent->right = temp->left;
```
```
    temp->left = parent;
```
```
    cout<<"Right-Right Rotation";
```
```
    return temp;
```
```
}
```
```
/*
```
```
 * Left- Left Rotation
```
```
 */
```

avl_node *avlTree::ll_rotation(avl_node *parent)

```
{
```
```
    avl_node *temp;
```
```
    temp = parent->left;
```
```
    parent->left = temp->right;
```
```
    temp->right = parent;
```
```
    cout<<"Left-Left Rotation";
```
```
    return temp;
```
```
}
```
```
/*
```
```
 * Left - Right Rotation
```
```
 */
```

avl_node *avlTree::lr_rotation(avl_node *parent)

```
{
```
```
    avl_node *temp;
```
```
    temp = parent->left;
```
```
    parent->left = rr_rotation(temp);
```
```
    cout<<"Left-Right Rotation";
```
```
    return ll_rotation(parent);
```
```
}
```
```
/*
```
```
 * Right- Left Rotation
```
```
 */
```

avl_node *avlTree::rl_rotation(avl_node *parent)

```
{
```
```
    avl_node *temp;
```
```
    temp = parent->right;
```
```
    parent->right = ll_rotation(temp);
```
```
    cout<<"Right-Left Rotation";
```
```
    return rr_rotation(parent);
```
```
}
```
```
/*
```
```
 * Balancing AVL Tree
```
```
 */
```

avl_node *avlTree::balance(avl_node *temp)

```
{
```
```
    int bal_factor = diff(temp);
```
```
    if (bal_factor > 1)
```
```
    {
```
```
        if (diff(temp->left) > 0)
```
```
        {
```
```
            temp = ll_rotation(temp);
```
```
        }
```
```
        else
```
```
        {
```
```
            temp = lr_rotation(temp);
```
```
        }
```
```
    }
```
```
    else if (bal_factor < -1)
```
```
    {
```
```
        if (diff(temp->right) > 0)
```
```
        {
```
```
            temp = rl_rotation(temp);
```
```
        }
```
```
        else
```
```
        {
```
```
            temp = rr_rotation(temp);
```
```
        }
```
```
    }
```
```
    return temp;
```
```
}
```
```
/*
```
```
 * Insert Element into the tree
```
```
 */
```

avl_node *avlTree::insert(avl_node *root, int value)

```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        root = new avl_node;
```
```
        root->data = value;
```
```
        root->left = NULL;
```
```
        root->right = NULL;
```
```
        return root;
```
```
    }
```
```
    else if (value < root->data)
```
```
    {
```

        root->left = insert(root->left, value);

```
        root = balance(root);
```
```
    }
```
```
    else if (value >= root->data)
```
```
    {
```

        root->right = insert(root->right, value);

```
        root = balance(root);
```
```
    }
```
```
    return root;
```
```
}
```
```
/*
```
```
 * Display AVL Tree
```
```
 */
```

void avlTree::display(avl_node *ptr, int level)

```
{
```
```
    int i;
```
```
    if (ptr != NULL)
```
```
    {
```
```
        display(ptr->right, level + 1);
```
```
        printf("\n");
```
```
        if (ptr == root)
```
```
            cout << "Root -> ";
```

        for (i = 0; i < level && ptr != root; i++)

```
            cout << "        ";
```
```
        cout << ptr->data;
```
```
        display(ptr->left, level + 1);
```
```
    }
```
```
}
```
```
/*
```
```
 * Inorder Traversal of AVL Tree
```
```
 */
```
```
void avlTree::inorder(avl_node *tree)
```
```
{
```
```
    if (tree == NULL)
```
```
        return;
```
```
    inorder(tree->left);
```
```
    cout << tree->data << "  ";
```
```
    inorder(tree->right);
```
```
}
```
```
/*
```
```
 * Preorder Traversal of AVL Tree
```
```
 */
```
```
void avlTree::preorder(avl_node *tree)
```
```
{
```
```
    if (tree == NULL)
```
```
        return;
```
```
    cout << tree->data << "  ";
```
```
    preorder(tree->left);
```
```
    preorder(tree->right);
```
```
}/*
```
```
 * Postorder Traversal of AVL Tree
```
```
 */
```
```
void avlTree::postorder(avl_node *tree)
```
```
{
```
```
    if (tree == NULL)
```
```
        return;
```
```
    postorder(tree ->left);
```
```
    postorder(tree ->right);
```
```
    cout << tree->data << "  ";
```
```
}
```

Output:

$ g++ TypeOfRotation.cpp
$ a.out
 
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 23
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
23  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 45
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
 
                45
Root -> 23
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
23  45  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 4
Preorder Traversal:
23  45  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 5
Postorder Traversal:
45  23  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 37
Left-Left RotationRight-Left RotationRight-Right Rotation
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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

« Prev - C++ Program to Perform Dictionary Operations in a Binary Search Tree

» Next - C++ Program to Create the Prufer Code for a Tree

Related Posts:

Recommended Articles: