AVL.cpp

#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        left = right = nullptr;
        height = 1;
    }
};

class AVL {
    Node* root;

    int getHeight(Node* node) {
        return node ? node->height : 0;
    }

//    int getHeight(Node* node) {
//        if (node != nullptr) {
//            return node->height;
//        } else {
//            return 0;
//        }
//    }


    int getBalance(Node* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

//    int getBalance(Node* node) {
//        if (node != nullptr) {
//            int leftHeight = getHeight(node->left);
//            int rightHeight = getHeight(node->right);
//            return leftHeight - rightHeight;
//        } else {
//            return 0;
//        }
//    }


    int max(int a, int b) {
        return (a > b) ? a : b;
    }

//    int max(int a, int b) {
//        if (a > b) {
//            return a;
//        } else {
//            return b;
//        }
//    }

    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        y->left = x;

        x->height = 1 + max(getHeight(x->left), getHeight(x->right));
        y->height = 1 + max(getHeight(y->left), getHeight(y->right));

        return y;
    }

    Node* rotateRight(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        x->right = y;

        y->height = 1 + max(getHeight(y->left), getHeight(y->right));
        x->height = 1 + max(getHeight(x->left), getHeight(x->right));

        return x;
    }

    Node* balance(Node* node) {
        int bf = getBalance(node);

        if (bf > 1 && getBalance(node->left) >= 0)
            return rotateRight(node);
        if (bf > 1 && getBalance(node->left) < 0) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        if (bf < -1 && getBalance(node->right) <= 0)
            return rotateLeft(node);
        if (bf < -1 && getBalance(node->right) > 0) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }

    Node* insert(Node* node, int val) {
        if (node == nullptr) {
            return new Node(val);
        }
        if (val < node->data) {
            node->left = insert(node->left, val);
        } else if (val > node->data) {
            node->right = insert(node->right, val);
        } else {
            return node;
        }
        node->height = 1 + max(getHeight(node->left), getHeight(node->right));
        return balance(node);
    }

    Node* findMin(Node* pNode){
        if(pNode == nullptr){
            return nullptr;
        }
        else if (pNode->left == nullptr){
            return pNode;
        }
        else {
            return findMin(pNode->left);
        }
    }

    Node* finMax(Node* pNode){
        if(pNode == nullptr){
            return nullptr;
        }
        else if (pNode->right == nullptr){
            return pNode;
        }
        else{
            return finMax(pNode->right);
        }
    }

    Node* remove(Node* pNode, int val) {
        if (pNode == nullptr) {
            return nullptr;
        }
        else if (val < pNode->data) {
            pNode->left = remove(pNode->left, val);
        }
        else if (val > pNode->data) {
            pNode->right = remove(pNode->right, val);
        }
        else {
            if (pNode->left == nullptr && pNode->right == nullptr) {
                delete pNode;
                pNode = nullptr;
            }
            else if (pNode->left == nullptr && pNode->right != nullptr) {
                Node* temp = pNode->right;
                delete pNode;
                pNode = temp;
            }
            else if (pNode->left != nullptr && pNode->right == nullptr) {
                Node* temp = pNode->left;
                delete pNode;
                pNode = temp;
            }
            else {
                Node* min = findMin(pNode->right);
                pNode->data = min->data;
                pNode->right = remove(pNode->right, min->data);
            }
        }

        if (pNode == nullptr)
            return nullptr;

        pNode->height = 1 + max(getHeight(pNode->left), getHeight(pNode->right));
        return balance(pNode);
    }

    void inOrder(Node* node) {
        if (node == nullptr) return;
        inOrder(node->left);
        cout << node->data << " ";
        inOrder(node->right);
    }

public:
    AVL() {
        root = nullptr;
    }

    void insert(int val) {
        root = insert(root, val);
    }

    void remove(int val) {
        root = remove(root, val);
    }

    void displayInOrder() {
        inOrder(root);
        cout << endl;
    }

    int height() {
        return getHeight(root);
    }
};

int main() {
    AVL tree;

    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(10);
    tree.insert(25);
    tree.insert(50);
    tree.insert(5);

    cout << "InOrder Traversal: ";
    tree.displayInOrder();

    cout << "Tree Height: " << tree.height() << endl;

    tree.remove(40);

    cout << "After Deletion (40): ";
    tree.displayInOrder();

    return 0;
}