_WA自动机的blog

过期高中生。

平衡树总结

发表于 更新于 分类于 阅读次数： Valine：

BST：

概念：

BST(Binary Search Tree)：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

  • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

  • 左、右子树也分别为二叉排序树。

应用：

在BST上可以进行这样的操作：

  1. 插入 \(x\)数
  2. 删除 \(x\) 数(若有多个相同的数，因只删除一个)
  3. 查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 +1+1 。若有多个相同的数，因输出最小的排名)
  4. 查询排名为 $ x$ 的数
  5. 求 \(x\) 的前驱(前驱定义为小于 \(x\)，且最大的数)
  6. 求 \(x\) 的后继(后继定义为大于 \(x\)，且最小的数)

实现：

(1.2操作略，s为子树大小)

3.求排名

1
2
3
4
5
6
7
8
int rank(int x,node* o=root)
{
    if (!o) return INT_MAX;
    int s=o->ch[0]?o->ch[0]->s:0;
    if (o->v==x) return s+1;
    if (o->v>x) return rank(x,o->ch[0]);
    if (o->v<x) return rank(x,o->ch[1])+s+o->cnt; 
}

4.求第k大

1
2
3
4
5
6
7
8
int kth(int k,node* o=root)
{
    if (!o) return INT_MIN;
    int s=o->ch[0]?o->ch[0]->s:0;
    if (k>s && k<=s+o->cnt) return o->v;
    if (k<=s) return kth(k,o->ch[0]);
    return kth(k-s-o->cnt,o->ch[1]);
}

5.求前驱

1
2
3
4
5
6
7
8
//全局变量prec
void pre(int x,node* o=root)
{
    if (!o) return;
    if (o->v>prec && o->v<x) prec=o->v;
    if (o->v>=x) pre(x,o->ch[0]);
        else pre(x,o->ch[1]); 
}

6.求后继

1
2
3
4
5
6
7
8
//全局变量succ
void suc(int x,node* o=root)
{
    if (!o) return;
    if (o->v<succ && o->v>x) succ=o->v;
    if (o->v<=x) suc(x,o->ch[1]);
        else suc(x,o->ch[0]);
}

平衡树

随机数据下，树期望高度为\(O(\log n)\)。所以，当树平衡时，所有这些操作时间都为\(O(\log n)\)。但树不一定平衡：按递增或递减顺序插入元素，树就会退化成一条链。在实际应用中，树几乎不会非常平衡。所以，朴素BST表现不佳。

易知，元素相同的BST可能有多种形态（朴素BST的形态与插入顺序有关）。我们我们采用一些方式来使BST的形态发生变化，但仍然为合法BST。这样树就变得平衡。

常见的BST有Splay，Treap，替罪羊树，红黑树，SBT等。

还有权值线段树、01trie、跳表等

大多数BST基于旋转操作。

旋转：

令一个节点换到它的父亲位置上。为了维护BST性质，节点的子节点的位置也会跟着发生变化。 (这里原来有图片，但是挂了)

令x为被旋转节点，y为其父亲，则：

  1. x变到原来y的位置

  2. y与x的位置关系与原来x与y的位置关系相反（如：x为y的左儿子，则后来y为x的右儿子）

  3. y非x的儿子不变，x的与x.y共线的儿子不变

  4. 原来x位置的节点变成了x的与x.y不共线的儿子

代码实现大概是这个样子(建议假设x是左儿子来理解,此时k==0)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//数组版：
inline void rotate(int x)
{//把x旋转到爸爸的位置
    int y=f[x],z=f[y],k=(c[y][1]==x),w=c[x][!k];//k是x相对y的位置，w是x的不与x.y共线的儿子
    c[z][c[z][1]==y]=x;//x变到原来y的位置
    c[x][!k]=y;//x为y的左儿子，则后来y为x的右儿子
    c[y][k]=w;//原来x位置的节点变成了x的与xy不共线的儿子
    if(w)f[w]=y;//更新父亲，下同
    f[y]=x;f[x]=z;
    pushup(y);pushup(x);//只有x.y的子树信息发生改变
}
//指针版：
void rotate(node* &o,int d)
{//o为根，d=0表示右儿子左旋，d=1表示左儿子右旋。此版本未维护父亲指针。
    node* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o->pushup();
    k->pushup();
    o=k;
}

数组和指针操作明显不同是因为我学习时抄的模板不是一个人写的

Treap

  • Treap=Tree+Heap

treap的每个节点有一个随机的优先级。对于键值而言，它是BST；对于优先级而言，它是堆（即，每棵子树中，根的优先级总是最大的）。因为优先级随机，所以树期望平衡。虽然基于随机，但不容易被卡掉，跑得也很快。

我采用刘汝佳式的指针写法，节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node
{
    int v,cnt,rank,s;//cnt是重复元素个数，rank为优先级，s为子树大小。
    node *ch[2];
    node(int v):v(v),cnt(1),s(1),rank(rand()){ch[0]=ch[1]=0;}
    void pushup()
	{
        s=cnt;
        if (ch[0]) s+=ch[0]->s;
        if (ch[1]) s+=ch[1]->s;
    }
    int cmp(int x)
	{
        if (x==v) return -1;
        return v<x;
    }
}*root;

insert

insert操作基本思想为dfs找到新节点应该在的位置并新建该节点，然后回溯判断是否违反堆性质并通过旋转维护堆性质。（注意对重复元素的处理）

1
2
3
4
5
6
7
8
9
void insert(node* &o,int v)
{
    if (!o) {o=new node(v);return;}
    int d=o->cmp(v);
    if (d==-1) {++o->cnt;++o->s;return;}
    insert(o->ch[d],v);
    if (o->ch[d]->rank>o->rank) rotate(o,d^1);
    o->pushup();
}

remove

当要删除的节点只有一个儿子时，删除操作很简单：直接用这个儿子代替它即可。remove操作正是基于这样的理念：将要删除的节点向下转到有至少一棵子树为空，然后删除。若有子树非空，则用非空的儿子代替它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void remove(node* &o,int v)
{
    //if (!o) return;
    int d=o->cmp(v);
    if (d==-1)
    {
        if (o->cnt>1) {--o->cnt;--o->s;return;}
        if (!(o->ch[0])) {node* k=o;o=o->ch[1];delete k;}
        else if (!(o->ch[1])) {node* k=o;o=o->ch[0];delete k;}
        else
        {
            int d2=o->ch[0]->rank>o->ch[1]->rank;
            rotate(o,d2);
            remove(o->ch[d2],v);
        }
    }
    else remove(o->ch[d],v);
    if (o) o->pushup();
}

完整实现如下：

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<ctime>
struct node
{
    int v,cnt,rank,s;
    node *ch[2];
    node(int v):v(v),cnt(1),s(1),rank(rand()){ch[0]=ch[1]=0;}
    void pushup()
	{
        s=cnt;
        if (ch[0]) s+=ch[0]->s;
        if (ch[1]) s+=ch[1]->s;
    }
    int cmp(int x)
	{
        if (x==v) return -1;
        return v<x;
    }
}*root;
void rotate(node* &o,int d)
{
    node* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o->pushup();
    k->pushup();
    o=k;
}
void insert(node* &o,int v)
{
    if (!o) {o=new node(v);return;}
    int d=o->cmp(v);
    if (d==-1) {++o->cnt;++o->s;return;}
    insert(o->ch[d],v);
    if (o->ch[d]->rank>o->rank) rotate(o,d^1);
    o->pushup();
}
void remove(node* &o,int v)
{
    int d=o->cmp(v);
    if (d==-1)
    {
        if (o->cnt>1) {--o->cnt;--o->s;return;}
        if (!(o->ch[0])) {node* k=o;o=o->ch[1];delete k;}
        else if (!(o->ch[1])) {node* k=o;o=o->ch[0];delete k;}
        else
        {
            int d2=o->ch[0]->rank>o->ch[1]->rank;
            rotate(o,d2);
            remove(o->ch[d2],v);
        }
    }
    else remove(o->ch[d],v);
    if (o) o->pushup();
}
int rank(int x,node* o=root)
{
    if (!o) return INT_MAX;
    int s=o->ch[0]?o->ch[0]->s:0;
    if (o->v==x) return s+1;
    if (o->v>x) return rank(x,o->ch[0]);
    if (o->v<x) return rank(x,o->ch[1])+s+o->cnt; 
}
int kth(int k,node* o=root)
{
    if (!o) return INT_MIN;
    int s=o->ch[0]?o->ch[0]->s:0;
    if (k>s && k<=s+o->cnt) return o->v;
    if (k<=s) return kth(k,o->ch[0]);
    return kth(k-s-o->cnt,o->ch[1]);
}
int prec,succ;
void pre(int x,node* o=root)
{
    if (!o) return;
    if (o->v>prec && o->v<x) prec=o->v;
    if (o->v>=x) pre(x,o->ch[0]);
        else pre(x,o->ch[1]); 
}
void suc(int x,node* o=root)
{
    if (!o) return;
    if (o->v<succ && o->v>x) succ=o->v;
    if (o->v<=x) suc(x,o->ch[1]);
        else suc(x,o->ch[0]);
}
int main()
{
    //freopen("phs.in","r",stdin);
    //freopen("phs.out","w",stdout);
    srand(time(0));
    int n;
    int opt,x;
    scanf("%d",&n);
    while (n--)
    {
        scanf("%d%d",&opt,&x);
        switch (opt)
        {
            case 1:insert(root,x);break;
            case 2:remove(root,x);break;
            case 3:printf("%d\n",rank(x));break;
            case 4:printf("%d\n",kth(x));break;
            case 5:prec=INT_MIN;pre(x);printf("%d\n",prec);break;
            case 6:succ=INT_MAX;suc(x);printf("%d\n",succ);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}