知识点:二叉(重量)平衡树——替罪羊树 亦凉 2021-12-14 10:45 248阅读 0赞 目录 * 知识点概要 * 知识点详解 * 平衡因子 * 子树的重构 * 基础操作 * 复杂度分析 * 关于替罪羊树 * 代码(luogu3369 && BZOJ3224) ## 知识点概要 ## 在各种二叉平衡树中,大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质,并且尽量保证每次的查找的复杂度为\\(log\\)的。然而说实话,各种情况的旋转很容易写挂,考场上一旦写挂掉就会心态爆炸,所以我们或许可以通过一些奇妙的方法来使这棵二叉平衡树能够拥有与有需要旋转的二叉查找树同样的性质。而替罪羊树则是这众多非旋转的二叉平衡树中比较好些也比较好理解的一种了(至少比无旋Treap要简单的多了)。 接下来讲替罪羊树是如何实现非旋转的。首先问何为数据结构的优美? 暴力啊~ 数据结构最优美的莫过于最暴力却又仍然满足复杂度的数据结构了(类似的还有分块啊,莫队啊,都是很优美的 逃)。所以替罪羊树秉承着最暴力的思想:如果树的结构不够优美了(即查找的复杂度要退化成\\(O(n)\\)或者比\\(log\\)要大了),那么就把这棵子树拍扁了重构,具体如何重构将在下面讲述。这样就能重新回复二叉查找树优美的性质了。所以只要是没有需要提取子树来进行干什么的一些操作,那么替罪羊树无论在代码量和运行时间上都可以优于splay许多。 ## 知识点详解 ## **注:接下来的代码都以luogu3369为例** ### 平衡因子 ### 平衡因子,顾名思义,是为了判断这棵树是否平衡的一个系数,而在替罪羊树中,这个平衡因子就是用来判断这一棵子树是否需要重构的标准,我们用\\(\\alpha\\)来表示。当以x为根这颗子树的满足\\(max(sz\[lson,sz\[rson\])>=sz\[x\]\*\\alpha\\)时,我们就可以对这颗子树进行重构了。一般\\(\\alpha\\)取值为0.5~1左右,普通题目一般取0.7左右就行了。如果取的\\(\\alpha\\)较大,那么重构的次数就比较小,所以插入的效率较高,而查询的效率会相对较低,反之也是如此。 子树重构的代码(由于比较短,就直接现在\\(node\\)结构体里了),代码也顺便给出了\\(node\\)结构体里的各种变量的定义。 struct node { node *l,*r;//左右孩子 int v,sz,valid;//节点的值,节点的字数大小,节点合法(未被删除)子树大小 bool del;//节点是否被删除 bool Bad() {//字数是否需要重构 return (double)l->sz>alpha*(double)sz||(double)r->sz>alpha*(double)sz; } void Update() {//节点的各个值的更新 sz=!del+l->sz+r->sz; valid=!del+l->valid+r->valid; } }; ### 子树的重构 ### 当我们的树不够平衡的时候,我们就要对于这个子树进行重构了,然而由于这是一棵二叉查找树,所以我们仍要维护这个性质,即保持重建后整棵树的中序遍历与原树相同。所以我们就可以对需要重构的子树进行中序遍历一下,然后二分递归下去进行重构(有点类似与线段树的构建)。 下面是构造之前与构造之后的图: 构造前: ![原树][70] 构造后: ![构造后][70 1] 子树重构的代码: node *Build(std::vector<node*> &v,int l,int r) { if(l>=r) return null; int mid=(l+r)>>1; node *o=v[mid]; o->l=Build(v,l,mid); o->r=Build(v,mid+1,r); o->Update(); return o; } void Dfs(node *o,std::vector<node*> &v) { if(o==null) return ; Dfs(o->l,v); if(!o->del) v.push_back(o);//如果这个节点被删除了,那么就不用进行重构了 Dfs(o->r,v); if(o->del) delete o; //节点删除 } void ReBuild(node* &o) { std::vector<node*>v;//v数组记录中序遍历之后各个需要重构的节点 Dfs(o,v); o=Build(v,0,v.size());//o表示重构之后子树的根节点 } ### 基础操作 ### 替罪羊树的基础的操作基本都与普通平衡树的操作类似。 插入: 与普通的splay大致相同,只不过插入之后需要判断子树是否需要重构。 void Insert(int x,node* &o) { if(o==null) {//新建节点 o=new node; o->l=o->r=null; o->del=false; o->sz=o->valid=1; o->v=x; return ; } ++o->sz;++o->valid;//在递归下去的时候就把该维护的信息维护好 if(x>=o->v) Insert(x,o->r); else Insert(x,o->l); if(o->Bad()) ReBuild(o);//判断是否需要重构 } 删除: 这里的删除并不是直接的删除,而是给这个节点打上一个删除标记,直到重构子树的时候再把无用的节点删除掉。 void Delete(node *o,int rnk) {//当前节点、需要删除的节点的排名(所以在删除之前需要查询一下rank) if(!o->del&&rnk==o->l->valid+1) { o->del=1;//打上删除标记 --o->valid; return ; } --o->valid;//维护子树未被删除节点的信息 if(rnk<=o->l->valid+!o->del) Delete(o->l,rnk); else Delete(o->r,rnk-o->l->valid-!o->del); } 查询rank与kth也都与其他的平衡树差不多。 int GetRank(node* o,int x) { int ans=1; while(o!=null) { if(o->v>=x) o=o->l; else { ans+=o->l->valid+!o->del; o=o->r; } } return ans; } int FindKth(node* o,int x) { while(o!=null) { if(!o->del&&o->l->valid+1==x) return o->v; if(o->l->valid>=x) o=o->l; else { x-=o->l->valid+!o->del; o=o->r; } } } ### 复杂度分析 ### 虽然说是要重构子树,但是复杂度并不会太高,重构一次为\\(O(n)\\)的,并且只有插入的节点达到\\(\\alpha\*size\[t\]\\)的时候才有可能会进行重建,所以总共会重建\\(log\\)次,而其他操作的复杂度也是不高的,所以均摊下来总体的复杂度是\\(O(nlogn)\\)的,也是十分优美的。 ### 关于替罪羊树 ### 替罪羊树虽然在时间复杂度和代码量上都远超splay,然而为什呢替罪羊树运用的却并不广泛呢。原因或许就在于他的非旋转性吧,splay虽然需要用到旋转的操作,但是他灵活性确实无可质疑的,因为splay在维护一个序列的操作中近乎完美。所以替罪羊树的应用也并没有splay那么广泛,不过如果碰到题目可以用替罪羊树代替splay的话,那么就可以毫无异议的使用替罪羊树了。 ## 代码(luogu3369 && BZOJ3224) ## #include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const double alpha=0.7; int n; /*==================Define Area================*/ namespace ScapegoatTree { struct node { node *l,*r; int v,sz,valid; bool del; bool Bad() { return (double)l->sz>alpha*(double)sz||(double)r->sz>alpha*(double)sz; } void Update() { sz=!del+l->sz+r->sz; valid=!del+l->valid+r->valid; } }; node *null; void Dfs(node *o,std::vector<node*> &v) { if(o==null) return ; Dfs(o->l,v); if(!o->del) v.push_back(o); Dfs(o->r,v); if(o->del) delete o; } node *Build(std::vector<node*> &v,int l,int r) { if(l>=r) return null; int mid=(l+r)>>1; node *o=v[mid]; o->l=Build(v,l,mid); o->r=Build(v,mid+1,r); o->Update(); return o; } void ReBuild(node* &o) { std::vector<node*>v; Dfs(o,v); o=Build(v,0,v.size()); } void Insert(int x,node* &o) { if(o==null) { o=new node; o->l=o->r=null; o->del=false; o->sz=o->valid=1; o->v=x; return ; } ++o->sz;++o->valid; if(x>=o->v) Insert(x,o->r); else Insert(x,o->l); if(o->Bad()) ReBuild(o); } int GetRank(node* o,int x) { int ans=1; while(o!=null) { if(o->v>=x) o=o->l; else { ans+=o->l->valid+!o->del; o=o->r; } } return ans; } int FindKth(node* o,int x) { while(o!=null) { if(!o->del&&o->l->valid+1==x) return o->v; if(o->l->valid>=x) o=o->l; else { x-=o->l->valid+!o->del; o=o->r; } } } void Delete(node *o,int rnk) { if(!o->del&&rnk==o->l->valid+1) { o->del=1; --o->valid; return ; } --o->valid; if(rnk<=o->l->valid+!o->del) Delete(o->l,rnk); else Delete(o->r,rnk-o->l->valid-!o->del); } node *rt; } using namespace ScapegoatTree; int main() { null=new node; rt=null; read(n); while(n--) { int opt,x; read(opt);read(x); if(opt==1) Insert(x,rt); if(opt==2) Delete(rt,GetRank(rt,x)); if(opt==3) writeln(GetRank(rt,x)); if(opt==4) writeln(FindKth(rt,x)); if(opt==5) writeln(FindKth(rt,GetRank(rt,x)-1)); if(opt==6) writeln(FindKth(rt,GetRank(rt,x+1))); } return 0; } 转载于:https://www.cnblogs.com/Apocrypha/p/9430380.html [70]: /images/20211214/564b60c0813247e58448d5b58c3ef509.png [70 1]: /images/20211214/4e93f84849e5458f84a1de141a4958ec.png
相关 二叉搜索树、平衡二叉树 一、二叉搜索树 这里我们不用太多书面化的语言来定义,笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字,不便于读者理解。 阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 31 阅读
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 233 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 402 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 271 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 245 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 292 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 328 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 443 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 446 阅读
还没有评论,来说两句吧...