平衡树学习笔记
Divinsword_Liao
·
2024-08-07 14:01:06
·
算法·理论
什么是平衡树
平衡树（Balanced Tree）是一种特殊的二叉搜索树，它通过自动调整节点的插入和删除操作，以保持树的平衡性。
在平衡树中，任何节点的左右子树的高度差不超过一个预定义的常数（自平衡）。
平衡树的概念是由 G. M. Adelson-Velsky和Evgenii Landis 两位计算机科学家提出来的，并提供了平衡树的实现--AVL 树， 该树的名称就是由两位作者的姓氏命名的，他们在1962年的论文 An algorithm for the organization of information 中公开了这一数据结构。
当然，平衡树不止有 AVL 树一种，像后面出现的 Treap， Splay树 ， 红黑树等都是平衡树的实现。我们先说AVL树 （其实是因为作者之前只写了AVL树）
AVL 树
AVL 树，是一种平衡的二叉搜索树。由于各种算法教材上对 AVL 的介绍十分冗长，造成了很多人对 AVL 树复杂、不实用的印象。但实际上，AVL 树的原理简单，实现也并不复杂。 （但是作者预习的时候是觉得AVL树比较稳定，会先讲，然后才先学的，结果讲了Treap，而且写了旋转函数没加引用符号，改代码改了一节课，最后自己发现的......）
性质
空二叉树是一个 AVL 树
如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |h(ls) - h(rs)| \leq 1，h 是其左右子树的高度
树高为 O(\log n)
平衡因子：右子树高度 - 左子树高度 （记好）
过程
插入节点
根据平衡树的性质，左小右大，从上往下遍历，在合适的位置插入
删除节点
与Treap类似，先找到要删除的节点，然后将此节点通过旋转转成树的叶子节点，或只有一个子节点，然后再删除或让子节点取父节点的位置
自平衡
在AVL中最重要的判断因子就是子树的高度，若|rs(x).h - ls(x).h| \ge 2 ,就说明树退化了，需要通过左旋(zag)和右旋(zig)操作来减小树的高度。
代码
#include
using namespace std;
#define int long long
#define N 100005
#define ls(x) tree[x].son[0]
#define rs(x) tree[x].son[1]
constexpr int INF = 0x3f3f3f3f; //const 的升级版
//封装成类
class BBT
{
private: //私有的，即外部不可用，在团队协作编程中非常重要
struct AVL {
int val, son[2], size, high, cnt;
} tree[N];
int root, tot;
//inline关键字的原理是在编译时用特定的方式将代码直接复制过去，如代码量较大，且调用地方多，不推荐使用，代码会膨胀得很恐怖，这里是需要速度，所以加上
inline void pushup(int id)
{
if (!id) return;
tree[id].size = tree[ls(id)].size + tree[rs(id)].size + tree[id].cnt;
tree[id].high = max(tree[ls(id)].high, tree[rs(id)].high) + 1;
}
inline void left(int &id)
{
int temp = rs(id);
rs(id) = ls(temp);
ls(temp) = id;
id = temp;
pushup(ls(id));
pushup(id);
}
inline void right(int &id)
{
int temp = ls(id);
ls(id) = rs(temp);
rs(temp) = id;
id = temp;
pushup(rs(id));
pushup(id);
}
inline int newNode(int v)
{
tree[++tot].val = v;
// tree[tot].high = 0;
// ls(tot) = 0;
// rs(tot) = 0;
tree[tot].size = 1; //60
tree[tot].cnt = 1;
return tot;
}
void insert(int &id, int v)
{
if (!id)
{
id = newNode(v);
// pushup(id);
return;
}
if (v < tree[id].val)
{
insert(ls(id), v);
pushup(id);
int lf = ls(id), rt = rs(id);
if (tree[lf].high == tree[rt].high + 2)
{
if (tree[ls(lf)].high == tree[rt].high + 1)
right(id);
else if (tree[rs(lf)].high == tree[rt].high + 1)
left(ls(id)), right(id);
return;
}
return;
}
if (v > tree[id].val)
{
insert(rs(id), v);
pushup(id);
int lf = ls(id), rt = rs(id);
if (tree[rt].high == tree[lf].high + 2)
{
if (tree[rs(rt)].high == tree[lf].high + 1)
left(id);
else if (tree[ls(rt)].high == tree[lf].high + 1)
right(rs(id)), left(id);
return;
}
return;
}
tree[id].cnt ++;
pushup(id);
}
void del(int &id, int v)
{
if (!id) return;
if (tree[id].val == v)
{
if (tree[id].cnt > 1)
{
tree[id].cnt --;
pushup(id);
return;
}
if (!ls(id) || !rs(id))
{
id = ls(id) + rs(id);
return;
}
if (tree[ls(id)].high < tree[rs(id)].high)
left(id), del(ls(id), v);
else right(id), del(rs(id), v);
}
else if (v < tree[id].val)
del(ls(id), v);
else del(rs(id), v);
pushup(id);
}
int Rank(int id, int v)
{
if (!id) return 1;
if (tree[id].val == v)
return tree[ls(id)].size + 1;
if (tree[id].val < v)
return tree[ls(id)].size + Rank(rs(id), v) + tree[id].cnt;
return Rank(ls(id), v);
}
int xth(int id, int rank)
{
if (!id) return INF;
if (rank <= tree[ls(id)].size)
return xth(ls(id), rank);
if (rank <= tree[ls(id)].size + tree[id].cnt)
return tree[id].val;
return xth(rs(id), rank - tree[ls(id)].size - tree[id].cnt);
}
int pre(int id, int v)
{
if (!id) return -INF;
if (tree[id].val < v)
return max(tree[id].val, pre(rs(id), v));
return pre(ls(id), v);
}
int sub(int id, int v)
{
if (!id) return INF;
if (tree[id].val > v)
return min(tree[id].val, sub(ls(id), v));
return sub(rs(id), v);
}
public: //共有的，即外部可用的，一般只有函数，比如queue队列，只有front()等
//重载，因为root在类内，有inline对效率得影响几乎没有
inline void insert(int v)
{
insert(root, v);
}
inline void del(int v)
{
del(root, v);
}
inline int Rank(int v)
{
return Rank(root, v);
}
inline int xth(int rank)
{
return xth(root, rank);
}
inline int pre(int v)
{
return pre(root, v);
}
inline int sub(int v)
{
return sub(root, v);
}
};
#undef int //取消int的宏定义，慎用，除非你知道数据的哪里不会用到long long
#undef N
#undef ls(x)
#undef rs(x)
持续更新中