据说啊，AVL树 是第一种被发明的平衡树。
它在动态维护过程中，保证了左右子树高度差不超过 \(1\)，
所以说是一种严格平衡的二叉查找树。
最重要的就是左旋、右旋以及左右旋、右左旋，
以及分情况讨论什么时候该做哪一种旋转。
void zig(int &id) {
int rc = rid(id);
//记录下右子节点(right child)
rid(id) = lid(rc);
lid(rc) = id;
update(id);
update(rc);
id = rc;
}//右旋
void zag(int &id) {
int lc = lid(id);
//记录下左子节点(left child)
lid(id) = rid(lc);
rid(lc) = id;
update(id);
update(lc);
id = lc;
}//左旋
void zig_zag(int &id) {
zag(rid(id));
zig(id);
}//右左旋
void zag_zig(int &id) {
zig(lid(id));
zag(id);
}//左右旋
void lgr(int &id) {
if(h(lid(id))-h(rid(id)) >= 2) {
if(h(lid(lid(id))) >= h(rid(lid(id))))
zag(id);
else
zag_zig(id);
}
}//当左子树高度可能更大时
void rgl(int &id) {
if(h(rid(id))-h(lid(id)) >= 2) {
if(h(rid(rid(id))) >= h(rid(lid(id))))
zig(id);
else
zig_zag(id);
}
}//反之
以上就是 AVL树 的核心了。
据说理论分析上 AVL树 比红黑树更快？
但是红黑树的小常数足以把这个小差距盖过去。
其实似乎 AVL树 实在是一种平平无奇的平衡树，
没有 TREAP 简单，没有 FHQ-TREAP 实用，没有 SPLAY 功能多，也没有 红黑树 快。
论暴力程度它也比不上朝鲜树。（（
\(\textrm{luogu P6136 【模板】普通平衡树（数据加强版）}\)
不会有人刚刚才过这题罢
#include <iostream>
#include <algorithm>
const int N = 3e6+10;
struct AVL {
int key, cnt;
int lid, rid;
int height, size;
} avl[N];
int avl_tot, root;
#define key(id) avl[id].key//键值
#define cnt(id) avl[id].cnt//数量
#define lid(id) avl[id].lid//左子节点
#define rid(id) avl[id].rid//右子节点
#define h(id) avl[id].height//子树高
#define s(id) avl[id].size//子树大小
#define mh(x,y) std :: max(h(x),h(y))
int new_node(int val) {
key(++avl_tot) = val;
lid(avl_tot) = rid(avl_tot) = 0;
h(avl_tot) = s(avl_tot) = cnt(avl_tot) = 1;
return avl_tot;
}
int update(int id) {
s(id) = s(lid(id))+s(rid(id))+cnt(id);
h(id) = mh(lid(id),rid(id))+1;
return h(id);
}
void zig(int &id) {
int rc = rid(id);
//记录下右子节点(right child)
rid(id) = lid(rc);
lid(rc) = id;
update(id);
update(rc);
id = rc;
}//右旋
void zag(int &id) {
int lc = lid(id);
//记录下左子节点(left child)
lid(id) = rid(lc);
rid(lc) = id;
update(id);
update(lc);
id = lc;
}//左旋
void zig_zag(int &id) {
zag(rid(id));
zig(id);
}//右左旋
void zag_zig(int &id) {
zig(lid(id));
zag(id);
}//左右旋
void lgr(int &id) {
if(h(lid(id))-h(rid(id)) >= 2) {
if(h(lid(lid(id))) >= h(rid(lid(id))))
zag(id);
else
zag_zig(id);
}
}//当左子树高度可能更大时
void rgl(int &id) {
if(h(rid(id))-h(lid(id)) >= 2) {
if(h(rid(rid(id))) >= h(rid(lid(id))))
zig(id);
else
zig_zag(id);
}
}//反之
void ins(int &id,int val) {
if(!id) {
id = new_node(val);
return;
}
if(key(id) == val) {
++cnt(id);
update(id);
return;
}
if(key(id) < val) {
ins(rid(id),val);
update(id);
rgl(id);
} else {
ins(lid(id),val);
update(id);
lgr(id);
}
update(id);
}
void del(int &id,int val) {
if(!id)
return;
if(key(id) > val) {
del(lid(id),val);
update(id);
rgl(id);
} else if(key(id) < val) {
del(rid(id),val);
update(id);
lgr(id);
} else {
if(cnt(id) > 1) {
--cnt(id);
update(id);
return;
}
if(lid(id)&&rid(id)) {
int now = rid(id);
while(lid(now))
now = lid(now);
cnt(id) = cnt(now);
key(id) = key(now);
cnt(now) = 1;
del(rid(id),key(now));
update(id);
lgr(id);
} else if(lid(id))
id = lid(id);
else if(rid(id))
id = rid(id);
else
id = 0;
}
if(id)
update(id);
}
int get_rks(int id,int val) {
if(!id)
return 1;
if(key(id) == val)
return s(lid(id))+1;
else if(key(id) > val)
return get_rks(lid(id),val);
else
return get_rks(rid(id),val)+s(lid(id))+cnt(id);
}
int get_val(int id,int rks) {
if(s(lid(id)) >= rks)
return get_val(lid(id),rks);
else if(cnt(id)+s(lid(id)) >= rks)
return key(id);
else
return get_val(rid(id),rks-s(lid(id))-cnt(id));
}
int get_pre(int val) {
int id = root;
int res = 0;
while(id) {
if(key(id) == val) {
if(lid(id)) {
id = lid(id);
while(rid(id))
id = rid(id);
res = id;
}
break;
}
if(key(id) <= val&&(key(id) > key(res)||key(res) <= 0))
res = id;
id = key(id) < val ? rid(id) : lid(id);
}
return key(res);
}
int get_suc(int val) {
int id = root;
int res = 0;
while(id) {
if(key(id) == val) {
if(rid(id)) {
id = rid(id);
while(lid(id))
id = lid(id);
res = id;
}
}
if(key(id) > val&&(key(id) < key(res)||key(res) <= 0))
res = id;
id = key(id) < val ? rid(id) : lid(id);
}
return key(res);
}
void init() {
avl_tot = 0;
root = 1;
rid(root) = lid(root) = 0;
}
void dfs(int id) {
if(lid(id))
dfs(lid(id));
printf("%d (%d %d) %d %d\n",id,lid(id),rid(id),cnt(id),key(id));
if(rid(id))
dfs(rid(id));
}
int n, m, opt, x;
int ans, final_ans;
void work_P3369() {
init();
scanf("%d",&n);
for(int i = 1;i <= n;++i) {
scanf("%d %d",&opt,&x);
if(opt == 1) {
if(avl_tot == 0)
root = new_node(x);
else
ins(root,x);
} else if(opt == 2)
del(root,x);
else if(opt == 3)
printf("%d\n",get_rks(root,x));
else if(opt == 4)
printf("%d\n",get_val(root,x));
else if(opt == 5)
printf("%d\n",get_pre(x));
else if(opt == 6)
printf("%d\n",get_suc(x));
else {
printf("DFS >> \n");
dfs(root);
}
}
}
int new_n;
void work_P6136() {
init();
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;++i) {
scanf("%d",&x);
if(avl_tot == 0)
root = new_node(x);
else
ins(root,x);
}
for(int i = 1;i <= m;++i) {
scanf("%d %d",&opt,&x);
x ^= ans;
if(opt == 1) {
if(avl_tot == 0)
root = new_node(x);
else
ins(root,x);
} else if(opt == 2)
del(root,x);
else if(opt == 3)
final_ans ^= (ans = get_rks(root,x));
else if(opt == 4)
final_ans ^= (ans = get_val(root,x));
else if(opt == 5)
final_ans ^= (ans = get_pre(x));
else if(opt == 6)
final_ans ^= (ans = get_suc(x));
else {
printf("DFS >> \n");
dfs(root);
}
}
printf("%d\n",final_ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
work_P6136();
return 0;
}