差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:替罪羊树 [2020/06/23 09:54]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:替罪羊树 [2021/08/11 10:20] (当前版本)
jxm2001 [代码模板]
@@ 行 5: / 行 5: @@
 一种平衡树，思维简单，码量少，速度还行，而且没有旋转操作。
-===== 算法思想 ====
+===== 算法思想 =====
 首先替罪羊树的插入类似普通的二叉搜索树，删除操作就是打上删除标记。
@@ 行 15: / 行 15: @@
 重构方法为中序遍历子树，将没有打上删除标记的结点加入序列。得到一个有序序列，然后用类似线段树建树的方法重新建树。
-重构操作虽然单次复杂度为 $O(n)$，但可以证明均摊复杂度为 $O(\log n)$，证明方法自行百度。
+重构操作虽然单次复杂度为 $O(n)$，但可以用势函数方法证明均摊复杂度为 $O(\log n)$，具体证明方法自行百度。
 问题在于何时考虑重构。
-考虑维护每个结点所在子树的未被删除的结点个数 $\text{cnt}$ 和结点总数 $\text{tot}$。
+考虑维护每个结点所在子树的未被删除的结点个数 $\text{sz}$ 和结点总数 $\text{tot}$。
-引入一个平衡因子 $\alpha$ 值，当 $\alpha\ast\text{cnt} \lt \max(\text{cnt}_{lson},\text{cnt}_{rson})$ 时考虑重构。
+引入一个平衡因子 $\alpha$ 值，当 $\alpha\ast\text{sz} \lt \max(\text{sz}_{lson},\text{sz}_{rson})$ 时考虑重构。
 $\alpha$ 过大将导致树的平衡度较差，查询效率低。 $\alpha$ 过小将导致树的重构次数过多，插入、删除效率低。
@@ 行 29: / 行 29: @@
 同时，如果一棵树上被删除的无效结点过多，也会影响查找效率，所以也需要重构。
-这里设置为当 $\alpha\ast\text{tot} \lt \text{cnt}$ 时考虑重构。
+这里设置 $\beta$ 值为 $0.4$，当 $\beta\ast\text{tot} \gt \text{sz}$ 时考虑重构。
+插入或删除结束后需要检查从根结点到插入结点的路径是否有结点需要重构，不能检查从插入结点到根结点的路径。
+因为一个结点的重构不能影响该结点的祖先结点的平衡度，所以如果该结点的祖先结点需要重构，则重构该结点没有意义。
 ===== 代码模板 =====
@@ 行 37: / 行 41: @@
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e5+5;
+namespace scapegoat_tree{
+	#define lch(k) node[node[k].lch]
+	#define rch(k) node[node[k].rch]
+	const double alpha=0.75,del_x=0.4,inf=1e9;
+	struct Node{
+		int lch,rch,v,sz,tot;
+		bool exist;
+	}node[MAXN];
+	int node_cnt;
+	int new_node(int val){
+		int k=++node_cnt;
+		node[k].lch=node[k].rch=0;
+		node[k].v=val;
+		node[k].sz=node[k].tot=1;
+		node[k].exist=true;
+		return k;
+	}
+	int root,a[MAXN],n;
+	bool isbad(int k){
+		return alpha*node[k].sz<max(lch(k).sz,rch(k).sz);
+	}
+	bool isbad_2(int k){
+		return del_x*node[k].tot>node[k].sz;
+	}
+	void build(int &k,int lef,int rig){
+		if(lef>rig) return k=0,void();
+		int mid=lef+rig>>1;
+		k=a[mid];
+		if(lef==rig){
+			node[k].lch=node[k].rch=0;
+			node[k].sz=node[k].tot=1;
+			return;
+		}
+		build(node[k].lch,lef,mid-1);
+		build(node[k].rch,mid+1,rig);
+		node[k].tot=node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void dfs(int k){
+		if(!k)return;
+		dfs(node[k].lch);
+		if(node[k].exist)a[++n]=k;
+		dfs(node[k].rch);
+	}
+	void rebuild(int &k){
+		n=0;
+		dfs(k);
+		build(k,1,n);
+	}
+	void check(int &k,int v){
+		if(k){
+			if(isbad(k)||isbad_2(k))
+			rebuild(k);
+			else if(v<node[k].v)
+			check(node[k].lch,v);
+			else
+			check(node[k].rch,v);
+		}
+	}
+	int rank(int v){// 返回小于 v 的个数+1
+		int k=root,rk=1;
+		while(k){
+			if(v<=node[k].v)
+			k=node[k].lch;
+			else{
+				rk+=lch(k).sz+node[k].exist;
+				k=node[k].rch;
+			}
+		}
+		return rk;
+	}
+	int kth(int rk){// 返回第 rk 小的数
+		int k=root;
+		while(k){
+			if(lch(k).sz+1==rk&&node[k].exist)return node[k].v;
+			if(lch(k).sz+node[k].exist>=rk)
+			k=node[k].lch;
+			else{
+				rk-=lch(k).sz+node[k].exist;
+				k=node[k].rch;
+			}
+		}
+		return inf;
+	}
+	void Insert(int &k,int v){
+		if(!k){
+			k=new_node(v);
+			return;
+		}
+		node[k].sz++;node[k].tot++;
+		if(v<node[k].v)
+		Insert(node[k].lch,v);
+		else
+		Insert(node[k].rch,v);
+	}
+	void Insert(int v){
+		Insert(root,v);
+		check(root,v);
+	}
+	void Delate(int k,int rk){
+		node[k].sz--;
+		if(lch(k).sz+1==rk&&node[k].exist){
+			node[k].exist=false;
+			return;
+		}
+		if(lch(k).sz+node[k].exist>=rk)
+		Delate(node[k].lch,rk);
+		else
+		Delate(node[k].rch,rk-lch(k).sz-node[k].exist);
+	}
+	void Delate(int v){
+		Delate(root,rank(v));
+		check(root,v);
+	}
+	int pre(int v){// 返回一个严格比 v 小的数
+		return kth(rank(v)-1);
+	}
+	int suf(int v){// 返回一个严格比 v 大的数
+		return kth(rank(v+1));
+	}
+	#undef lch
+	#undef rch
+}
+int main()
+{
+	int q=read_int(),opt,x;
+	while(q--){
+		opt=read_int(),x=read_int();
+		switch(opt){
+			case 1:
+				scapegoat_tree::Insert(x);
+				break;
+			case 2:
+				scapegoat_tree::Delate(x);
+				break;
+			case 3:
+				enter(scapegoat_tree::rank(x));
+				break;
+			case 4:
+				enter(scapegoat_tree::kth(x));
+				break;
+			case 5:
+				enter(scapegoat_tree::pre(x));
+				break;
+			case 6:
+				enter(scapegoat_tree::suf(x));
+				break;
+		}
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具