AVL Tree

//https://www.facebook.com/pages/C%C3%B9ng-h%E1%BB%8Dc-l%E1%BA%ADp-tr%C3%ACnh/632038696941833
//Xin lỗi mọi người code sẽ không giống trong video vì mình không nhìn hết các trường hợp, mọi thắc mắc hay phản hồi các bạn vui lòng inbox lên page trên nha
#include <iostream>
#include <queue>
using namespace std;

#define LH -1
#define EH 0
#define RH 1

struct AVLNode
{
    int x;
    char CSCB;
    AVLNode *pLeft;
    AVLNode *pRight;
};

typedef AVLNode * AVLTree;

void CreateAVLTree(AVLTree &Root)
{
    Root = NULL;
}

AVLNode *CreateAVLNode(int x)
{
    AVLNode *p = new AVLNode;

    if (!p) exit(1);

    p->CSCB = EH;
    p->x = x;
    p->pLeft = NULL;
    p->pRight = NULL;

    return p;
}

//cay con trai lech trai
void Rotate_Left_Left(AVLTree &Root)
{
    AVLNode *p;

    p = Root->pLeft;
    Root->pLeft = p->pRight;
    p->pRight = Root;

    switch (p->CSCB)
    {
    case LH:
        Root->CSCB = EH;
        p->CSCB = EH;
        break;
    case EH:
        p->CSCB = RH;
        Root->CSCB = LH;
        break;
    }

    Root = p;
}

//cay con phai lech phai
void Rotate_Right_Right(AVLTree &Root)
{
    AVLNode *p;

    p = Root->pRight;
    Root->pRight = p->pLeft;
    p->pLeft = Root;

    switch (p->CSCB)
    {
    case EH:
        Root->CSCB = RH;
        p->CSCB = EH;
        break;
    case RH:
        p->CSCB = EH;
        Root->CSCB = EH;
        break;
    }

    Root = p;
}

//cay con phai lech trai
void Rotate_Right_Left(AVLTree &Root)
{
    AVLNode *p1, *p2;

    p1 = Root->pRight;
    p2 = p1->pLeft;
    Root->pRight = p2->pLeft;
    p1->pLeft = p2->pRight;
    p2->pLeft = Root;
    p2->pRight = p1;

    switch (p2->CSCB)
    {
    case LH:
        Root->CSCB = EH;
        p1->CSCB = RH;
        break;
    case EH:
        Root->CSCB = EH;
        p1->CSCB = EH;
        break;
    case RH:
        Root->CSCB = LH;
        p1->CSCB = EH;
        break;
    }

    p2->CSCB = EH;
    Root = p2;
}

//cay con trai lech phai
void Rotate_Left_Right(AVLTree &Root)
{
    AVLNode *p1, *p2;

    p1 = Root->pLeft;
    p2 = p1->pRight;
    Root->pLeft = p2->pRight;
    p1->pRight = p2->pLeft;
    p2->pRight = Root;
    p2->pLeft = p1;

    switch (p2->CSCB)
    {
    case LH:
        p1->CSCB = EH;
        Root->CSCB = RH;
        break;
    case EH:
        Root->CSCB = EH;
        p1->CSCB = EH;
        break;
    case RH:
        Root->CSCB = EH;
        p1->CSCB = LH;
        break;
    }

    p2->CSCB = EH;
    Root = p2;
}

//Can bang khi cay lech trai
int BalanceLeft(AVLTree &Root)
{
    AVLNode *p;

    p = Root->pLeft;

    switch (p->CSCB)
    {
    case LH:
        Rotate_Left_Left(Root);
        return 2;
    case EH:
        Rotate_Left_Left(Root);
        return 1;
    case RH:
        Rotate_Left_Right(Root);
        return 2;
    }
}

//can bang cay lech phai
int BalanceRight(AVLTree &Root)
{
    AVLNode *p;

    p = Root->pRight;

    switch (p->CSCB)
    {
    case RH:
        Rotate_Right_Right(Root);
        return 2;
    case EH:
        Rotate_Right_Right(Root);
        return 1;
    case LH:
        Rotate_Right_Left(Root);
        return 2;
    }
}

//Chen 1 node vao cay AVL
int InsertNode(AVLTree &Root, int x)
{
    int Res;
    if (Root)
    {
        //gia tri da co trong cay
        if (Root->x == x) return 0;

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

            //Res >= 2
            switch (Root->CSCB)
            {
            case RH:
                Root->CSCB = EH;
                return 1;
            case EH:
                Root->CSCB = LH;
                return 2;
            case LH:
                BalanceLeft(Root);
                return 1;
            }
        }

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

            if (Res < 2) return Res;

            //Res >= 2
            switch (Root->CSCB)
            {
            case LH:
                Root->CSCB = EH;
                return 1;
            case EH:
                Root->CSCB = RH;
                return 2;
            case RH:
                BalanceRight(Root);
                return 1;
            }
        }
    }

    Root = CreateAVLNode(x);
    return 2;
}

//Tim node the mang
int SearchStandFor(AVLTree &Root, AVLNode *&p)
{
    int Res;

    if (p->pLeft)
    {
        Res = SearchStandFor(Root, p->pLeft);

        if (Res < 2) return Res;

        switch (p->CSCB)
        {
        case LH:
            p->CSCB = EH;
            return 1;
        case EH:
            p->CSCB = RH;
            return 2;
        case RH:
            return BalanceRight(Root);
        }
    }

    Root->x = p->x;
    Root = p;
    p = p->pRight;
    return 2;
}

//Xoa 1 node tren cay
int DelNode(AVLTree &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->x > x)
    {
        Res = DelNode(Root->pLeft, 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->CSCB)
        {
        case LH:
            Root->CSCB = EH;
            return 2;
        case EH:
            Root->CSCB = RH;
            return 1;
        case RH:
            return BalanceRight(Root);
        }
    }

    if (Root->x < x)
    {
        Res = DelNode(Root->pRight, x);

        if (Res < 2) return Res;

        switch (Root->CSCB)
        {
        case LH:
            return BalanceLeft(Root);
        case EH:
            Root->CSCB = LH;
            return 1;
        case RH:
            Root->CSCB = EH;
            return 2;
        }
    }
    else
    {
        //Root->x = x
        AVLNode *p1 = Root;

        if (Root->pLeft == NULL)
        {
            Root = Root->pRight;
            Res = 2;
        }
        else
        {
            if (Root->pRight == NULL)
            {
                Root = Root->pLeft;
                Res = 2;
            }
            else
            {
                Res = SearchStandFor(p1, Root->pRight);

                if (Res < 2) return Res;
                switch (Root->CSCB)
                {
                case RH:
                    Root->CSCB = EH;
                    return 2;
                case EH:
                    Root->CSCB = LH;
                    return 1;
                case LH:
                    return BalanceRight(Root);
                }
            }
            delete p1;
            return Res;
        }
    }

}

//Duyet theo muc
void Level(AVLTree Root)
{
    queue<AVLTree> q;
    AVLTree p;

    if (Root == NULL) return;

    p = Root;
    q.push(p);

    while (!q.empty())
    {
        p = q.front();
        q.pop();
        cout << p->x << endl;

        if (p->pLeft) q.push(p->pLeft);
        if (p->pRight) q.push(p->pRight);
    }
}

void Input(AVLTree &Root)
{
    int x;
    do
    {
        cout << "x = 0 de thoat: x = ";
        cin >> x;
        if (x == 0) break;
        InsertNode(Root, x);
    } while (1);
}

void main()
{
    AVLTree Root;
    CreateAVLTree(Root);
    InsertNode(Root, 866);
    InsertNode(Root, 790);
    InsertNode(Root, 879);
    InsertNode(Root, 777);
    InsertNode(Root, 864);
    InsertNode(Root, 870);
    InsertNode(Root, 900);
    InsertNode(Root, 475);
    InsertNode(Root, 863);
    InsertNode(Root, 865);
    InsertNode(Root, 867);
    InsertNode(Root, 875);
    InsertNode(Root, 888);
    InsertNode(Root, 915);
    DelNode(Root, 777);
    DelNode(Root, 790);
    Level(Root);
    system("pause");
}