AVLTree.cpp

#include <iostream>
using namespace std;

struct BSTNode
{
    int data;
    int bf;
    BSTNode *LChild = NULL;
    BSTNode *RChild = NULL;
} *root = NULL;

int calculateHeight(BSTNode *node, int height)
{
    int rh, lh;
    if (node == NULL)
    {
        return 0;
    }
    // incrementing height when a node != null,maintains height at every recursive call
    height++;
    // if node has no child
    if (node->LChild == NULL && node->RChild == NULL)
    {
        return height;
    }
    // if node has 1 right child. case where node->RChild->RChild
    if (node->LChild == NULL)
    {
        node = node->RChild;
        rh = calculateHeight(node, height);
        return rh;
    }
    // if node has 1 left child. case where node->LChild->LChild
    else if (node->RChild == NULL)
    {
        node = node->LChild;
        lh = calculateHeight(node, height);
        return lh;
    }
    // if node has both childs
    else
    {
        // height from the node's left child
        lh = calculateHeight(node->LChild, height);
        // height from the node's left child
        rh = calculateHeight(node->RChild, height);
        if (lh > rh)
        {
            height = lh;
        }
        else
        {
            height = rh;
        }
    }
    return height;
}
// BF = L-Subtree's Height - R-Subtree's Height.
// Updating the balance factor of all the nodes in the current tree after every insertion
int updateBalanceFactor(BSTNode *UB)
{
    int LHeight, RHeight;
    LHeight = calculateHeight(UB->LChild, 0);
    cout << "L: " << LHeight << endl;
    RHeight = calculateHeight(UB->RChild, 0);
    cout << "R: " << RHeight << endl;
    return LHeight - RHeight;
}
// when node is un-balanced form right subtree and new insertion is on the right side
BSTNode* shift_left(BSTNode* UB)
{
    if (UB->RChild == NULL)
    {
        return UB;
    }
    BSTNode* temp = UB->RChild->LChild;
    BSTNode* temp2 = UB->RChild;
    UB->RChild->LChild = UB;
    UB->RChild = temp;
    return temp2;
}
// when node is un-balanced form left subtree and new insertion is on the left side
BSTNode* shift_right(BSTNode *UB)
{
    BSTNode *temp = UB->LChild->RChild;
    BSTNode* temp2 = UB->LChild;
    UB->LChild->RChild = UB;
    UB->LChild = temp;
    return temp2;
}
// when node is un-balanced form left subtree and new insertion is on the right side
BSTNode*  DoubleShift_LR(BSTNode *UB)
{
    // stroring the UB->LChild->RChild to help re-connecting with the tree
    BSTNode *temp = UB->LChild->RChild;
    UB->LChild = shift_left(UB->LChild);
    return shift_right(UB);
}
// when node is un-balanced form right subtree and new insertion is on the left side
BSTNode* DoubleShift_RL(BSTNode *UB)
{
    // stroring the UB->RChild->LChild to help re-connecting with the tree
    BSTNode *temp = UB->RChild->LChild;
    UB->RChild = shift_right(UB->RChild);
    return shift_left(UB);
}
BSTNode* rebalanceTree(BSTNode* UB,BSTNode* node)
{
    //temp stores the latest inserted node.
    BSTNode*temp;
    if (node->LChild != NULL)
    {
        temp = node->LChild;
    }
    else if (node->RChild != NULL)
    {
        temp = node->RChild;
    }
    
    // it means the height of the left subtree is greater than that of the right subtree
    if (UB->bf > 1)
    {
        // do right rotation if the newNode->value < UB->LChild->value
        if (UB->LChild != NULL && temp->data < UB->LChild->data)
        {
            cout<<"SR ";
            UB = shift_right(UB);
        }
        // Else, do left-right rotation
        else if (UB->LChild != NULL && temp->data > UB->LChild->data)
        {
            cout<<"SLR ";
            UB = DoubleShift_LR(UB);
        }
    }
    // it means the height of the right subtree is greater than that of the left subtree
    else if (UB->bf < -1)
    {
        // do left rotation if the newNode->value > UB->RChild->value
        if (UB->RChild != NULL && temp->data > UB->RChild->data)
        {
            cout<<"SL ";
            UB = shift_left(UB);
        }
        // Else, do right-left rotation
        else if (UB->RChild != NULL && temp->data < UB->RChild->data)
        {
            cout<<"SRL ";
            UB = DoubleShift_RL(UB);
        }
    }
    return UB;
}
BSTNode *insert(BSTNode *node, int value)
{
    if (node == NULL)
    {
        BSTNode *temp = (BSTNode *)malloc(sizeof(BSTNode));
        temp->data = value;
        temp->bf = 0;
        temp->LChild = NULL;
        temp->RChild = NULL;
        return temp;
    }
    if (value < node->data)
    {
        node->LChild = insert(node->LChild, value);
    }
    else
    {
        node->RChild = insert(node->RChild, value);
    }
    node->bf = updateBalanceFactor(node);
    cout<<"BF: "<<node->bf<<endl;
    // it means the height of the left subtree is greater than that of the right subtree
    if (node->bf > 1)
    {
        cout<<"Right Rotation "<<endl;
        node = rebalanceTree(node,node->LChild);
    }
    // it means the height of the right subtree is greater than that of the left subtree
    else if (node->bf < -1)
    {
        cout<<"Left Rotation "<<endl;
        node = rebalanceTree(node,node->RChild);
    }
    return node;
}
BSTNode* FindMinimum(BSTNode* node){
    BSTNode* curr = node;
    while (curr->LChild != NULL)
    {
        curr = curr->LChild;
    }
    return curr;
}
BSTNode* Delete(BSTNode* node, int value){
    //Locate nodeToBeDeleted
    if (node == NULL)
    {
        return NULL;
    }
    if (value < node->data)
    {
        node->LChild = Delete(node->LChild,value);
    }
    else if (value > node->data)
    {
        node->RChild = Delete(node->RChild,value);
    }
    else{
        BSTNode* temp;
        if (node->LChild == NULL && node->RChild == NULL)
        {
            free(node);
            return NULL;
        }
        //If nodeToBeDeleted has one child, then swap nodeToBeDeleted with that child. 
        //Remove the child
        else if (node->LChild == NULL)
        {
            temp = node->RChild;
            free(node);
            return temp;
        }
        else if (node->RChild == NULL)
        {
            temp = node->LChild;
            free(node);
            return temp;
        }
        // Having 2 Children
        temp = FindMinimum(node->RChild);
        node->data = temp->data;
        node->RChild = Delete(node->RChild,temp->data);
    }
    node->bf = updateBalanceFactor(node);
    cout<<"BF: "<<node->bf<<endl;
    // it means the height of the left subtree is greater than that of the right subtree
    if (node->bf > 1)
    {
        cout<<"Right Rotation "<<endl;
        node = rebalanceTree(node,node->LChild);
    }
    // it means the height of the right subtree is greater than that of the left subtree
    else if (node->bf < -1)
    {
        cout<<"Left Rotation "<<endl;
        node = rebalanceTree(node,node->RChild);
    }
    return node;
}
void preOrder(BSTNode *node)
{
    if (node != NULL)
    {
        cout << node->data << " ";
        preOrder(node->LChild);
        preOrder(node->RChild);
    }
}
int main(int argc, char const *argv[])
{
    int value = 0;
    cout << "Enter value to insert ";
    cin >> value;
    while (value > -1)
    {
        root = insert(root, value);
        cout << "Enter value to insert ";
        cin >> value;
    }
    preOrder(root);
    cout << "Enter value to delete ";
    cin >> value;
    while (value > -1)
    {
        root = Delete(root, value);
        cout << "Enter value to delete ";
        cin >> value;
    }
    preOrder(root);
    cout << endl;
    return 0;
}