笔者码风不好，换言之就是语文不好
这篇文章介绍了 fhq_treap, AVL, ScapeGoatTree，这三类数据结构，要是看 splay 请前往 SHIROKU 他写的很好（雾，反正我四爷看不懂splay
说到 AVL 树，我就十分激动，我觉得最简单的，最平易近人的树也就是他，除了码量略大之外还算有好吧，以下的代码均已 P3369 为准，但是 AVL 树是 P6136
操作 BST 基本一致，但是不得不说的是发明 AVL 的人能想到旋转真的太妙了。
AVL: 其每个节点左右孩子的高度差不能超过一，这就保证了十分平衡，具有十分优秀的效率。
然后不平衡就旋转。注意左旋右旋在数据结构了写的和算导是反的，我学的是叫左旋就把左孩子旋转为自己的树根。然后注意双旋修正
在 OI 中极少应用但是还是不错的，因为这玩意出了红黑树之外是最难写的.四种插入，六种删除，四个旋转，然后 prv 和 nxt 操作也不，好写，就是一个遍历的过程，然后遍历到了你懂的.
没啥好说的，注意细节。我有不是讲算法的，就是讲个思路，提供思路了自己写不出来？我觉得挺显然的。
#include <bits/stdc++.h>
using namespace std;
#define gc() getchar()
#define pc(i) putchar(i)
template <typename KYN>
inline KYN read()
{
KYN x = 0;
char ch = gc();
bool f = 0;
while(!isdigit(ch))
{
f = (ch == ‘-‘);
ch = gc();
}
while(isdigit(ch))
{
x = x * 10 + (ch - ‘0‘);
ch = gc();
}
return f ? -x : x;
}
template <typename KYN>
void put(KYN x)
{
if(x < 0)
{
x = -x;
pc(‘-‘);
}
if(x < 10) {
pc(x + 48);
return;
}
put(x / 10);
pc(x % 10 + 48);
return ;
}
#define vit std::vector <int>:: iterator
#define vi std::vector <int>
#define lbd(i, j, k) lower_bound(i, j, k)
#define pii std::pair <int, int>
#define mkp(i, j) std::make_pair(i, j)
#define lowbit(i) (i & -i)
#define ispow(i) (i == lowbit(i))
#define rdi() read <int> ()
#define rdl() read <long long> ()
#define pti(i) put <int> (i), putchar(‘ ‘)
#define ptl(i) put <long long> (i), putchar(‘ ‘)
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull;
typedef unsigned int ui;
const int Maxn = 1e6 + 1e5 + 111;
namespace RSX_love_KYN
{
const int MAXN = 1e6 + 1e5 + 111;
template <typename KYN>
class avlTree
{
private:
struct avlNode;
typedef avlNode *avl;
struct avlNode
{
avl ls, rs;
int size, height, num;
KYN data;
void maintain()
{
this->size = this->ls->size + this->rs->size + this->num;
this->height = max(this->ls->height , this->rs->height) + 1;
}
};
protected:
avl rot, null, tot, deleted[MAXN];
avlNode memory[MAXN];
int deltop;
inline avl init(KYN x)
{
avl tmp = deltop ? deleted[deltop--] : tot++;
tmp->ls = tmp->rs = null;
tmp->size = tmp->num = tmp->height = 1;
tmp->data = x;
return tmp;
}
inline avl Single_left(avl T)
{
avl a = T->ls;
T->ls = a->rs;
a->rs = T;
T->maintain();
a->maintain();
return a;
}
inline avl Single_right(avl T)
{
avl a = T->rs;
T->rs = a->ls;
a->ls = T;
T->maintain();
a->maintain();
return a;
}
inline avl double_left(avl T)
{
T->ls = Single_right(T->ls);
return Single_left(T);
}
inline avl double_right(avl T)
{
T->rs = Single_left(T->rs);
return Single_right(T);
}
avl insert(avl T, KYN x)
{
if(T == null) return init(x);
if(x == T->data)
{
++(T->num);
T->maintain();
return T;
}
if(x < T->data)
{
T->ls = insert(T->ls, x);
T->maintain();
if(T->ls->height - T->rs->height == 2)
{
if(x < T->ls->data) T = Single_left(T);
else T = double_left(T);
}
}
else
{
T->rs = insert(T->rs, x);
T->maintain();
if(T->rs->height - T->ls->height == 2)
{
if(T->rs->data < x) T = Single_right(T);
else T = double_right(T);
}
}
return T;
}
avl erase(avl T, KYN x)
{
if(T == null) return null;
if(x < T->data)
{
T->ls = erase(T->ls, x);
T->maintain();
if(T->rs->height - T->ls->height == 2)
{
if(T->rs->rs->height >= T->rs->ls->height) T = Single_right(T);
else T = double_right(T);
}
}
else if(T->data < x)
{
T->rs = erase(T->rs, x);
T->maintain();
if(T->ls->height - T->rs->height == 2)
{
if(T->ls->ls->height >= T->ls->rs->height) T = Single_left(T);
else T = double_left(T);
}
}
else
{
if(T->num > 1)
{
--(T->num);
T->maintain();
return T;
}
if(T->ls != null && T->rs != null)
{
avl p = T->rs;
while(p->ls != null) p = p->ls;
T->num = p->num;
T->data = p->data, p->num = 1;
T->rs = erase(T->rs, T->data);
T->maintain();
if(T->ls->height - T->rs->height == 2)
{
if(T->ls->ls->height >= T->ls->rs->height) T = Single_left(T);
else T = double_left(T);
}
}
else
{
avl p = T;
if(T->ls != null) T = T->ls;
else if(T->rs != null) T = T->rs;
else T = null;
deleted[++deltop] = p;
}
}
return T;
}
KYN get_rank(avl T, KYN x)
{
int ans = 0;
while(T != null)
{
if(T->data == x) { return ans + T->ls->size + 1; }
else if(x < T->data) { T = T->ls; }
else { ans += T->ls->size + T->num; T = T->rs; }
}
return ans + 1;
}
KYN get_data(avl T, int rank)
{
while(T != null)
{
if(T->ls->size >= rank) T = T->ls;
else if(T->ls->size + T->num >= rank) return T->data;
else rank -= T->num + T->ls->size; T = T->rs;
}
}
avl makeempty(avl x)
{
if(x == null) return null;
x->ls = makeempty(x->ls);
x->rs = makeempty(x->rs);
deleted[++deltop] = x;
return null;
}
void output(avl x)
{
if(x == null) return;
output(x->ls);
put <KYN> (x->data);
putchar(‘ ‘);
output(x->rs);
}
avl find(avl T, KYN x)
{
while(T != null) {
if(T->data == x) return T;
else if(T->data > x) T = T->ls;
else T = T->rs;
}
return null;
}
public:
KYN prv(KYN x)
{
KYN ans = KYN(-1 << 30);
avl tmp = rot;
while(tmp != null)
{
if(tmp->data == x)
{
if(tmp->ls != null)
{
tmp = tmp->ls;
while(tmp->rs != null) tmp = tmp->rs;
ans = tmp -> data;
}
break;
}
if(tmp->data < x && ans < tmp->data) ans = tmp->data;
tmp = tmp->data < x ? tmp->rs : tmp->ls;
}
return ans;
}
KYN next(KYN x) {
KYN ans = KYN(1 << 30);
avl tmp = rot;
while(tmp != null)
{
if(tmp->data == x)
{
if(tmp->rs != null)
{
tmp = tmp->rs;
while(tmp->ls != null) tmp = tmp->ls;
ans = tmp->data;
}
break;
}
if(x < tmp->data && tmp->data < ans) ans = tmp->data;
tmp = tmp->data < x ? tmp->rs : tmp->ls;
}
return ans;
}
avlTree()
{
deltop = 0;
null = tot++;
null->ls = null->rs = null;
null->size = null->height = null->num = 0;
rot = null;
tot = memory;
}
inline void insert(KYN x) { rot = insert(rot, x); return ; }
inline void erase(KYN x) { rot = erase(rot, x); }
inline int get_rank(KYN x) { return get_rank(rot, x); }
inline KYN get_data(int x) { return get_data(rot, x); }
void clear() { rot = makeempty(rot); }
bool find(KYN x) { return find(rot, x) != null; }
void output() { output(rot); }
KYN operator[] (int k) { return get_data(k); }
int size() { return rot->size; }
};
}
using namespace RSX_love_KYN;
int n, opt, x, m, last = 0, tmp, ans;
avlTree <int> tree;
int main() {
#ifdef _DEBUG
freopen("P6136_2.in", "r", stdin);
#endif
n = rdi(); m = rdi();
while(n--) tree.insert(rdi());
while(m--) {
opt = rdi(); x = rdi();
x ^= last;
switch (opt)
{
case 1: tree.insert(x); break;
case 2: tree.erase(x); break;
case 3: last = tree.get_rank(x); ans ^= last; break;
case 4: last = tree[x]; ans ^= last; break;
case 5: last = tree.prv(x); ans ^= last; break;
case 6: last = tree.next(x); ans ^= last; break;
}
}
pti(ans);
return 0;
}
我第二种学的树，不出意外在平衡树裸题里不会用他，太难写了艹。
思想:暴力即优雅.不平衡暴力重构就行了
定义不平衡的概念：一个树太空了和太歪了
没啥好说的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
template <typename T>
inline T read()
{
T x = 0;
char ch = getchar();
bool f = 0;
while(ch < ‘0‘ || ch > ‘9‘)
{
f = (ch == ‘-‘);
ch = getchar();
}
while(ch <= ‘9‘ && ch >= ‘0‘)
{
x = (x << 1) + (x << 3) + (ch - ‘0‘);
ch = getchar();
}
return f ? -x : x;
}
template <typename T>
void put(T x)
{
if(x < 0) { x = -x; putchar(‘-‘); }
if(x < 10) { putchar(x + 48); return; }
put(x / 10);
putchar(x % 10 + 48);
}
int mid(int l, int r) { return (l + r) >> 1; }
const db alpha=0.7125;
template <typename name>
class ScapeGoat
{
private:
struct sgtNode;
typedef sgtNode *sgt;
struct sgtNode
{
sgt ls, rs;
int size, valid;
name data;
bool del;
inline bool bad()
{ return (db) ls->size > alpha * (db) size || (db) rs->size > alpha * (db) size || valid * 3 <= size; }
inline void update()
{ size = ls->size + rs->size + !del; valid = ls->valid + rs->valid + !del; }
};
protected:
sgt rot = NULL, null = NULL;
inline sgt init(name x)
{
sgt tmp = new sgtNode;
tmp->ls = tmp->rs = null;
tmp->del = 0;
tmp->size = tmp->valid = 1;
tmp->data = x;
return tmp;
}
void dfs(sgt T, vector <sgt> &ve) {
if(T == null) return ;
dfs(T->ls ,ve);
if(!T->del) ve.push_back(T);
dfs(T->rs, ve);
if(T->del) delete T;
}
sgt build(int l, int r, vector <sgt> &ve) {
if(l > r) return null;
int mid = (l + r) >> 1;
sgt T = ve[mid];
T->ls = build(l, mid - 1, ve);
T->rs = build(mid + 1, r, ve);
T->update();
return T;
}
void rebuild(sgt &T) {
vector <sgt> ve;
dfs(T, ve);
T = build(0, ve.size() - 1, ve);
return ;
}
void insert(sgt &T, name x) {
if(T == null) {
T = init(x);
return;
}
++(T->size);
++(T->valid);
if(x < T->data) insert(T->ls, x);
else insert(T->rs, x);
if(T->bad()) rebuild(T);
return;
}
void erase(sgt &T, int rk) {
if(T == null) return;
if(!T->del && rk == T->ls->valid + !T->del) {
T->del = 1;
--(T->valid);
return;
}
--(T->valid);
if(rk <= T->ls->valid + !T->del) erase(T->ls, rk);
else erase(T->rs, rk - T->ls->valid - !T->del);
return;
}
sgt makeempty(sgt x)
{
if(x == null) return null;
x->ls = makeempty(x->ls);
x->rs = makeempty(x->rs);
delete x;
return null;
}
bool fin(sgt T, name x)
{
if(T == null) return 0;
if(T->data == x) return 1;
if(T->data < x) return fin(T->rs, x);
return fin(T->ls, x);
}
public:
ScapeGoat()
{
if(null == NULL)
{
null = new sgtNode;
null->ls = null->rs = null;
null->size = null->valid = null->del = 0;
}
rot = null;
}
inline name get_data(int rk) {
sgt T = rot;
while(T != null) {
if(!T->del && !T->del + T->ls->valid == rk) { return T->data; }
if(rk <= T->ls->valid + !T->del) T = T->ls;
else {
rk -= T->ls->valid + !T->del;
T = T->rs;
}
}
}
inline int get_rank(name x) {
int ans = 1;
sgt T = rot;
while(T != null) {
if(x <= T->data) { T = T->ls; }
else { ans += T->ls->valid + !T->del; T=T->rs; }
}
return ans;
}
inline void insert(name x) { insert(rot, x); return ; }
inline void erase(name x) { erase(rot, get_rank(x)); }
inline bool find(name x) { return fin(rot, x); }
inline int prv(name x) { return get_data(get_rank(x) - 1); }
inline int next(name x) { return get_data(get_rank(x + 1)); }
void clear() { rot = makeempty(rot); }
};
ScapeGoat <int> tree;
int n, x, opt;
int main()
{
// freopen("in.txt", "r", stdin);
n = read <int> ();
while(n--)
{
opt = read <int> ();
x = read <int> ();
switch(opt)
{
case 1: tree.insert(x); break;
case 2: tree.erase(x); break;
case 3: put(tree.get_rank(x)), putchar(‘\n‘); break;
case 4: put(tree.get_data(x)), putchar(‘\n‘); break;
case 5: put(tree.prv(x)), putchar(‘\n‘); break;
case 6: put(tree.next(x)), putchar(‘\n‘); break;
}
}
tree.clear();
return 0;
}
好东西呀。真的好东西。可以序列维护，避免了我不会 \(splay\) 的尴尬.
话说我不会treap，就会了 fhq_treap..
两个函数主要 split 和 merge 这是好东西呀。
有两种 merge 一种是根据 size（序列维护），还有就是根据权值其他平衡树.
不多说了代码实现
#include <bits/stdc++.h>
using namespace std;
#define gc() getchar()
#define pc(i) putchar(i)
template <typename T>
inline T read()
{
T x = 0;
char ch = gc();
bool f = 0;
while(!isdigit(ch))
{
f = (ch == ‘-‘);
ch = gc();
}
while(isdigit(ch))
{
x = x * 10 + (ch - ‘0‘);
ch = gc();
}
return f ? -x : x;
}
template <typename T>
void put(T x)
{
if(x < 0)
{
x = -x;
pc(‘-‘);
}
if(x < 10) {
pc(x + 48);
return;
}
put(x / 10);
pc(x % 10 + 48);
return ;
}
#define vit std::vector <int>:: iterator
#define sit std::string:: iterator
#define vi std::vector <int>
#define lbd(i, j, k) lower_bound(i, j, k)
#define pii std::pair <int, int>
#define mkp(i, j) std::make_pair(i, j)
#define lowbit(i) (i & -i)
#define ispow(i) (i == lowbit(i))
#define rdi() read <int> ()
#define rdl() read <long long> ()
#define pti(i) put <int> (i), putchar(‘\n‘)
#define ptl(i) put <long long> (i), putchar(‘ ‘)
#define For(i, j, k) for(int i = j; i <= k; ++i)
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull;
typedef unsigned int ui;
const int Maxn = 204001;
/*
一种叫做 FHQ-Treap,又称作无旋treap
*/
class Treap
{
private:
struct Node;
typedef Node *node;
#define pnn pair <node, node>
struct Node
{
node son[2];
int size, val, rad;
void maintain()
{
this->size = this->son[0]->size + this->son[1]->size + 1;
return void();
}
};
protected:
node null, rot, tot, del[Maxn];
Node memory[Maxn];
int deltop;
inline node init(int x)
{
node tmp = deltop ? del[deltop--] : tot++;
tmp->son[0] = tmp->son[1] = null;
tmp->size = 1;
tmp->val = x;
tmp->rad = rand();
return tmp;
}
pnn split(node T, int k)
{
if(T == null) return mkp(null, null);
pnn t;
if(k < T->val)
{
t = split(T->son[0], k);
T->son[0] = t.second;
T->maintain();
t.second = T;
}
else
{
t = split(T->son[1], k);
T->son[1] = t.first;
T->maintain();
t.first = T;
}
return t;
}
node merge(node x, node y)
{
if(x == null) return y;
if(y == null) return x;
if(x->rad < y->rad)
{
x->son[1] = merge(x->son[1], y);
x->maintain();
return x;
}
else
{
y->son[0] = merge(x, y->son[0]);
y->maintain();
return y;
}
}
void _insert(int v)
{
pnn t = split(rot, v);
rot = merge(merge(t.first, init(v)), t.second);
}
void _erase(int v)
{
pnn t = split(rot, v);
pnn t1 = split(t.first, v - 1);
del[++deltop] = t1.second;
t1.second = merge(t1.second->son[0], t1.second->son[1]);
rot = merge(merge(t1.first, t1.second), t.second);
}
int _rk(int v)
{
pnn t = split(rot, v - 1);
int ans = t.first->size + 1;
rot = merge(t.first, t.second);
return ans;
}
int _data(node T, int rk)
{
while(T != null)
{
if(1 + T->son[0]->size == rk) return T->val;
if(rk <= T->son[0]->size) T = T->son[0];
else
{
rk -= T->son[0]->size + 1;
T = T->son[1];
}
}
}
int _prv(int v)
{
pnn t = split(rot, v - 1);
int ans = _data(t.first, t.first->size);
rot = merge(t.first, t.second);
return ans;
}
void output(node x)
{
if(x == null) return;
output(x->son[0]);
pti(x->val);
output(x->son[1]);
}
int _nxt(int v)
{
pnn t = split(rot, v);
int ans = _data(t.second, 1);
rot = merge(t.first, t.second);
return ans;
}
node mky(node x)
{
if(x == null) return null;
x->son[0] = mky(x->son[0]);
x->son[1] = mky(x->son[1]);
del[++deltop] = x;
return null;
}
public:
Treap()
{
tot = memory;
deltop = 0;
null = tot++;
null->son[0] = null->son[1] = null;
null->size = 0;
rot = null;
}
inline void insert(int v) { return _insert(v); }
inline void erase(int v) { return _erase(v); }
inline int rk(int v) { return _rk(v); }
inline int data(int v) { return _data(rot, v); }
inline int prv(int v) { return _prv(v); }
inline int nxt(int v) { return _nxt(v); }
void output() { return output(rot); }
int operator [](int v) { return _data(rot, v); }
void clear() { rot = mky(rot); }
}tree;
int n;
int main()
{
#ifdef _DEBUG
freopen("in.txt", "r", stdin);
#endif
srand(20050217);
n = rdi();
For(i, 1, n)
{
switch (rdi())
{
case 1: tree.insert(rdi()); break;
case 2: tree.erase(rdi()); break;
case 3: pti(tree.rk(rdi())); break;
case 4: pti(tree[rdi()]); break;
case 5: pti(tree.prv(rdi())); break;
case 6: pti(tree.nxt(rdi())); break;
}
}
return 0;
}
怕是我，永远无法释怀的罢
原文：https://www.cnblogs.com/zhltao/p/12805942.html