【模板】替罪羊树——SGT

替罪羊树(SGT),又叫重量平衡树,通过将不平衡的子树拍扁重构来保证整棵树的平衡。

常见的平衡树保证平衡的方式有旋转(Treap,Splay),分割合并(fhq Treap),还有暴力重构(SGT)。

本文采用数组模拟指针的方式来实现SGT。

节点

节点有记录父亲和不记录父亲两种方式,我这里为了节省空间使用不记录的,需要用到父亲的位置(rebuild)直接用指针来充当边就好了。

1
2
3
4
5
6
7
8
9
//const int NIL = -1;
struct Node {
Node() : key(0), left(NIL), right(NIL), cnt(0), size(0) { }
int key;//关键字
int cnt;//当前节点个数
int size;//当前子树大小
int left;//左儿子下标
int right;//右儿子下标
};

插入

我们先像BST一样在树上走路,找到插入的位置插进去。然后看其他人代码都是往上找不平衡的节点重构,而我推荐从根再走一遍来寻找重构节点,一是常数比较小,二是不用记录父亲。

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
void insert(int key) {
//注意一下我的newNode(int)创建出来的节点cnt和size都是0,不可以直接退出。
if(root == NIL) root = newNode(key);
int now = root;
while(true) {
//在树上走路
++node[now].size;
if(key < node[now].key) {
if(node[now].left == NIL) {
node[now].left = newNode(key);
}
now = node[now].left;
} else if(node[now].key < key) {
if(node[now].right == NIL) {
node[now].right = newNode(key);
}
now = node[now].right;
} else {
//找到节点,退出
++node[now].cnt;
break;
}
}
int *son = &root;
//使用指针来记录边,方便修改
while(node[*son].key != key) {
if(!balance(*son)) {
//如果不平衡就重构
rebuild(son);
break;
}
if(key < node[*son].key) {
son = &node[*son].left;
} else if(node[*son].key < key) {
son = &node[*son].right;
}
}
return;
}

删除

SGT的删除也许是平衡树中的一股清流,不用做什么操作,只要把cnt设成0就行了。然后如果空节点个数大于了整棵树的一半,就把整棵树重构一下,并扔掉所有空节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void remove(int key) {
int now = root;
while(true) {
//在树上走路
--node[now].size;
if(key < node[now].key) {
now = node[now].left;
} else if(node[now].key < key) {
now = node[now].right;
} else {
--node[now].cnt;
if(node[now].cnt == 0) {
++del_num;//记录树中有多少被删除的节点
}
break;
}
}
if((del_num << 1) > node[root].size) {
rebuild(&root);
}
return;
}

重构

SGT的精髓就是暴力重构(感觉有点怪),那么我们这就来讲一下怎么暴力重构

平衡

当一个节点不平衡的时候,我们就把这棵子树拍扁重构。

判断一个子树平不平衡的方式,我们选择让根节点的size乘以一个平衡因子alpha,如果比任何一个子树的size小,则认为他是不平衡的。

这个alpha是我们自己定的,在0.6~0.9之间效果较好,在0.5~0.6之间或0.9~1.0之间SGT的复杂度就会明显退化。我推荐你们在0.7~0.8之间选一个,我习惯使用0.75。
——igronemyk

判断平衡代码如下:

1
2
3
4
5
6
7
8
bool balance(int key) {
//平衡返回true,不平衡返回false
//BALANCE_SIZE即为alpha
return (node[key].left == NIL ||
node[key].size * BALANCE_SIZE >= (double)node[node[key].left].size) &&
(node[key].right == NIL ||
node[key].size * BALANCE_SIZE >= (double)node[node[key].right].size);
}

重构

重构子树分几步:

  1. 把子树拍扁成一个序列
  2. 按序列重建一棵完全平衡的树
  3. 把指向原来子树根节点的边指向新的子树根

拍扁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void recycle(int now, int &cnt, int *id) {
//now 当前节点下标
//cnt 拍扁后数组长度
//id 拍扁后数组
if(node[now].left != NIL) {
recycle(node[now].left, cnt, id);
}
if(node[now].cnt > 0) {
//如果当前节点不是被删除的节点就直接放到数组里
id[++cnt] = now;
} else {
//否则就无视这个节点,并且让空节点个数-1
--del_num;
}
if(node[now].right != NIL) {
recycle(node[now].right, cnt, id);
}
return;
}

重构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int build(const int *arr, int left, int right) {//[left, right]
const int mid = left + right >> 1;
//mid就是当前节点的在数组中的位置
node[arr[mid]].size = node[arr[mid]].cnt;
if(mid - 1 >= left) {
node[arr[mid]].left = build(arr, left, mid - 1);
node[arr[mid]].size += node[node[arr[mid]].left].size;
} else {
node[arr[mid]].left = NIL;
}
if(mid + 1 <= right) {
node[arr[mid]].right = build(arr, mid + 1, right);
node[arr[mid]].size += node[node[arr[mid]].right].size;
} else {
node[arr[mid]].right = NIL;
}
return arr[mid];
//返回当前子树的根节点
}

rebuild

1
2
3
4
5
6
7
8
void rebuild(int *son) {
int now = *son;
int len = 0;
static int *id = new int[MAX_SGT_NODE_NUM];
recycle(now, len, id);
*son = build(id, 1, len);
return;
}

其实SGT还是很简单的,把主要思想告诉大家其实大家都能自己写出来。

上一份完整的普通平衡树代码,加上主函数只有200行左右,还是很短的:
https://paste.ubuntu.com/p/4Tb7hv9VDh/