替罪羊树学习笔记

(Updated: )
OI
views
Word count: 1.3k (~6 mins to read) Last updated:

博客咕咕咕了好久……最近会逐步继续恢复更新博客的。
最近又在学习二叉搜索树。实测发现替罪羊树快的飞起(时间约Splay的1/2)~写起来还比较简单，决定来一波。
（那为什么还要用Splay呢？因为Splay是序列之王！还能维护LCT！（你要用非旋Treap（FHQ-Treap）我也没意见））
替罪羊树的主要思想就是当出现重量失衡的时候，把罪魁祸首的那个子树拎出来，重新按最完美的方式（也就是近似完全二叉树）构造一遍再接回去。
如何定义某个子树不平衡：当这个子树的左右子树其中之一的“重量”（节点个数）超过了整个子树的α*100%时，我们认为这个子树不平衡。
举例：α=0.75时，如果一个子树左子树有4个节点，右子树有1个，这个子树大小就是4+1+1=6，左子树占比超过了α*100%（即75%），这个子树不平衡，需要重构。
显然，α取值介于0.5至1.0之间，越小树越平衡但重构次数越多，越大重构次数越少但树越不平衡。太大太小都会出事。一般而言，α取0.75。如果题目查询次数远大于插入次数，可略微降低α取值（比如α=0.70）；若远小于，则略升高（如α=0.80）。
下面以洛谷3369【模板】普通平衡树为例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//这个板子有改进之处：比如删除节点可以打上删除懒标记，单个节点可以记录同一数字数量避免多余节点。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define inf (1<<30)
#define maxn (2100000)
#define db double
#define il inline
#define RG register
using namespace std;

const db al=0.75;//α
struct node {
    int son[2],fa,size,num;//左右孩子储存地址，节点父亲，以该节点为根子树的重量，该节点储存的数字
} t[maxn];
int n,cnt,root;

il bool balance(RG int id)   //判断子树是否平衡
{
    return (db)(t[id].size*al>=(db)t[ t[id].son[0] ].size) && (db)( t[id].size*al>=(db)t[t[ id].son[1] ].size);
}
int cur[maxn],sum;

il void recycle(RG int id)    //压扁，把需要重构的子树拎出来先拍扁成序列
{
    if(t[id].son[0]) recycle(t[id].son[0]);
    cur[++sum]=id;
    if(t[id].son[1]) recycle(t[id].son[1]);
}

il int build(RG int l,RG int r)   //递归建树，使结构最优
{
    if(l>r) return 0;
    RG int mid=(l+r)>>1,id=cur[mid];
    t[ t[id].son[0]=build(l,mid-1) ].fa=id;
    t[ t[id].son[1]=build(mid+1,r) ].fa=id;
    t[id].size=t[ t[id].son[0] ].size+t[ t[id].son[1] ].size+1;
    return id;
}

il void rebuild(RG int id)   //重构子树，再“接回去”
{
    sum=0;
    recycle(id);
    RG int fa=t[id].fa,Son=( t[ t[id].fa ].son[1]==id );
    RG int cur=build(1,sum);
    t[ t[fa].son[Son]=cur ].fa=fa;
    if(id==root) root=cur;
}

il void insert(RG int x)//插入一个数字x
{
    RG int now=root,cur=++cnt;
    t[cur].size=1,t[cur].num=x;
    while(1) { //找到适合位置插入
        t[now].size++;
        RG bool Son=(x>=t[now].num);
        if( t[now].son[Son] ) now=t[now].son[Son];
        else {
            t[ t[now].son[Son]=cur ].fa=now;
            break;
        }
    }
    RG int flag=0;
    for(RG int i=cur; i; i=t[i].fa) if(!balance(i)) flag=i;//注意：重建时取深度最浅的，以避免小子树重构完大子树还重构，浪费时间
    if(flag) rebuild(flag); //插入往往会导致不平衡,这时需要重建不平衡的子树即可
}

il int get_num(RG int x)   //查询 x 在树中的节点编号（在数组中储存位置下标）
{
    RG int now=root;
    while(1) {
        if(t[now].num==x) return now;
        else now=t[now].son[ t[now].num<x ];
    }
}

il void erase(RG int id)   //删除
{
    if(t[id].son[0] && t[id].son[1]) {
        RG int cur=t[id].son[0];
        while(t[cur].son[1]) cur=t[cur].son[1];
        t[id].num=t[cur].num;
        id=cur;
    } //删除操作需要找到左子树的最后一个节点或右子树的第一个节点来顶替,优先找左子树
    RG int Son=(t[id].son[0]) ? t[id].son[0]:t[id].son[1];
    RG int k=( t[ t[id].fa ].son[1]==id );
    t[ t[ t[id].fa ].son[k]=Son ].fa=t[id].fa;
    for(RG int i=t[id].fa; i; i=t[i].fa) t[i].size--;
    if(id==root) root=Son;
}

il int get_rank(RG int x)   //查 x 的排名
{
    RG int now=root,ans=0;
    while(now) {
        if(t[now].num<x) ans+=t[ t[now].son[0] ].size+1,now=t[now].son[1];
        else now=t[now].son[0];
    }
    return ans;
}

il int get_kth(RG int x)   //查树中的第 k 个数
{
    RG int now=root;
    while(1) {
        if(t[ t[now].son[0] ].size==x-1) return now;
        else if(t[ t[now].son[0] ].size>=x) now=t[now].son[0];
        else x-=t[ t[now].son[0] ].size+1,now=t[now].son[1];
    }
    return now;
}
int main()
{
    cnt=2,root=1;
    t[1].num=-inf,t[1].size=2,t[1].son[1]=2;
    t[2].num=inf,t[2].size=1,t[2].fa=1;
    scanf("%d",&n);
    RG int type,x;
    for(RG int i=1; i<=n; i++) {
        scanf("%d%d",&type,&x);
        if(type==1) insert(x);
        else if(type==2) erase( get_num(x) );
        else if(type==3) printf("%d\n",get_rank(x));
        else if(type==4) printf("%d\n",t[ get_kth(x+1) ].num);
        else if(type==5) printf("%d\n",t[get_kth(get_rank(x))].num);
        else if(type==6) printf("%d\n",t[get_kth(get_rank(x+1)+1)].num);//注意此处 
    }
    return 0;
}