平衡树

前置芝士
普通平衡树
- 1. 替罪羊树
实际时空比较
Refence

Updating...

前置芝士

二叉搜索树（Binary Search Tree，BST）

普通平衡树

模板：

普通平衡树的基本操作可以参考上方模板

1. 替罪羊树

~~众所周知~~ 每种平衡树都有一种操作来维护平衡。

替罪羊树是暴力维护平衡的（

替罪羊树要存左右儿子，节点值，子树实际大小（前面的一般平衡树都要用），子树不实际大小（？）还有删除标记（后面解释）。

struct Node
{
	int l,r,val;
	int size,fact; // 实际大小：fact
	bool exist; // exist : 是否存在
}tzy[N];
int cnt,root; // cnt : 节点数量    root : 根

// 创建新节点
inline void newnode(int &now,int val){now=++cnt; tzy[now].val=val; tzy[now].size=tzy[now].fact=1; tzy[now].exist=true;}

1.1. 插入

只要按 BST 插入方法插入即可，但是为了平衡还得在后面加一句判平衡。

void ins(int &now,int val)
{
	if (!now){newnode(now,val); check(root,now); return ;} // check : 判平衡
	++tzy[now].size; ++tzy[now].fact;
	if (val<tzy[now].val) ins(tzy[now].l,val);
	else ins(tzy[now].r,val);
}

1.2. 删除

还记得前面节点里有维护「删除标记」吗？

对，删除就是把节点打上标记。

而「子树不实际大小」就是树中子树的大小，
「子树实际大小」就是树中子树去掉打了标记的大小。

同样，为了平衡还得在后面加一句判平衡。

void del(int now,int val)
{
	if (tzy[now].exist&&tzy[now].val==val){tzy[now].exist=false; tzy[now].fact--; check(root,now); return ;}
	tzy[now].fact--;
	if (val<tzy[now].val) del(tzy[now].l,val);
	else del(tzy[now].r,val);
}

!.! 判断树是否平衡并调整树

插入和删除都提到了「判平衡」，但是「判平衡」怎么写呢？

我们从根向要操作的节点找，如果找到了需要重构的节点，就暴力重构它的子树。

判断是否平衡的条件是：

当前节点的左子树或右子树的大小大于当前节点的大小 ( imes alpha)，其中 (alpha) 是平衡因子，或
当前节点为根的子树内被删除的节点数量 (>) 树大小（非实际）的 (30\%) 了 .

(alpha) 必须取 ([0.5,1])，一般取 (alphain[0.7,0.8])，最平常的是取 (alpha=0.75) .

inline bool imbalence(int now){return (max(tzy[tzy[now].l].size,tzy[tzy[now].r].size)>tzy[now].size*alpha)||
                                      (tzy[now].size-tzy[now].fact>tzy[now].size*0.3);                      }

所以总体的 check 大概是这样的：

void check(int &now,int end)
{
	if (now==end) return;
	if (imbalence(now)){rebuild(now); update(root,now); return ;}
	if (tzy[end].val<tzy[now].val) check(tzy[now].l,end);
	else check(tzy[now].r,end);
}

这里 rebuild 是重构，update 是更新数据（size）。

update 非常的好写：

void update(int now,int end)
{
	if (!now) return;
	if (tzy[end].val<tzy[now].val) update(tzy[now].l,end);
	else update(tzy[now].r,end);
	tzy[now].size=tzy[tzy[now].l].size+tzy[tzy[now].r].size+1;
}

前面说过了，替罪羊树的维护平衡（重构）是暴力，替罪羊树的重构就是拉开（中序遍历）再拎起来。

来个动图演示一下:

vector<int> v;
void ldr(int now) // 拉开
{
	if (!now) return;
	ldr(tzy[now].l);
	if (tzy[now].exist) v.push_back(now);
	ldr(tzy[now].r);
}
void lift(int l,int r,int &now) // 拎起来
{
	if (l==r){now=v[l]; tzy[now].l=tzy[now].r=0; tzy[now].size=tzy[now].fact=1; return ;}
	int m=(l+r)>>1;
	while ((l<m)&&(tzy[v[m]].val==tzy[v[m-1]].val)) --m;
	now=v[m];
	if (l<m) lift(l,m-1,tzy[now].l);
	else tzy[now].l=0;
	lift(m+1,r,tzy[now].r);
	tzy[now].size=tzy[tzy[now].l].size+tzy[tzy[now].r].size+1; // （
	tzy[now].fact=tzy[tzy[now].l].fact+tzy[tzy[now].r].fact+1;
}
void rebuild(int &now)
{
	v.clear(); ldr(now);
	if (v.empty()){now=0; return ;}
	lift(0,v.size()-1,now);
}

1.3. & 1.4. 查询值的排名 / 查询排名的值

这些就按照普通 BST 写就行啦

int getrank(int val)
{
	int now=root,rank=1;
	while (now)
	{
		if (val<=tzy[now].val) now=tzy[now].l;
		else {rank+=tzy[now].exist+tzy[tzy[now].l].fact; now=tzy[now].r;}
	} return rank;
}
int getval(int rank)
{
	int now=root;
	while (now)
	{
		if (tzy[now].exist&&tzy[tzy[now].l].fact+tzy[now].exist==rank) break;
		else if (tzy[tzy[now].l].fact>=rank) now=tzy[now].l;
		else {rank-=tzy[tzy[now].l].fact+tzy[now].exist; now=tzy[now].r;} // 这个 rank-=... 有主席树内味了
	} return tzy[now].val;
}

1.5. & 1.6. 求前趋 / 求后继

前趋和后继有个小技巧：
前趋：getval(getrank(x)-1);
后继：getval(getrank(x+1));

inline int pre(int x){return getval(getrank(x)-1);}
inline int nxt(int x){return getval(getrank(x+1));}

实际时空比较

普通平衡树：

平衡树	代码长度	时间	空间
替罪羊树	3.15KB	352ms	1.89MB

平衡树