AVL

#include<iostream>
using namespace std;

struct Node{
    int key;
    Node *left, *right;
    int height;

    Node(int x){
        this->key=x;
        this->left=NULL;
        this->right=NULL;
        this->height=1;
    }
};

class Avl_tree{
private:
    Node* root;

    void preorderHelper(Node* x){
        if(x==NULL)
            return;
        cout<<x->key<<" ";
        preorderHelper(x->left);
        preorderHelper(x->right);

    }
    Node* insertHelper(Node* x, int key){
        if(x==NULL){
            return new Node(key);
        }
        else if(key > x->key){
            x->right= insertHelper(x->right, key);
        }
        else if(key < x->key){
            x->left= insertHelper(x->left, key);
        }
        else{
            return x;
        }

        x->height= 1+ max(height(x->left), height(x->right));
        int bf= getBalanceFactor(x);

        if(bf> 1 and key < x->left->key){
            return rightRotate(x);
        }
        if(bf> 1 and key> x->left->key){
            x->left= leftRotate(x->left);
            return rightRotate(x);
        }
        if(bf<-1 and key> x->right->key){
            return leftRotate(x);
        }
        if(bf< -1 and key < x->right->key){
            x->right= rightRotate(x->right);
            return leftRotate(x);
        }

        return x;
    }
    Node* InorderSuccessor(Node* x){
        while(x->left!=NULL){
            x=x->left;
        }
        return x;
    }
    Node* deleteHelper(Node* x, int key){
        if(x==NULL){
            return x;
        }
        if(key < x->key){
            x->left= deleteHelper(x->left, key);
        }
        else if(key> x->key){
            x->right= deleteHelper(x->right, key);
        }
        else{
            if(x->left==NULL or x->right==NULL){
                Node* temp= x->left? x->left: x->right;
                free(x);
                return temp;
            }
            else{
                Node* temp=InorderSuccessor(x->right);
                x->key= temp->key;
                x->right= deleteHelper(x->right, temp->key);
            }
        }
        x->height= 1+ max(height(x->left), height(x->right));
        int bf= getBalanceFactor(x);

        if(bf>1 and getBalanceFactor(x->left)>=0){
            return rightRotate(x);
        }
        if(bf>1 and getBalanceFactor(x->left)<0 ){
            x->left= leftRotate(x->left);
            return rightRotate(x);
        }
        if(bf<-1 and getBalanceFactor(x->right)>=0){
            x->right= rightRotate(x->right);
            return leftRotate(x);
        }
        if(bf<-1 and getBalanceFactor(x->right)<0){
            return leftRotate(x);
        }
        return x;
    }
public:
    Avl_tree(){
        root=NULL;
    }
    int height(Node* x){
        if(x==NULL)
            return 0;
        return x->height;
    }
    int getBalanceFactor(Node* x){
        if(x==NULL)
            return 0;
        return height(x->left)-height(x->right);
    }
    Node* leftRotate(Node* x){
        Node *y= x->right;
        Node *z= y->left;

        y->left= x;
        x->right= z;

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

        return y;
    }
    Node* rightRotate(Node* x){
        Node* y= x->left;
        Node* z= y->right;

        y->right= x;
        x->left=z;

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

        return y;
    }

    void insert(int key){
        root= insertHelper(root, key);
    }

    void preorder(){
        preorderHelper(root);
    }
    void deleteNode(int key){
        root= deleteHelper(root, key);
    }

};
int main(){
    Avl_tree avl;
    avl.insert(12);
    avl.insert(1);

    avl.insert(4);
    avl.insert(3);
    avl.insert(7);
    avl.insert(8);
    avl.insert(10);
    avl.insert(2);
    avl.insert(11);
    avl.insert(5);
    avl.insert(6);

    // avl.preorder();
    avl.deleteNode(4);
    avl.deleteNode(8);
    avl.deleteNode(5);
    avl.deleteNode(6);
    avl.preorder();

    return 0;
}