Ref: 伸展树的基本操作与应用

概述

Splay 即伸展树,可以将任意结点旋转到根节点,
也可以快捷地进行子树的分裂和合并。
其实现是基于Treap的。

实现

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
struct Node
{
Node *ch[2];
Node *fa;
int r;
int v;
int s;
int id;
Node(int v,int id): v(v),id(id)
{
ch[0] = ch[1] = NULL;
s = 1;
r = rand();
}

int cmp(int x)
{
if(x == v) return -1;
return x<v ? 0:1;
}

void maintain()
{
s = 1;
if(ch[0] != NULL) s += ch[0]->s;
if(ch[1] != NULL) s += ch[1]->s;
}
};

Node *null;

//0 左旋 1 右旋
void rotate(Node* &o,int d)
{
Node* k = o -> ch[d^1];
o -> ch[d^1] = k -> ch[d];
k->ch[d] = o;

o -> maintain();
k -> maintain();

o = k;
}

//寻找序列左数第k个元素并伸展到根
void splay(Node* &o,int k)
{
int d = o->cmp(k);
if(d==1) k -= o->ch[0]->s + 1;
if(d != -1)
{
Node *p = o->ch[d];
int d2 = p->cmp(k);
int k2 = (d2 == 0? k : k - p->ch[0]->s -1);
if(d2!=-1)
{
splay(p->ch[d2],k2);
if(d == d2) rotate(o,d^1);
else rotate(o->ch[d],d);
}
rotate(o,d^1);
}
}

//合并left right,假定left 所有元素比right 小
Node* merge(Node* left,Node* right)
{
splay(left,left->s);
left->ch[1] = right;
left->maintain();
return left;
}

//将o前k小的结点放在left里,其它放在right
void split(Node *o,int k,Node* &left,Node* &right)
{
splay(o,k);
left = 0;
right = o->ch[1];
o->ch[1] = null;
left -> maintain();
}

void insert(Node* &o,int v,int id)
{
if(o == NULL) o = new Node(v,id);
else
{
int d = (v < o->v ? 0:1);
insert(o->ch[d],v,id);
if(o->ch[d]->r > o -> r) rotate(o,d^1);
}
o->maintain();
}

void remove(Node* &o,int v)
{
int d = o -> cmp(v);
if(d == -1)
{
Node* u = o;
if(o -> ch[0] != NULL && o->ch[1] != NULL)
{
int d2 = (o->ch[0]->r > o->ch[1]->r ? 1:0);
rotate(o,d2);
remove(o->ch[d2],v);
}
else
{
if(o->ch[0] == NULL) o = o->ch[1];
else o = o->ch[0];
delete u;
}
}
else remove(o->ch[d],v);
if(o!=NULL) o->maintain();
}