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
| #pragma once
#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "search_tree.h"
namespace data_structure {
template <class T>
class splay_tree : public search_tree<T> {
struct node {
node *ch[2], *fa;
T key;
};
memery_pool<node> pool;
node* root;
void copy_self(node*& rt, node* fa, node* cp) {
if (cp == nullptr) return;
rt = pool.get();
rt->key = cp->key;
rt->fa = fa;
copy_self(rt->ch[0], rt, cp->ch[0]);
copy_self(rt->ch[1], rt, cp->ch[1]);
}
void delete_self(node* rt) {
if (rt == nullptr) return;
delete_self(rt->ch[0]);
delete_self(rt->ch[1]);
pool.erase(rt);
}
node* newnode(const T& w, node* fa) {
node* res = pool.get();
res->ch[0] = res->ch[1] = nullptr;
res->fa = fa;
res->key = w;
return res;
}
int which_son(node* rt) { return rt == rt->fa->ch[1]; }
void rotate(node* son) {
assert(son != nullptr);
node* fa = son->fa;
if (fa == root) root = son;
assert(fa != nullptr);
node* gr = fa->fa;
int sonis = which_son(son);
son->fa = gr;
fa->fa = son;
if (son->ch[sonis ^ 1] != nullptr) son->ch[sonis ^ 1]->fa = fa;
if (gr != nullptr) gr->ch[gr->ch[1] == fa] = son;
fa->ch[sonis] = son->ch[sonis ^ 1];
son->ch[sonis ^ 1] = fa;
}
void splay(node* rt) {
assert(rt != nullptr);
while (rt->fa != nullptr) {
node *fa = rt->fa, *gr = fa->fa;
if (fa != root) which_son(rt) == which_son(fa) ? rotate(fa) : rotate(rt);
rotate(rt);
}
}
node* search(node* rt, const T& w) {
if (rt == nullptr)
return rt;
else if (w < rt->key)
return search(rt->ch[0], w);
else if (rt->key < w)
return search(rt->ch[1], w);
else {
splay(rt);
return rt;
}
}
void insert(node*& rt, const T& w, node* fa) {
if (rt == nullptr) {
splay(rt = newnode(w, fa));
} else if (w < rt->key) {
insert(rt->ch[0], w, rt);
} else if (rt->key < w) {
insert(rt->ch[1], w, rt);
}
}
void replace(node* a, node* b) {
if (a == root)
root = b;
else
a->fa->ch[which_son(a)] = b;
if (b != nullptr) b->fa = a->fa;
pool.erase(a);
}
void erase(node* rt, const T& w) {
rt = search(rt, w);
if (rt == nullptr || rt->key != w) return;
if (rt->ch[0] == nullptr)
replace(rt, rt->ch[1]);
else if (rt->ch[1] == nullptr)
replace(rt, rt->ch[0]);
else {
node* pre = rt->ch[0];
while (pre->ch[1] != nullptr) pre = pre->ch[1];
rt->key = pre->key;
replace(pre, pre->ch[0]);
}
}
void preorder(node*& rt, void (*f)(const T&)) {
if (rt == nullptr) return;
f(rt->key);
preorder(rt->ch[0], f);
preorder(rt->ch[1], f);
}
void midorder(node*& rt, void (*f)(const T&)) {
if (rt == nullptr) return;
midorder(rt->ch[0], f);
f(rt->key);
midorder(rt->ch[1], f);
}
int hight() { return hight(root); }
int hight(node* rt) {
using namespace algorithm;
if (rt == nullptr) return 0;
return 1 + max(hight(rt->ch[0]), hight(rt->ch[1]));
}
public:
splay_tree() { root = nullptr; }
splay_tree(const splay_tree<T>& rhs) { copy_self(root, nullptr, rhs.root); }
splay_tree<T> operator=(const splay_tree<T>& rhs) {
delete_self(root);
copy_self(root, nullptr, rhs.root);
return *this;
}
~splay_tree() { delete_self(root); }
void insert(const T& w) { insert(root, w, nullptr); }
node*& search(const T& w) { return search(root, w); }
void erase(const T& w) { erase(root, w); }
void preorder(void (*f)(const T&)) { preorder(root, f); }
void midorder(void (*f)(const T&)) { midorder(root, f); }
};
}
|
设自己为x，父亲为y，祖父为z， 则势能变化为 \[
\begin{aligned}
&X'+Y'+Z'-X-Y-Z
\\&=Y'+Z'-X-Y\lt X'+Z'-2X
\\&=(3X'-3X)+(X+Z'-2X')
\end{aligned}
\] 这里的x和z‘的子树大小加起来刚好等于x'的子树大小-1。所以势能变化小于\(3(X'-X)-2\) ### 对于一条非直链，我们要rotate自己两次，才能上去，rotate父亲不行的 
同理，势能变化为 \[
\begin{aligned}
&X'+Y'+Z'-X-Y-Z
\\&=Y'+Z'-X-Y\lt Y'+Z'-2X
\\&=(2X'-2X)+(Y'+Z'-2X')
\end{aligned}
\] 这里的y'和z'的子树大小加起来刚好等于x‘的子树大小-1，所以势能变化小于\(2(X'-X)-2\) ### 单旋 易证势能变化小于\(X'-X\) ### 整理合并 三种操作的均摊复杂度分别为\(O(1)+X'-X\),\(O(1)+2(X'-X)-2\),\(O(1)+3(X'-X)-2\),对于后面的两种情况,我们增大势的单位来支配隐藏在O(1)中的常数，最终分别为\(O(1)+X'-X\),\(2(X'-X)\),\(3(X'-X)\),再次放缩: \(O(1)+3(X'-X)\),\(3(X'-X)\),\(3(X'-X)\),最后对于所有的旋转求和，因为只有一次单旋所以最终我们得到了均摊复杂度为\(O(1)+X'-X\lt O(1)+X'\),显然X'是一个很小的数，他恰好等于伸展树中的元素的个数取对数后的结果。至此所有的操作均取决于splay的复杂度，均为\(lg\)级别。 ## splay代码