고도 균형 이 진 트 리 (AVL) 삽입 및 삭제

avl 트 리 삽입
균형 이 잡 힌 이 진 트 리: 빈 나무 나 좌우 자나무 의 높이 차 이 는 1 을 넘 지 않 고 좌우 자나무 가 각각 균형 이 잡 힌 이 진 트 리 입 니 다.한편, AVL 트 리 를 삽입 하려 면 이 진 트 리 의 균형 성 을 조정 하여 균형 적 이 고 질서 있 게 해 야 한다. 여 기 는 왼쪽 회전, 오른쪽 회전, 좌우 쌍 회전 이 필요 하 다.또한 해당 하 는 균형 인 자 를 조절 하고 균형 인 자 는 오른쪽 나무 높이 에서 왼쪽 나무 높이 를 뺀 것 과 같다.AVLTreeNOde:

struct AVLNode
    {
        AVLNode *leftchild;
        AVLNode*rightchild;
        AVLNode*parent;
        int balance;
        KeyType key;
    };

왼쪽 회전:

static void RotateLeft(AVLNode*&p)
    {
        if (p == NULL)
            return;
        AVLNode*newroot = p->rightchild;
        newroot->parent = p->parent;
        p->rightchild = newroot->leftchild;
        if (newroot->leftchild != NULL)
        {

            newroot->leftchild->parent = p;
        }
        newroot->leftchild = p;
        p->parent = newroot;
        p = newroot;

    }

오른쪽 회전:

    static void RotateRight(AVLNode*&p)
    {
        if (p == NULL)
            return;
        AVLNode*newroot = p->leftchild;
        newroot->parent = p->parent;
        p->leftchild = newroot->rightchild;
        if (newroot->rightchild != NULL)
        {
            newroot->rightchild->parent = p;
        }
        newroot->rightchild = p;
        p->parent = newroot;
        p = newroot;
    }

나무 가 불 균형 할 때 좋 은 여러 가지 상황 이 있다. 모든 상황 에 따라 균형 후의 균형 인자 상황 을 기록 하면 규칙 을 발견 할 수 있다. 여 기 는 왼쪽 균형 과 오른쪽 균형 두 가지 로 나 뉜 다. 왼쪽 균형:

static void LeftBalance(AVLNode *&p)
    {
        if (p == NULL)
            return;
        AVLNode*right = p->rightchild;
        AVLNode*left = NULL;
        switch (right->balance)
        {
        case 0:
            if ((GetDepth(p->rightchild) - GetDepth(p->leftchild)) <= 1)
                cout << "balanced" << endl; 
            else
            {
                right->balance = -1; p->balance = 1;
                RotateLeft(p);
            }
            break;
        case 1:
            right->balance = p->balance = 0;
            RotateLeft(p);
            break;
        case -1:
            left = right->leftchild;
            switch (left->balance)
            {
            case 0:  right->balance  = left->balance = p->balance = 0; break;
            case 1:  left->balance = right->balance = 0; p->balance = -1; break;
            case -1: left->balance = p->balance = 0; right->balance = 1; break;
            }

            RotateRight(p->rightchild); 
            RotateLeft(p);
            break;
        default:
            cout << "error" << endl;
            break;
        }
    }

오른쪽 균형:

    static void RightBalance(AVLNode*&p)
    {
        if (p == NULL)
            return;
        AVLNode*left = p->leftchild;
        AVLNode*right = NULL;
        switch (left->balance)
        {
        case 0:
            if((GetDepth(p->rightchild)-GetDepth(p->leftchild))>=-1)
                cout << "balanced" << endl;
            else
            {
                p->balance = -1; left->balance = 1;
                RotateRight(p);
            }
            break;
        case 1:
            right = left->rightchild;
            switch (right->balance)
            {
            case 0:right->balance = left->balance = p->balance =  0; break;
            case 1:left->balance = -1; p->balance = right->balance = 0; break;
            case -1:p->balance = 1; right->balance = left->balance = 0; break;
            }
            RotateLeft(p->leftchild);
            RotateRight(p);
            break;
        case -1:
            p->balance = left->balance = 0;
            RotateRight(p);
            break;
        default:
            cout << "error" << endl;
            break;
        }
    }

삽입 은 하나의 요 소 를 삽입 할 때마다 균형 요 소 를 바 꾸 고 불 균형 하면 조정 하 는 것 입 니 다. 코드 삽입:

static bool Insert(AVLNode*&root, KeyType k, AVLNode*p)
    {
        bool res = false;
        if (root == NULL)
        {
            AVLNode*node = BuyNode();
            node->key = k;
            node->parent = p;
            root = node;
            res=true;
        }
        else if (root->key > k)
        {
            res=Insert(root->leftchild, k, root);
            if (res == true)
            {
                switch (root->balance)
                {
                case 0:root->balance = -1; break;
                case 1:root->balance = 0; break;
                case -1:
                    RightBalance(root);
                    break;
                default:
                    cout << "error" << endl;
                    break;
                }
            }
        }
        else if (root->key < k)
        {
            res= Insert(root->rightchild, k, root);
            if (res == true)
            {
                switch (root->balance)
                {
                case 0:root->balance = 1; break;
                case 1:
                    LeftBalance(root); break;
                case -1:root->balance = 0; break;
                default:
                    cout << "error" << endl;
                    break;
                }
            }
        }
        return res;
    }

삽입 과 비슷 한 코드 를 삭제 하 는 것 은 다음 과 같 습 니 다.

static bool ReMove_ex(AVLNode* &root, KeyType e)
    {
        bool res = false;
        if (root == NULL)
            res= false;
        else if (root->key > e)
        {
            res = ReMove_ex(root->leftchild, e);

            if (res == true)
            {
                /*switch (root->balance)
                {
                case 0:root->balance = 1; break;
                case 1:LeftBalance(root); break;
                case -1:root->balance=0; break;
                }*/
                int balance = GetDepth(root->rightchild) - GetDepth(root->leftchild);
                if (balance >= 2)
                {
                    LeftBalance(root);
                }
                else
                {
                    root->balance = balance;
                }
            }

        }
        else if (root->key < e)
        {
            res = ReMove_ex(root->rightchild, e);
            if (res == true)
            {
                int balance = GetDepth(root->rightchild) - GetDepth(root->leftchild);
                if (balance <= -2)
                {
                    RightBalance(root);
                }
                else
                {
                    root->balance = balance;
                }
            }
        }
        else
        {
            if (root->leftchild != NULL&&root->rightchild != NULL)
            {
                AVLNode*child = Next(root);
                root->key = child->key;
                res=ReMove_ex(root->rightchild, child->key);
            }
            else//    
            {
                AVLNode*p = root->leftchild == NULL ? root->rightchild : root->leftchild;
                if (p != NULL)
                    p->parent = root->parent;
                free(root);
                root = p;
                //(*size)--;
                res = true;
            }
        }
        return res;
    }