SBT 노트 와 템 플 릿

1. SBT 가 균형 을 유지 하 는 방식 으로 SBT 는 size 를 유지 하여 균형 을 유지 합 니 다.r 를 뿌리 로 하 는 서브 트 리 에 대해 SBT 는 다음 과 같은 성질 을 만족 시 켜 야 한다. 1. r 의 왼쪽 아들 의 size 는 r 의 오른쪽 아들 의 좌우 아들 의 size 2. r 의 오른쪽 아들 의 size 는 r 의 왼쪽 아들 의 좌우 아들 의 size SBT 유지 크기 보다 간단 하 다. 즉, 삽입 + size, 삭제 – size 유지 균형 은 maintain 함수 에 의존한다.구체 적 으로 논문 을 보다.AVL 과 비슷 한 점 을 쓰 고 싶 습 니 다.우선 maintain 함 수 를 드 리 겠 습 니 다.

void maintain(int &r,bool flag)
{
    if(!flag)
    {
        if(tree[tree[r].rc].sz<tree[tree[tree[r].lc].lc].sz)zig(r);
        else if(tree[tree[r].rc].sz<tree[tree[tree[r].lc].rc].sz)zagzig(r);
        else return;
    }
    else
    {
        if(tree[tree[r].lc].sz<tree[tree[tree[r].rc].rc].sz)zag(r);
        else if(tree[tree[r].lc].sz<tree[tree[tree[r].rc].lc].sz)zigzag(r);
        else return;
    }
    maintain(tree[r].lc,0);
    maintain(tree[r].rc,1);
    maintain(r,0);
    maintain(r,1);
}

그리고 AVL 의 maintain 은 이렇게 생 겼 습 니 다.

void maintain(int &r)
{
    if(tree[tree[r].lc].h==tree[tree[r].rc].h+2)
    {
        int t=tree[r].lc;
        if(tree[tree[t].lc].h==tree[tree[r].rc].h+1)r=zig(r);
        else if(tree[tree[t].rc].h==tree[tree[r].rc].h+1)r=zagzig(r);
    }
    else if(tree[tree[r].rc].h==tree[tree[r].lc].h+2)
    {
        int t=tree[r].rc;
        if(tree[tree[t].rc].h==tree[tree[r].lc].h+1)r=zag(r);
        else if(tree[tree[t].lc].h==tree[tree[r].lc].h+1)r=zigzag(r);
    }
    tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+1;
}

발견 할 수 있 는 것 은 1. AVL 과 SBT 는 모두 회전 이 있 고 한 번 의 회전 과 두 번 의 회전 이 있 지만 판단 조건 은 h 에서 size 2. AVL 로 현재 의 r 만 유지 하고 SBT 는 여러 번 유지 해 야 한다. 비록 O (1) 의 3. SBT 의 maintain 은 왼쪽 이 든 오른쪽 이 든 왼쪽 이 0 이 고 오른쪽 이 1 이다.그렇다면 기억 에 있어 서 SBT 는 여러 번 (뿌리 좌우 모두 maintain, 왼쪽 아들 은 왼쪽, 오른쪽 아들 오른쪽 만 유지) 해 야 한 다 는 것 만 기억 하고 SBT 의 회전 판단 조건 도 있다.왼쪽 아들 의 왼쪽 아들 이 오른쪽 아들 보다 크 면 우회전 한다.왼쪽 아들 의 오른쪽 아들 이 오른쪽 아들 보다 크 면 먼저 왼쪽으로 돌 고 오른쪽으로 돌 면 이것 은 AVL 의 저것 과 매우 유사 하 다.
2. insert 는 이 진 트 리 를 찾 는 insert 입 니 다. 게다가 size 를 유지 하고 마지막 에 maintain 이 있 습 니 다.

void insert(int &r,int x)
{
    if(r==0)
    {
        tree[++cnt].sz=1;
        tree[cnt].v=x;
        r=cnt;
        return;
    }
    ++tree[r].sz;
    if(x<tree[r].v)insert(tree[r].lc,x);
    else insert(tree[r].rc,x);
    maintain(r,x>=tree[r].v);
}

3. del 은 이 진 트 리 를 찾 는 del 이 고 유지 size 입 니 다.유지 하지 않 고 오히려 빨리 해 야 한다.이곳 은 유지 하지 않 고 마음대로 지 워 도 나무의 높이 는 변 하지 않 기 때문에 이 진 트 리 를 찾 는 성질 이 변 하지 않 고 시간 복잡 도 는 적어도 증가 하지 않 으 며 유지 하지 않 으 면 오히려 상수 시간 을 절약 할 수 있 기 때문이다.

int del(int &r,int x)
{
    int res;
    --tree[r].sz;
    if(tree[r].v==x||(x<tree[r].v&&tree[r].lc==0)||(x>tree[r].v&&tree[r].rc==0))
    {
        res=tree[r].v;
        if(0==tree[r].lc||0==tree[r].rc)r=tree[r].lc+tree[r].rc;
        else tree[r].v=del(tree[r].lc,x);
    }
    else
    {
        if(x<tree[r].v)res=del(tree[r].lc,x);
        else res=del(tree[r].rc,x);
    }
    return res;
}

4. SBT 를 중시 할 수 있 습 니 다. 사실 위 에 있 는 insert 는 SBT 를 중시 할 수 있 는 실현 입 니 다.SBT 로 하여 금 두 가지 생각 을 다시 하 게 하 다.1. tot 도 메 인 을 추가 하고 이 노드 가 몇 번 삽입 되 었 는 지 기록 합 니 다.그리고 많은 부분 을 수정 해 야 합 니 다. 예 를 들 어 삽입 할 때 r! =0 은 3 가지 상황 으로 나 누 어 tree [r]. v > x 는 왼쪽 하위 트 리, tree [r]. v < x 는 오른쪽 하위 트 리, tree [r]. v = = x 는 tree [r]. tot + + 그리고 del 일 때 이 점 의 tot 값 > 1 이면 바로 tot, tot = = 1 이면 점 을 삭제 합 니 다.그리고 del 은 2 원 그룹 으로 돌아 가 tot 와 v 를 기록 해 야 합 니 다.순 위 를 구하 자 면 K 가 컸 을 때 도 수정 이 있 었 다.선구자 후 계 는 수정 할 필요 가 없다.어쨌든 실현 은 비교적 번거롭다.

int kth(int r,int k)
{
    if(k>=tree[tree[r].rc].sz+1&&k<=tree[tree[r].rc].sz+tree[r].tot)return tree[r].v;
    if(k<1+tree[tree[r].rc].sz)return kth(tree[r].rc,k);
    else return kth(tree[r].lc,k-tree[r].tot-tree[tree[r].rc].sz);
}

그 다음 에 아버 지 를 더 괴 롭 히 는 것 이 바로 size 의 이의 성 이다. SBT 의 size 는 노드 의 개수 이 고 k 가 큰 size 는 삽 입 된 몇 개의 수 이 며 SBT 를 중시 하 는 것 은 다르다.따로 지 켜 야 합 니 다.하지만 유지 하지 않 아 도 될 것 같 습 니 다. 특별한 균형 이 아 닙 니까?2. 같은 값 을 다른 값 으로 삽입 하면 위의 insert 입 니 다. x = = tree [r]. v 가 있 으 면 x 를 오른쪽 트 리 에 삽입 합 니 다 (물론 왼쪽 트 리 도 가능 합 니 다).이 때 이 진 트 리 의 의 미 를 찾 는 데 변화 가 생 겼 습 니 다. 이 나무의 중간 순 서 는 점점 늘 어 나 는 것 이 아니 라 줄 어 들 지 않 습 니 다.이렇게 쓰 면 tot 도 메 인 을 추가 로 열지 않 아 도 되 고, 2 개의 의미 가 다른 size 를 유지 하지 않 아 도 됩 니 다.insert 와 delete 도 별로 고 칠 필요 가 없습니다.그러나 이렇게 쓰 려 면 선구자 가 k 대 와 rank 에 이 어 어느 쪽으로 돌아 가 는 지 잘 고려 해 야 한다.구체 적 으로 코드 를 보 세 요.일반 밸 런 스 트 리 코드:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node{
    int lc,rc,sz,v;
}tree[500010];
int n,op,x,pred,succ,cnt,rt;
char c;
inline void GET(int &n)
{
    n=0;
    int f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    while(c<='9'&&c>='0'){n=n*10+c-'0';c=getchar();}
    n*=f;
}
inline void zig(int &r)
{
    int t=tree[r].lc;
    tree[r].lc=tree[t].rc;
    tree[t].rc=r;
    tree[r].sz=tree[tree[r].lc].sz+tree[tree[r].rc].sz+1;
    tree[t].sz=tree[tree[t].lc].sz+tree[tree[t].rc].sz+1;
    r=t;
}
inline void zag(int &r)
{
    int t=tree[r].rc;
    tree[r].rc=tree[t].lc;
    tree[t].lc=r;
    tree[r].sz=tree[tree[r].lc].sz+tree[tree[r].rc].sz+1;
    tree[t].sz=tree[tree[t].lc].sz+tree[tree[t].rc].sz+1;
    r=t;
}
inline void zigzag(int &r)
{
    zig(tree[r].rc);
    zag(r);
}
inline void zagzig(int &r)
{
    zag(tree[r].lc);
    zig(r);
}
inline void maintain(int &r,bool flag)
{
    if(!flag)
    {
        if(tree[tree[r].rc].sz<tree[tree[tree[r].lc].lc].sz)zig(r);
        else if(tree[tree[r].rc].sz<tree[tree[tree[r].lc].rc].sz)zagzig(r);
        else return;
    }
    else
    {
        if(tree[tree[r].lc].sz<tree[tree[tree[r].rc].rc].sz)zag(r);
        else if(tree[tree[r].lc].sz<tree[tree[tree[r].rc].lc].sz)zigzag(r);
        else return;
    }
    maintain(tree[r].lc,0);
    maintain(tree[r].rc,1);
    maintain(r,0);
    maintain(r,1);
}
void insert(int &r,int x)
{
    if(r==0)
    {
        tree[++cnt].sz=1;
        tree[cnt].v=x;
        r=cnt;
        return;
    }
    ++tree[r].sz;
    if(x<tree[r].v)insert(tree[r].lc,x);
    else insert(tree[r].rc,x);
    maintain(r,x>=tree[r].v);
}
int del(int &r,int x)
{
    int res;
    --tree[r].sz;
    if(tree[r].v==x||(x<tree[r].v&&tree[r].lc==0)||(x>tree[r].v&&tree[r].rc==0))
    {
        res=tree[r].v;
        if(0==tree[r].lc||0==tree[r].rc)r=tree[r].lc+tree[r].rc;
        else tree[r].v=del(tree[r].lc,x);
    }
    else
    {
        if(x<tree[r].v)res=del(tree[r].lc,x);
        else res=del(tree[r].rc,x);
    }
    return res;
}
void predecessor(int r,int x)
{
    if(r==0)return;
    if(x<=tree[r].v)predecessor(tree[r].lc,x);
    else
    {
        if(x!=tree[r].v)pred=tree[r].v;
        predecessor(tree[r].rc,x);
    }
}
void successor(int r,int x)
{
    if(r==0)return;
    if(x<tree[r].v)
    {
        if(x!=tree[r].v)succ=tree[r].v;
        successor(tree[r].lc,x);
    }
    else successor(tree[r].rc,x);
}
int kth(int r,int x)
{
    if(x==tree[tree[r].lc].sz+1)return tree[r].v;
    if(x<tree[tree[r].lc].sz+1)return kth(tree[r].lc,x);
    return kth(tree[r].rc,x-tree[tree[r].lc].sz-1);
}
int rnk(int r,int x)
//      x   , 1 1 1 2 2 3 3,rnk(rt,2)=4
{
    if(r==0)return 1;
    if(x<=tree[r].v)return rnk(tree[r].lc,x);
    return rnk(tree[r].rc,x)+tree[tree[r].lc].sz+1;
}
int main()
{
    GET(n);
    while(n--)
    {
        GET(op);GET(x);
        if(op==1)insert(rt,x);
        else if(op==2)del(rt,x);
        else if(op==3)printf("%d
",rnk(rt,x));
        else if(op==4)printf("%d
",kth(rt,x));
        else if(op==5){predecessor(rt,x);printf("%d
",pred);}
        else if(op==6){successor(rt,x);printf("%d
",succ);}
    }
}