AVL_Tree.cpp

#include<bits/stdc++.h>
using namespace std;

class Node
{   public:
        int data, height;
        Node * left;
        Node * right;
};

class AVL{
    public:

        Node * root = NULL;  

        AVL(){
              
        }
        
        int get_height(Node * node){
            if(node == NULL)
                return -1;
            return (node->height);
        }

        int get_balance_factor(Node * node){
            if(node == NULL)
                return 0;
            // balance factor = height of left subtree - height of right subtree
            // negative balance factor indicates right imbalance, positive balance factor indicates left imbalance
            return (get_height(node->left) - get_height(node->right));
        }


        Node * LL_rotation(Node * node){
            Node * child = node->left;
            node->left = child->right;
            child->right = node;
            node->height = max(get_height(node->left), get_height(node->right)) + 1;
            child->height = max(get_height(child->left), get_height(child->right)) + 1;
            return child;
        }

        Node * RR_rotation(Node * node){
            Node * child = node->right;
            node->right = child->left;
            child->left = node;
            node->height = max(get_height(node->left), get_height(node->right)) + 1;
            child->height = max(get_height(child->left), get_height(child->right)) + 1;
            return child;
        }

        void pre_order(Node * node)
        {   
            if(node != NULL)
            {   cout << node->data << " ";
                pre_order(node->left);
                pre_order(node->right);
            }
        }

        void in_order(Node * node)
        {   
            if(node != NULL)
            {  
                pre_order(node->left);
                cout << node->data << " ";
                pre_order(node->right);
            }
        }

        Node * insert(Node * node, int val)
        {
            
            if(node == NULL){
                // inserting as a leaf node
                node = new Node;
                node->data = val;
                node->left = NULL;node->right = NULL;
                node->height = 0;
                return node;
            }

            // BST logic 
            if(node->data < val)
                node->right = insert(node->right, val);
            else
                node->left = insert(node->left, val);

            // Update Height
            node->height = max(get_height(node->left), get_height(node->right)) + 1;

            // Get Balance factor
            int b = get_balance_factor(node);

            // Left heavy 
            if(b > 1){
                // LL Rotation 
                if(get_balance_factor(node->left) == 1){
                    node = LL_rotation(node);
                }
                // LR Rotation(RR rotation of left child, RR rotation of node)
                else{
                    node->left = RR_rotation(node->left);
                    node = LL_rotation(node);
                }
            }
            // Right Heavy
            else if(b < -1){
                // RR Rotation Case
                if(get_balance_factor(node->right) == -1){
                    node = RR_rotation(node);
                }
                // RL Rotation(LL rotation of left child, RL rotation of node)
                else{
                    node->right = LL_rotation(node->right);
                    node = RR_rotation(node);
                }
            }
            return node;
        }


        Node * minValueNode(Node* node)
        {
            Node* current = node;

            while (current->left != NULL)
                current = current->left;
         
            return current;
        }
 

        Node * deleteNode(Node * node, int val)
        {
            
            if(node == NULL){
                // val not found in tree
                return node;
            }

            // BST logic 
            if(node->data < val)
                node->right = insert(node->right, val);
            else if(node->data > val)
                node->left = insert(node->left, val);
            else
            {
                // Case 1
                if( (node->left == NULL) || (node->right == NULL) )
                {
                    Node *temp = root->left ? root->left : root->right;
 
                    // Case 1 : No child case
                    if (temp == NULL)
                    {
                        temp = root;
                        root = NULL;
                    }
                    // Case 2 : One child case
                    else
                        *root = *temp;

                    free(temp);
                }
                else
                {
                    // Case 3 : two children: Get smallest in the right subtree
                    Node* temp = minValueNode(root->right);
         
                    root->data = temp->data;
         
                    root->right = deleteNode(root->right, temp->data);
                }
            }

            // Update Height
            node->height = max(get_height(node->left), get_height(node->right)) + 1;

            // Get Balance factor
            int b = get_balance_factor(node);

            // Left heavy 
            if(b > 1){
                // LL Rotation 
                if(get_balance_factor(node->left) == 1){
                    node = LL_rotation(node);
                }
                // LR Rotation(RR rotation of left child, RR rotation of node)
                else{
                    node->left = RR_rotation(node->left);
                    node = LL_rotation(node);
                }
            }
            // Right Heavy
            else if(b < -1){
                // RR Rotation Case
                if(get_balance_factor(node->right) == -1){
                    node = RR_rotation(node);
                }
                // RL Rotation(LL rotation of left child, RL rotation of node)
                else{
                    node->right = LL_rotation(node->right);
                    node = RR_rotation(node);
                }
            }
            return node;
        }

};

int main()
{   
    AVL tree;
    tree.root = tree.insert(tree.root, 10);
    tree.root = tree.insert(tree.root, 20);
    tree.root = tree.insert(tree.root, 30);
    cout << "Pre-order Traversal of the AVL Tree is : ";
    tree.pre_order(tree.root);
    cout<<endl;


    tree.root = tree.deleteNode(tree.root, 20);
    cout << "Pre-order Traversal of the AVL Tree is : ";
    tree.pre_order(tree.root);
    cout<<endl;


    return 0;
}