AVL

#include <iostream>
using namespace std;
#define Left_higher -1;
#define Equal_height 0;
#define Right_higher 1;
typedef struct node
{
    char balance_factor;
    int data;
    node*left;
    node*right;
}AVL_NODE;
/*Question 1*/
AVL_NODE *CreateAVLNode(int x)
{
    AVL_NODE *p = new AVL_NODE;

    if (!p) exit(1);

    p->balance_factor = Equal_height;
    p->data = x;
    p->left = NULL;
    p->right = NULL;

    return p;
}
/*Cay con trai lech trai*/
void Rotate_Left_Left(AVL_NODE*&root)
{
    AVL_NODE*p;
    p = root->left;
    root->left = p->right;
    p->right = root;
    switch (p->balance_factor)
    {
    case -1:
    {
               root->balance_factor = Equal_height;
               p->balance_factor = Equal_height;
               break;
    }
    case 0:
        p->balance_factor = Right_higher;
        root->balance_factor = Left_higher;
        break;
    }
    root = p;
}
/*Cay con phai lech phai*/
void Rotate_Right_Right(AVL_NODE*&root)
{
    AVL_NODE*p;
    p = root->right;
    root->right = p->left;
    p->left = root;
    switch (p->balance_factor)
    {
    case 0:
        root->balance_factor = Right_higher;
        p->balance_factor = Equal_height;
        break;
    case 1:
        p->balance_factor = Equal_height;
        root->balance_factor = Equal_height;
        break;
    }
    root = p;
}
//Cay con phai lech trai
void Rotate_Right_Left(AVL_NODE* &root)
{
    AVL_NODE *p1, *p2;

    p1 = root->right;
    p2 = p1->left;
    root->right = p2->left;
    p1->left = p2->right;
    p2->left = root;
    p2->right = p1;

    switch (p2->balance_factor)
    {
    case -1:
        root->balance_factor = Equal_height;
        p1->balance_factor = Right_higher;
        break;
    case 0:
        root->balance_factor = Equal_height;
        p1->balance_factor = Equal_height;
        break;
    case 1:
        root->balance_factor = Left_higher;
        p1->balance_factor = Equal_height;
        break;
    }

    p2->balance_factor = Equal_height;
    root = p2;
}
/*Cay con trai lech phai*/
void Rotate_Left_Right(AVL_NODE* &root)
{
    AVL_NODE *p1, *p2;

    p1 = root->left;
    p2 = p1->right;
    root->left = p2->right;
    p1->right = p2->left;
    p2->right = root;
    p2->left = p1;

    switch (p2->balance_factor)
    {
    case -1:
        p1->balance_factor = Equal_height;
        root->balance_factor = Right_higher;
        break;
    case 0:
        root->balance_factor = Equal_height;
        p1->balance_factor = Equal_height;
        break;
    case 1:
        root->balance_factor = Equal_height;
        p1->balance_factor = Left_higher;
        break;
    }

    p2->balance_factor = Equal_height;
    root = p2;
}
/*Can bang khi cay lech trai*/
int BalanceLeft(AVL_NODE* &root)
{
    AVL_NODE *p;

    p = root->left;

    switch (p->balance_factor)
    {
    case -1:
        Rotate_Left_Left(root);
        return 2;
    case 0:
        Rotate_Left_Left(root);
        return 1;
    case 1:
        Rotate_Left_Right(root);
        return 2;
    }
}
/*Can bang khi cay lech phai*/
int BalanceRight(AVL_NODE* &root)
{
    AVL_NODE *p;

    p = root->right;

    switch (p->balance_factor)
    {
    case 1:
        Rotate_Right_Right(root);
        return 2;
    case 0:
        Rotate_Right_Right(root);
        return 1;
    case -1:
        Rotate_Right_Left(root);
        return 2;
    }
}
/*Insert node to the tree*/
int InsertNode(AVL_NODE* &root, int x)
{
    int Res;
    if (root)
    {
        //gia tri da co trong cay
        if (root->data == x) return 0;

        //Root->x > x
        //chen vao ben trai
        if (root->data > x)
        {
            Res = InsertNode(root->left, x);
            if (Res < 2) return Res;

            //Res >= 2
            switch (root->balance_factor)
            {
            case 1:
                root->balance_factor = Equal_height;
                return 1;
            case 0:
                root->balance_factor = Left_higher;
                return 2;
            case -1:
                BalanceLeft(root);
                return 1;
            }
        }

        //Root->x < x
        //chen vao ben phai
        else
        {
            Res = InsertNode(root->right, x);

            if (Res < 2) return Res;

            //Res >= 2
            switch (root->balance_factor)
            {
            case -1:
                root->balance_factor = Equal_height;
                return 1;
            case 0:
                root->balance_factor = Right_higher;
                return 2;
            case 1:
                BalanceRight(root);
                return 1;
            }
        }
    }

    root = CreateAVLNode(x);
    return 2;
}
void Duyet_NLR(AVL_NODE*root)
{
    if (root != NULL)
    {
        Duyet_NLR(root->left);
        cout << root->data << " ";
        //Duyet_NLR(root->left);
        Duyet_NLR(root->right);
    }
}
/*Question 2*/
int SearchStandFor(AVL_NODE*&root, AVL_NODE*&p)
{
    int Res;

    if (p->left)
    {
        Res = SearchStandFor(root, p->left);

        if (Res < 2) return Res;

        switch (p->balance_factor)
        {
        case -1:
            p->balance_factor = Equal_height;
            return 1;
        case 0:
            p->balance_factor = Right_higher;
            return 2;
        case 1:
            return BalanceRight(p);
        }

    }

    root->data = p->data;
    root = p;
    p = p->right;
    return 2;
}
int DelNode(AVL_NODE* &root, int x)
{
    int Res;

    //Khong ton tai node nay tren cay
    if (!root) return 0;

    //Qua duoc if tren tuc la ton tai
    //Root->x > x => Sang ben trai tim xoa
    if (root->data > x)
    {
        Res = DelNode(root->left, x);

        //Neu co xoa thi Res = 1 hoac 2. 2 tuc thay doi chieu cao cay
        if (Res < 2) return Res;

        //Chieu cao bi thay doi
        switch (root->balance_factor)
        {
        case -1:
            root->balance_factor = Equal_height;
            return 2;
        case 0:
            root->balance_factor = Right_higher;
            return 1;
        case 1:
            return BalanceRight(root);
        }
    }

    if (root->data < x)
    {
        Res = DelNode(root->right, x);

        if (Res < 2) return Res;

        switch (root->balance_factor)
        {
        case -1:
            return BalanceLeft(root);
        case 0:
            root->balance_factor = Left_higher;
            return 1;
        case 1:
            root->balance_factor = Equal_height;
            return 2;
        }
    }
    else
    {
        //Root->x = x
        AVL_NODE *p1 = root;

        if (root->left == NULL)
        {
            root = root->right;
            Res = 2;
        }
        else
        {
            if (root->right == NULL)
            {
                root = root->left;
                Res = 2;
            }
            else
            {
                Res = SearchStandFor(p1, root->right);

                if (Res < 2) return Res;
                switch (root->balance_factor)
                {
                case 1:
                    root->balance_factor = Equal_height;
                    return 2;
                case 0:
                    root->balance_factor = Left_higher;
                    return 1;
                case -1:
                    return BalanceRight(root);
                }
            }
            delete p1;
            return Res;
        }
    }
}
int main()
{
    AVL_NODE*root = NULL;
    int x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15;
    int d1;
    x1 = InsertNode(root, 4);
    cout << x1 << endl;
    x2 = InsertNode(root, 5);
    cout << x2 << endl;
    x3 = InsertNode(root, 7);
    cout << x3 << endl;
    x4 = InsertNode(root, 10);
    cout << x4 << endl;
    x5 = InsertNode(root, 20);
    cout << x5 << endl;
    x6 = InsertNode(root, 9);
    cout << x6 << endl;
    x7 = InsertNode(root, 11);
    cout << x7 << endl;
    x8 = InsertNode(root, 13);
    cout << x8 << endl;

    cout << "delete\n";
    d1 = DelNode(root, 7);
    cout << d1 << endl;

    Duyet_NLR(root);
    system("pause");
}