이 진 트 리 - AVL 트 리 삭제 노드

앞에서 우 리 는 AVL 트 리 를 만 드 는 AVL 트 리 삽입 노드, 즉 노드 의 삽입 을 썼 습 니 다. 다음은 AVL 트 리 노드 의 삭 제 를 소개 합 니 다. 앞에서 조정 한 방법 과 마찬가지 로 트 리 가 불 균형 할 때 트 리 를 조정 합 니 다. 구체 적 인 절 차 는 다음 과 같 습 니 다.
1. - 트 리 가 NULL 인지 판단 하고 NULL 이면 false 로 되 돌아 갑 니 다. -트 리 가 하나의 노드 만 있 는 지 판단 하고 이 노드 는 삭제 할 노드 로 직접 삭제 합 니 다.pRoot 설치 NULL; -그렇지 않 으 면 노드 의 비트 값 을 삭제 하고 이 노드 (세 가지 상황 으로 나 뉘 어) 를 삭제 하 며 삭제 할 노드 를 아이 노드 로 대체 합 니 다. 이 과정 트 리 는 불 균형 이 생 길 수 있 으 므 로 조정 해 야 합 니 다.
2. 노드 삭제: - 삭제 할 노드 는 왼쪽 아이 만 있 을 때; -삭제 할 노드 는 오른쪽 아이 만 있 습 니 다. -삭제 할 노드 는 좌우 아이들 이 존재 합 니 다. 이때 오른쪽 하위 트 리 의 첫 번 째 노드 를 옮 겨 다 니 며 교체 하고 삭제 합 니 다.
3. 삭제 후 밸 런 스 인 자 를 업데이트 하여 트 리 의 밸 런 스 여 부 를 판단 하고 해당 하 는 회전 처 리 를 한다.
코드 구현:

    bool _Remove(const k& key,const v& value)
    {
        if(_pRoot == NULL)
            return false;
        if(_pRoot->_pLeft == NULL && _pRoot->_pRight == NULL && _pRoot->_key == key)
        {
            delete _pRoot;
            _pRoot = NULL;
        }

        //        
        Node* pNode = _pRoot;
        Node* pParent = NULL;

        while(pNode)
        {
            if(pNode->_key > key)
            {
                pParent = pNode;
                pNode = pNode->_pLeft;
            }
            else if(pNode->_key < key)
            {
                pParent = pNode;
                pNode = pNode->_pRight;
            }
            else
                break;
        }
        //         
        Node* pDel = NULL;

        if(pNode)
        {
            if(pNode->_pLeft == NULL)//       
            {
                if(_pRoot->_key == pNode->_key)
                {
                    pDel = pNode;
                    _pRoot = pNode->_pRight;
                    delete pDel;
                    //          
                    return true;
                }
                else
                {
                    if(pParent->_pLeft == pNode)
                    {
                        pDel = pNode;
                        pParent->_pLeft = pNode->_pRight;
                        pNode = pParent->_pLeft;
                        //      
                        //pParent->_bf++;
                    }
                    else
                    {
                        pDel = pNode;
                        pParent->_pRight = pNode->_pRight;
                        pNode = pParent->_pRight;
                    }
                }
            }
            else if(pNode->_pRight == NULL)//     
            {
                if(_pRoot == pNode)
                {
                    pDel = pNode;
                    _pRoot = pNode->_pLeft;
                    delete pDel;
                    //          
                    return true;
                }
                else
                {
                    if(pParent->_pLeft = pNode)
                    {
                        pDel = pNode;
                        pParent->_pLeft = pNode->_pLeft;
                        pNode = pParent->_pLeft;
                    }
                    else
                    {
                        pDel = pNode;
                        pParent->_pRight = pNode->_pLeft;
                        pNode = pParent->_pRight;
                    }
                }
            }
            else //       
            {
                Node* pCur = pNode;
                while(pCur->_pLeft)
                {
                    pParent = pCur;
                    pCur = pCur->_pLeft;//            
                }

                pNode->_key = pCur->_key;
                pNode->_value = pCur->_value;


                pDel = pCur;//????

                pParent->_pLeft = pCur->_pRight;
                pNode = pParent->_pLeft;

            }
            delete pDel;
        }


        //     pDel，      
        while(pParent)
        {
            if(pParent->_pLeft == pNode)//       
                pParent->_bf++;
            else if(pParent->_pRight == pNode)//       
                pParent->_bf--;
            if(pParent->_bf == 1 || pParent->_bf == -1)//pParent       ，           
                return true;
            else if(pParent->_bf == 0)
            {
                //if(pParent->_pLeft == pDel)//pParent     
                //{}
                pNode = pParent;
                pParent = pParent->_pParent;
            }
            else
            {
                //      ，      
                if(pParent->_bf == 2)//   
                {
                    if(pNode==NULL ||pNode->_bf == 1)//  
                        _RotateL(pParent);//    
                    else//  
                        _RotateRL(pParent);//      
                }
                else//   
                {
                    if(pNode==NULL || pNode->_bf == -1)//  
                        _RotateR(pParent);
                    else//  
                        _RotateLR(pParent);
                }
                break;//        
            }   
        }
    }

회전 처 리 는 이전 블 로그, AVL 의 생 성 을 볼 수 있 습 니 다. 여 기 는 군말 하지 않 습 니 다.