替罪羊树

替罪羊树

$\alpha$权重平衡

  1. 认为一棵树$X$是平衡的当且仅当它每一棵子树满足下列条件：

    $size(x.left) \le \alpha * size(x)$

    $size(x.right)\le \alpha * size(x)$

    $\alpha \in [0.5,1]$

    • $\alpha = 1$就是普通的二叉搜索树
    • $\alpha = 0.5$ 左右子树的大小是该数的一半
  1. 替罪羊树是平衡树的一种,但维护平衡的方式不是 旋转,而是重新建树,且重构成 左右子树大小相等的二叉搜索树
  2. 人为设定$\alpha$的值

重建(*)

  • （形象理解为将一棵树拍平, 拍平成一个数组),

  1. 将子树通过$dfs$中序遍历（数列顺序不变）存到数组（ 然后通过此数组重新建立子树）

  2. 左右递归建树（）

插入 (如何维护平衡)

  • 向下搜索找到对应位置插入,在回溯的过程中,判断每一节点是否需要满足平衡,一条树链上可能会有多个子树需要重构,则找到最接近根节点(最高)的子树重建

    1. 当前节点不平衡,记录该节点,当回到上一层节点再判断,如果上一层节点代表的子树仍不平衡,记录更新
    2. 当前节点代表的子树平衡,则判断记录是否有值,（且一定为左右子树的编号,)然后重构子树
    3. 每一次回溯都判断整棵树是否需要重构,避免(只有局部平衡)

  • 偷懒做法:

    每个节点判断后,如果需要重构就直接重构,

    去掉if(isbad(now)) ... else {}, 改为if(isbad(now)) rebuild(now)

删除

  • 给节点打标记,但是每次都检查,如果被删除（标记）的点过多,则重构整个树

    if((double)e[root].total*alpha > e[root].valid) rebuild(root);

数组下标分配问题,

  • 伪内存池 (不用的下标\编号回收)

其他的操作都和其他平衡树大同小异

Luogu 平衡树例题

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
const double alpha = 0.75;

struct scapegoat {
    int son[2],val,valid,total;
    bool exist;
} e[maxn];
int memory[maxn],cur[maxn];
int root,pool,poi,to_rebuild;

bool isbad(int now) {
    int left  = e[now].son[0];
    int right = e[now].son[1];
    if ((double)e[now].valid*alpha <= (double)max(e[left].valid,e[right].valid))
        return true;
    return false;
}

void dfs(int now) {
    if (!now) return ;
    dfs(e[now].son[0]);
    if (e[now].exist)
        cur[++poi] = now;
    else
        memory[++pool] = now;
    dfs(e[now].son[1]);
}

void build(int l,int r,int &now) {
    int mid=(l+r)>>1;
    now = cur[mid];
    if (l==r) {
        e[now].son[0] = e[now].son[1] = 0;
        e[now].total = e[now].valid = 1;
        return ;
    }
    if (l <= mid-1)
        build(l,mid-1,e[now].son[0]);
    else
        e[now].son[0] = 0;
    build(mid+1,r,e[now].son[1]);
    // 回溯时判断是否重建
    int left=e[now].son[0],right=e[now].son[1];
    e[now].total = e[left].total + e[right].total + 1;
    e[now].valid = e[left].valid + e[right].valid + 1;
}

void rebuild(int &now) { // 以now为根节点,重建
    poi = 0;
    dfs(now); // 从Now节点出发,把子树拍平
    if (poi) build(1,poi,now);
    else now = 0; //没有重建的返回 赋值为0
}

void insert(int &now,int val) {
    if (!now) {
        now = memory[pool--];
        e[now].val = val;
        e[now].exist = e[now].total = e[now].valid = 1;
        e[now].son[0] = e[now].son[1] = 0;
        return ;
    }
    // 沿路向下更新
    e[now].total++,e[now].valid++;
    if (val <= e[now].val) insert(e[now].son[0],val);
    else insert(e[now].son[1],val);
    // if(isbad(now)) rebuild(now);
    // 下面的都可以注释掉,改为每层不满足直接重构,而不去找离根节点最近的
    // 回溯时 判断是否重建
    if (!isbad(now)) { // now节点不需要重建
        if (to_rebuild) { // 子树中有节点需要重建
            if (e[now].son[0] == to_rebuild)
                rebuild(e[now].son[0]);
            else
                rebuild(e[now].son[1]);
            // 取消to_rebuild标记
            to_rebuild = 0;
        }
    } else
        to_rebuild = now;
    // 插入的每一层都判断 整个树是否需要重建
    if (isbad(root))
        rebuild(root);
}

void delete_pos(int &now,int tar) { // 删除排名为tar的值
    int left=e[now].son[0],right=e[now].son[1];
    if (e[now].exist && e[left].valid+1 == tar) { // 子树+1(本节点) == tar
        e[now].exist = 0;
        e[now].valid--;
        return ;
    }
    // 把路径上的点的valid都更新
    e[now].valid--;
    // 判断是否还是在 左边部分
    if (tar <= e[left].valid + e[now].exist)
        delete_pos(e[now].son[0],tar);
    else
        delete_pos(e[now].son[1],tar-e[left].valid-e[now].exist);
}

int find_kth(int k) { // 给出排名k找值
    int now = root;
    while (now) {
        int left=e[now].son[0],right=e[now].son[1];
        if (e[now].exist && e[left].valid+1 == k) // 是不是now节点代表的值
            return e[now].val;
        else if (k <= e[left].valid) // 是不是在左子树中
            now = left;
        else {
            k -= e[left].valid + e[now].exist; // 减去当前点和左子树大小
            now = right;
        }
    }
}

int find_rank(int val) { // 给值找排名
    int now = root,ans = 1;
    while (now) {
        if (val <= e[now].val)
            now = e[now].son[0];
        else {
            int left = e[now].son[0],right = e[now].son[1];
            ans += e[left].valid + e[now].exist;
            now = right;
        }
    }
    return ans;
}

void delete_val(int x) { // 删除值 x
    delete_pos(root,find_rank(x));
    // 被删除(标记)的点过多,则重构树
    if((double)e[root].total*alpha > e[root].valid) rebuild(root);
}

void init() { // 内存池初始化
    // i>=1 0是根节点的编号
    for (int i=maxn-1; i>=1; i--)
        memory[++pool] = i;
}

int main() {
    init();
    int n,x,val;
    cin >> n;
    while (n--) {
        cin >> x >> val;
        if (x == 1) insert(root,val);
        if (x == 2) delete_val(val);
        if (x == 3) cout << find_rank(val) << endl;
        if (x == 4) cout <<  find_kth(val) << endl;
        if (x == 5) cout << find_kth(find_rank(val)-1) << endl;
        if (x == 6) cout << find_kth(find_rank(val+1)) << endl;
    }
    return 0;
}
算法
平衡树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！