[데이터 구조] 범 호 강 Treap (비 회전 평형 트 리) & 지속 가능 한 Treap 정리
이것 은 매우 신기 한 데이터 구조 이다.또 이런 데이터 구 조 는 쓰기 쉽다.
쉽게 말 하면 이런 treap 은 두 가지 조작 을 바탕 으로 한다.
Merge (int x, int y) -> x 의 하위 트 리 와 y 의 하위 트 리 를 합 쳐 x 를 만족 시 키 는 하위 트 리 의 최대 치 는 y 하위 트 리 의 최소 치 보다 작 고 복잡 도 O (logN) Split (int x, int k) -> x 의 최소 k 개 값/k 와 같은 값 을 다른 부분 과 분리 합 니 다. 복잡 도 O (logN)
먼저 Merge 작업: 이미 알 고 있 는 x 의 서브 트 리 의 최대 치 는 y 서브 트 리 의 최소 치보다 작 기 때문에 반드시 y 가 x 의 오른쪽 아들 노드 에 연결 되 거나 x 가 y 의 왼쪽 아들 노드 (상세 한 코드 참조) 에 연결 되 어 깊이 를 최대한 작 게 하기 위해 우 리 는 무 작위 수 를 사용 하여 x 를 y 의 아들 로 판단 하거나 y 를 x 의 아들 로 판단 한다.
int Merge(int x,int y){
if(x==0) return y;
if(y==0) return x;
if(Tree[x].fix<Tree[y].fix){
Tree[x].ch[1]=Merge(Tree[x].ch[1],y);// y x
update(x);
return x;
}
else{
Tree[y].ch[0]=Merge(x,Tree[y].ch[0]);// x y
update(y);
return y;
}
}
다음은 Split 작업 (두 가지 다른 Split 방식 이 있 습 니 다. 제목 에 따라 스스로 적당 한 하 나 를 선택 할 수 있 습 니 다) 먼저 우 리 는 이 나 무 를 두 부분 으로 나 누 어야 합 니 다. 아래 코드 에서 first 는 앞부분 이 고 second 는 후반 부분 입 니 다.
pair<int,int> Split(int x,int k){
if(x==0) return make_pair(0,0);
pair<int,int> y;
if(Tree[x].key<=k){// k
y=Split(Tree[x].ch[1],k);//x k ， x ，
Tree[x].ch[1]=y.first;// x x ，
update(x);
y.first=x;
}
else{//
y=Split(Tree[x].ch[0],k);
Tree[x].ch[0]=y.second;
update(x);
y.second=x;
}
return y;
}
두 번 째:
pair<int,int> Split(int x,int k){
if(x==0) return make_pair(0,0);
pair<int,int> y;
if(Tree[Tree[x].ch[0]].sum<k){// k （ k ）
y=Split(Tree[x].ch[1],k);
Tree[x].ch[1]=y.first;
update(x);
y.first=x;
}
else{
y=Split(Tree[x].ch[0],k);
Tree[x].ch[0]=y.second;
update(x);
y.second=x;
}
return y;
}
이제 이 두 가지 조작 을 바탕 으로 우 리 는 균형 트 리 를 쓸 수 있 습 니 다. (쓰기 쉽 지 않 습 니까?!) 그러면 먼저 삽입 작업 입 니 다.
void Insert(int val){
pair<int,int> x=Split(root,val);
Tree[++ncnt]=node(val);//
Tree[ncnt].ch[0]=0;
Tree[ncnt].ch[1]=0;
root=Merge(Merge(x.first,ncnt),x.second);
}
쉽 죠?
그 다음 삭제 작업:
void Del(int val){
pair<int,int> x=Split(root,val);
pair<int,int> y=Split(x.first,val-1);
y.second=Merge(Tree[y.second].ch[0],Tree[y.second].ch[1]);
root=Merge(Merge(y.first,y.second),x.second);
}
쉽 죠?
하나 더: 밸 런 스 트 리 의 k 작은 수 를 구하 세 요.
int find_id(int x,int k){
if(x==0)
return 0;
int ch0=Tree[x].ch[0];
if(Tree[ch0].sum>=k)
return find_id(ch0,k);
if(Tree[ch0].sum+1>=k)
return Tree[x].key;
return find_id(Tree[x].ch[1],k-Tree[ch0].sum-1);
}
어?사실 이 건 보통 밸 런 스 트 리 와 다 르 지 않 은 것 같 아...
밸 런 스 트 리 에서 val 의 순 위 를 구 합 니 다. (이 값 은 트 리 에 없 을 수 있 습 니 다)
int get_kth(int k){
// Split k ， int k1=find_id(root,k); k-1 k1
pair<int,int> x=Split(root,k-1);// Split k
int ans=Tree[x.first].sum+1;
root=Merge(x.first,x.second);
return ans;
}
쉽 지 않 아 요??한 마디 로 하면, 이것 은 상당히 쓰기 좋 은 밸 런 스 트 리 입 니 다. 아직 익숙 하지 않 으 면, cqoi 의 일반 밸 런 스 트 리 를 몇 번 더 만 들 수 있 습 니 다.
지속 가능 한 Treap
사실, 만약 당신 이 다른 지속 가능 한 데이터 구 조 를 배 웠 다 면, 이 부분 은 매우 간단 할 것 입 니 다.
사실 주석 트 리 와 마찬가지 로 우 리 는 n 개의 루트 노드 만 사용 하고 삽입 할 때마다 경로 의 모든 노드 를 복사 하면 됩 니 다. 이것 은 지속 가능 한 Split 입 니 다.
pair<int,int> Split(int x,int k){
if(x==0)
return make_pair(0,0);
int newone;
pair<int,int> y;
if(Tree[x].key<=k){
newone=++ncnt;
Tree[newone]=Tree[x];
y=Split(Tree[newone].ch[1],k);
Tree[newone].ch[1]=y.first;
update(newone);
y.first=newone;
}
else{
newone=++ncnt;
Tree[newone]=Tree[x];
y=Split(Tree[newone].ch[0],k);
Tree[newone].ch[0]=y.second;
update(newone);
y.second=newone;
}
return y;
}
그러나 가끔 Merge 작업 은 새로운 노드 를 복사 할 필요 가 없습니다. 이 유 는 간단 합 니 다. 만약 에 Merge 의 두 개의 키 트 리 가 같은 시간 버 전에 있다 면 새로운 노드 를 복사 할 필요 가 없습니다.
int Merge(int x,int y){
if(x==0) return y;
if(y==0) return x;
if(Tree[x].fix<Tree[y].fix){
Tree[x].ch[1]=Merge(Tree[x].ch[1],y);
update(x);
return x;
}
else{
Tree[y].ch[0]=Merge(x,Tree[y].ch[0]);
update(y);
return y;
}
}
예제: 로 곡 3835 일반 지구 화 밸 런 스 트 리
#include
",find_kth(i,x)-1);
if(tag==4)
PF("%d
",get_kth(root[i],x+1));
if(tag==5)
PF("%d
",get_pre(i,x));
if(tag==6)
PF("%d
",get_bac(i,x));
}
}
지침 판
#include
",y.first->sum);
root[i]=Merge(y.first,y.second);
}
if(tag==4){
x++;
PF("%d
",find_kth(root[i],x)->val);
}
if(tag==5){
PNN y=Split(root[i],x-1);
PF("%d
",find_nxt(y.first,1)->val);
root[i]=Merge(y.first,y.second);
}
if(tag==6){
PNN y=Split(root[i],x);
PF("%d
",find_nxt(y.second,0)->val);
root[i]=Merge(y.first,y.second);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 기본 사용법 요약 (2)StringBuilder 또는 StringBuffer를 사용할 때 append () 방법으로 텍스트를 추가하고 toString () 방법으로 연결된 전체 텍스트를 가져올 수 있습니다 3. Iterator를 사용합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
