제1 4 장 데이터 구조 확장 구간 트 리 부분 코드

37711 단어 데이터 구조

구간 류 정 의 를 내 렸 다. 구간 나무 류 의 결점 구조, 좌회전, 우회전, 삽입 으로 인 한 붉 은 검 은 나무 성질 파 괴 를 회복 하고 삽입, 삭제 로 인 한 붉 은 검 은 나무 성질 파 괴 를 회복 하고 삭제 하 며 중첩 구간 을 찾 아 중첩 구간 을 찾 지만 최소 저 점 을 찾 아 중첩 구간 을 찾 지만 최대 저 점 을 찾 는 일련의 조작 코드 를 내 렸 다.
구간 클래스 정의:

class interval{
public:
        interval(const int& l=int(),const int& h=int()):lowEndPoint(l),highEndPoint(h){}
        friend bool operator<(const interval&,const interval&);//         
        friend class intervalTree;//         ，    interval        。 
private:
        int lowEndPoint;
        int highEndPoint;
};
inline bool operator< (const interval& lhs,const interval& rhs) { return lhs.lowEndPoint<rhs.lowEndPoint; }//

결점 구조:

struct node{
                interval element;
                node* parent;
                node* left;
                node* right;
                int color;
                int maxEndPoint;//    （      ）           。
                node(const interval& e=interval(),node* p=0,node* l=0,node* r=0,int c=BLACK,int m=INT_MIN):element(e),parent(p),left(l),right(r),color(c),maxEndPoint(m){}
        };

왼쪽 회전:

void intervalTree::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;
//          ，        maxEndPoint         。
        x->maxEndPoint=maximum(x->element.highEndPoint,x->left->maxEndPoint,x->right->maxEndPoint);
        y->maxEndPoint=maximum(y->element.highEndPoint,y->left->maxEndPoint,y->right->maxEndPoint);
}

오른쪽 회전:

void intervalTree::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;
//          ，        maxEndPoint         。
        x->maxEndPoint=maximum(x->element.highEndPoint,x->left->maxEndPoint,x->right->maxEndPoint);
        y->maxEndPoint=maximum(y->element.highEndPoint,y->left->maxEndPoint,y->right->maxEndPoint);
}

삽입 으로 인 한 붉 은 검 은 나무 성질 파괴 복구:

void intervalTree::RBInsertFixup(node* currentNode)
{
        node* tmp=currentNode->parent;
        while(tmp!=nullNode){
                tmp->maxEndPoint=maximum(tmp->element.highEndPoint,tmp->left->maxEndPoint,tmp->right->maxEndPoint);
                tmp=tmp->parent;
        }//  currentNode            maxEndPoint       

        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);
                                         leftRotate(currentNode->parent->parent);
                        }
                }
        }
        root->color=BLACK;
}

삽입:

//            ;
void intervalTree::insert(const interval& val)
{
        node* prevNode=nullNode;
        node* currentNode=root;

        while(currentNode!=nullNode){
                prevNode=currentNode;
                if(val<currentNode->element)
                        currentNode=currentNode->left;
                else
                        currentNode=currentNode->right;
        }

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

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

 node* tmp=currentNode->parent;
        while(tmp!=nullNode){
                tmp->maxEndPoint=maximum(tmp->element.highEndPoint,tmp->left->maxEndPoint,tmp->right->maxEndPoint);
                tmp=tmp->parent;
        }//  currentNode            maxEndPoint       


        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;
}

삭제:

//            
bool intervalTree::remove(const interval& val)
{
        node* searchNode=search(val,root);
        if(searchNode==nullNode)
                return false;

        node* nextNode=0;
        int originalColor;

        if(searchNode->left==nullNode){
                nextNode=searchNode->right;
                originalColor=searchNode->color;
                transplant(searchNode,searchNode->right);
        }
        else if(searchNode->right==nullNode){
                nextNode=searchNode->left;
                originalColor=searchNode->color;
                transplant(searchNode,searchNode->left);
        }
        else{
                node* succNode=findMin(searchNode->right);
                nextNode=succNode->right;
                originalColor=succNode->color;

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

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

        delete searchNode;
        return true;
}

중첩 구간 찾기:

bool intervalTree::isOverlap(const interval& lhs,const interval& rhs) const
{
        return !(lhs.highEndPoint<rhs.lowEndPoint||rhs.highEndPoint<lhs.lowEndPoint);
}
//            
void intervalTree:: searchOverlap(const interval& val) const
{
        node* currentNode=root;

        while(currentNode!=nullNode&&!isOverlap(currentNode->element,val)){
                if(currentNode!=nullNode&&val.lowEndPoint<=currentNode->left->maxEndPoint)
                        currentNode=currentNode->left;
                else
                        currentNode=currentNode->right;
        }

        if(currentNode==nullNode)
                throw runtime_error("the overlappint intervals are not existent.");

        cout<<"lowEndPoint: "<<currentNode->element.lowEndPoint<<"\t"<<"highEndPoint: "<<currentNode->element.highEndPoint<<endl;
}

중첩 구간 을 찾 지만 최소 저 점 이 있 습 니 다:

intervalTree::node* intervalTree::lessLowEndPointOverlap(const interval& val,node* rootNode) const
{
        if(rootNode==nullNode)
                return nullNode;

        if(rootNode->left!=nullNode&&val.lowEndPoint<=rootNode->left->maxEndPoint){
                node* tmp=lessLowEndPointOverlap(val,rootNode->left);
                if(tmp!=nullNode)
                        return tmp;
                else if(isOverlap(val,rootNode->element))
                        return rootNode;
                else return nullNode;
        }
        else if(isOverlap(val,rootNode->element))
                return rootNode;
        else
                return lessLowEndPointOverlap(val,rootNode->right);
}

void intervalTree::lessLowEndPointOverlap(const interval& val) const
{
        node* tmp=lessLowEndPointOverlap(val,root);

        if(tmp==nullNode)
                throw runtime_error("there are not overlapping intervals");

        cout<<"lowEndPoint: "<<tmp->element.lowEndPoint<<"\t"<<"highEndPoint: "<<tmp->element.highEndPoint<<endl;
}

중첩 구간 을 찾 지만 최대 저 점 이 있 습 니 다:

intervalTree::node* intervalTree::largestLowEndPointOverlap(const interval& val,node* rootNode) const
{
        if(rootNode==nullNode)
                return nullNode;

        if(rootNode->right!=nullNode&&val.lowEndPoint<=rootNode->right->maxEndPoint){
                node* tmp=largestLowEndPointOverlap(val,rootNode->right);

                if(tmp!=nullNode)
                        return tmp;
                else if(isOverlap(val,rootNode->element))
                        return rootNode;
                else
                        return largestLowEndPointOverlap(val,rootNode->left);
        }
        else if(isOverlap(val,rootNode->element))
                return rootNode;
        else
                return largestLowEndPointOverlap(val,rootNode->right);
}

void intervalTree::largestLowEndPointOverlap(const interval& val) const
{
        node* tmp=largestLowEndPointOverlap(val,root);

        if(tmp==nullNode)
                throw runtime_error("there are not overlapping intervals");

        cout<<"lowEndPoint: "<<tmp->element.lowEndPoint<<"\t"<<"highEndPoint: "<<tmp->element.highEndPoint<<endl;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

정수 반전

Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조선형 표순서 대기 행렬순환 대기 행렬체인 큐

어셈블리 언어 - Esc별로 색상 변경

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다