제1 4 장 데이터 구조 확장 동적 순서 통계 부분 코드

이 장 에서 동적 순서 통계 와 구간 트 리 는 데이터 구 조 를 확장 하 는 방법 을 보 여 주 는 데 사용 된다.일반적으로 하나의 데이터 구 조 를 확장 하 는 것 은 다음 과 같은 네 단계 로 나 뉜 다.
4. 567917. 기초 데이터 구 조 를 선택한다
4. 567917. 기초 데이터 구조 에서 유지 해 야 할 추가 정 보 를 확인한다
4. 567917. 기초 데이터 구조 상의 기본 수정 작업 이 추가 정 보 를 유지 할 수 있 는 지 검증 합 니 다
4. 567917. 새로운 조작 을 설계 합 니 다
물론 데이터 구조의 확장 을 설계 하 는 것 은 그리 순 조 롭 지 않 고 탐색 과 오 류 를 영원히 포함 하고 있다.다음은 붉 은 검 은 나무의 동적 순서 통계 와 구간 트 리 에 기반 한 코드 를 드 립 니 다.
동적 순서 통계:
아래 코드 는 왼쪽 회전, 오른쪽 회전, 삽입 으로 인 한 빨 간 검 은 나무 성질 의 파 괴 를 회복 하고 삽입, 삭제 로 인 한 빨 간 검 은 나무 성질 의 파 괴 를 회복 하 며 삭제, i 작은 키 워드 를 찾 아 원소 의 순 서 를 되 돌려 줍 니 다.
왼쪽 회전:

template<class Type>
void orderStatisticTree<Type>::leftRotate(node* x)
{
        node* y=x->right;

        y->parent=x->parent;
        if(x->parent==nullNode)
                root=y;
        else if(x==x->parent->left)
                x->parent->left=y;
        else
                x->parent->right=y;

        x->right=y->left;
        if(y->left!=nullNode)
                x->right->parent=x;

        y->left=x;
        x->parent=y;
//              ，              size。
        y->size=x->size;
        x->size=x->left->size+x->right->size+1;
}

오른쪽 회전:

template<class Type>
void orderStatisticTree<Type>::rightRotate(node* x)
{
         node* y=x->left;

         y->parent=x->parent;
         if(x->parent==nullNode)
                 root=y;
         else if(x==x->parent->left)
                 x->parent->left=y;
         else
                 x->parent->right=y;

         x->left=y->right;
         if(y->right!=nullNode)
                 x->left->parent=x;

         y->right=x;
         x->parent=y;
//              ，              size。
         y->size=x->size;
         x->size=x->left->size+x->right->size+1;
 }

삽입 으로 인 한 붉 은 검 은 나무 성질 의 파 괴 를 복구 합 니 다:
이 코드 는 빨 간 검 은 나무 장의 코드 와 같다.

template<class Type>
void orderStatisticTree<Type>::RBInsertFixup(node* currentNode)
{
         while(currentNode->parent->color==RED){
                 if(currentNode->parent==currentNode->parent->parent->left){
                         node* uncleNode=currentNode->parent->parent->right;
                       if(uncleNode->color==RED){
                                 currentNode->parent->color=BLACK;
                                 uncleNode->color=BLACK;
                                 currentNode->parent->parent->color=RED;
                                 currentNode=currentNode->parent->parent;
                         }
                         else if(currentNode==currentNode->parent->right){
                                 currentNode=currentNode->parent;
                                 leftRotate(currentNode);
                         }
                          else{
                                 currentNode->parent->color=BLACK;
                                 currentNode->parent->parent->color=RED;
                                 rightRotate(currentNode->parent->parent);
                         }
                 }
                 else {
                         node* uncleNode=currentNode->parent->parent->left;
                         if(uncleNode->color==RED){
                                 currentNode->parent->color=BLACK;
                                 uncleNode->color=BLACK;
                                 currentNode->parent->parent->color=RED;
                                 currentNode=currentNode->parent->parent;
                         }
                         else if(currentNode==currentNode->parent->left){
                                 currentNode=currentNode->parent;
                                 rightRotate(currentNode);
                         }
                         else{
                                 currentNode->parent->color=BLACK;
                                 currentNode->parent->parent->color=RED;
                                 leftRotate(currentNode->parent->parent);
                         }
                 }
         }

         root->color=BLACK;
 }

삽입:

template<class Type>
void orderStatisticTree<Type>::insert(const Type& val)
{
        node* currentNode=root;
        node* prevNode=nullNode;

        while(currentNode!=nullNode){
                currentNode->size+=1;//               size 1。
                prevNode=currentNode;
                if(val<currentNode->key)
                        currentNode=currentNode->left;
                else
                        currentNode=currentNode->right;
        }

        if(prevNode==nullNode)
                root=new node(val,1,nullNode,nullNode,nullNode,BLACK);
        else if(val<prevNode->key){
                prevNode->left=new node(val,1,prevNode,nullNode,nullNode,RED);
                RBInsertFixup(prevNode->left);
        }
        else{
                prevNode->right=new node(val,1,prevNode,nullNode,nullNode,RED);
                RBInsertFixup(prevNode->right);
        }
}

삭제 로 인 한 붉 은 검 은 나무의 파괴 회복:

template<class Type>
void orderStatisticTree<Type>::RBRemoveFixup(node* currentNode)
{
        node* tmp=currentNode->parent;
        while(tmp!=nullNode){
                tmp->size=tmp->left->size+tmp->right->size+1;
                tmp=tmp->parent;
        }// currentNode          size 1。

        while(currentNode!=root&&currentNode->color==BLACK){
                if(currentNode==currentNode->parent->left){
                        node* brotherNode=currentNode->parent->right;
                        if(brotherNode->color==RED){
                                brotherNode->color=BLACK;
                                currentNode->parent->color=RED;
                                leftRotate(currentNode->parent);
                        }
                        else if (brotherNode->left->color==BLACK&&brotherNode->right->color==BLACK){
                                brotherNode->color=RED;
                                currentNode=currentNode->parent;
                        }
                        else if(brotherNode->right->color==BLACK){
                                brotherNode->left->color=RED;
                                brotherNode->color=RED;
                                rightRotate(brotherNode);
                                brotherNode=currentNode->parent->right;
                        }
                        else{
                                brotherNode->color=currentNode->parent->color;
                                currentNode->parent->color=BLACK;
                                leftRotate(currentNode->parent);
                                currentNode=root;
                        }
                }
                else{
                        node* brotherNode=currentNode->parent->left;
                        if(brotherNode->color==RED){
                                brotherNode->color=BLACK;
                                currentNode->parent->color=RED;
                                rightRotate(currentNode->parent);
                        }
                        else if (brotherNode->right->color==BLACK&&brotherNode->left->color==BLACK){
                                brotherNode->color=RED;
                                currentNode=currentNode->parent;
                        }
                        else if(brotherNode->left->color==BLACK){
                                brotherNode->right->color=RED;
                                brotherNode->color=RED;
                                leftRotate(brotherNode);
                                brotherNode=currentNode->parent->left;
                        }
                        else{
                                brotherNode->color=currentNode->parent->color;
                                currentNode->parent->color=BLACK;
                                rightRotate(currentNode->parent);
                                currentNode=root;
                        }
                }
        }

        currentNode->color=BLACK;

}

삭제:
코드 는 레 드 블랙 트 리 에서 코드 를 삭제 하 는 것 과 같 습 니 다.

template<class Type>
void orderStatisticTree<Type>::transplant(node* u,node* v)
{
        if(u->parent==nullNode)
                root=v;
        else if(u==u->parent->right)
                u->parent->right=v;
        else
                u->parent->left=v;

        v->parent=u->parent;
}

template<class Type>
bool orderStatisticTree<Type>::remove(const Type& val)
{
        node* searchNode=search(val,root);

        if(searchNode==nullNode)
                return false;

        int originalColor;
        node* x=0;
        if(searchNode->left==nullNode){
                x=searchNode->right;
                transplant(searchNode,searchNode->right);
                originalColor=searchNode->color;
        }
        else if(searchNode->right==nullNode){
                x=searchNode->left;
                transplant(searchNode,searchNode->left);
                originalColor=searchNode->color;
        }
        else{
                node* succNode=findMinimum(searchNode->right);
                originalColor=succNode->color;
                x=succNode->right;

                if(succNode->parent==searchNode)
                        x->parent=succNode;
                else{
                        transplant(succNode,succNode->right);
                        succNode->right=searchNode->right;
                        succNode->right->parent=succNode;
                }
                transplant(searchNode,succNode);
                succNode->left=searchNode->left;
                succNode->color=searchNode->color;
                succNode->size=searchNode->size;
        }

        delete searchNode;

        if(originalColor==BLACK)
                RBRemoveFixup(x);

        return true;
}

작은 키 찾기:

//   i    ：
template<class Type>
const Type& orderStatisticTree<Type>::select(int i) const
{
        node* currentNode=root;
        int rank=currentNode->left->size+1;
        while(rank!=i){
                if(i<rank)
                        currentNode=currentNode->left;
                else{
                        currentNode=currentNode->right;
                        i=i-rank;
                }

                rank=currentNode->left->size+1;
        }

        return currentNode->key;
}

원소 의 순 서 를 되 돌려 줍 니 다:

template<class Type>
int orderStatisticTree<Type>::rank(const Type& val) const
{
        node* searchNode=search(val,root);

        if(searchNode==nullNode)
                throw runtime_error("the element is not existent in the tree.");

        int rank=searchNode->left->size+1;
        node* currentNode=searchNode;
        while(currentNode!=root){
                if(currentNode==currentNode->parent->right)
                        rank+=currentNode->parent->left->size+1;
                currentNode=currentNode->parent;
        }

        return rank;
}