Treap 是 Tree + Heap (树堆) 的生成词
是一种简单的平衡二叉树

概述

每个结点都有一个随机决定的优先级,每次插入结点和删除结点时,若子结点优先级大于当前结点优先级,那么将该子节点旋转到根节点位置(堆的性质),这样保证了二叉树的平衡。

模板

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
struct Node
{
Node *ch[2];
int r; //优先级
int v; //权值
int s; //结点个数

Node(int v): v(v)
{
ch[0] = ch[1] = NULL;
s = 1;
r = rand();
}
bool operator<(const Node& rhs) const
{
return r < rhs.r;
}
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;
}
};


//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;
}

void insert(Node* &o,int v)
{
if(o == NULL) o = new Node(v);
else
{
int d = (v < o->v ? 0:1);
insert(o->ch[d],v);
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();
}

int find(Node* o,int v)
{
if(o == NULL) return -1;
int d = o->cmp(v);
if(d == -1) return 1;
else return find(o->ch[d],v);
}

//返回名次为K的结点权值
int Kth(Node* o,int k)
{
if(o==NULL || k<=0 || k > o->s) return 0;
int s = (o->ch[0]==NULL ? 0:o->ch[0]->s);
if(k == s+1) return o->v;
else if(k <= s) return Kth(o->ch[0],k);
else return Kth(o->ch[1],k-s-1);
}

//返回权值为v的结点名次
int Rank(Node* o,int v)
{
if(o==NULL) return 0;
int s = (o->ch[0]==NULL?1:o->ch[0]->s+1);
if(v == o->v) return s;
if(v < o->v) return Rank(o->ch[0],v);
else return s+Rank(o->ch[1],v);
}

Splay

伸展树,可以将任意结点旋转到根节点。