• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

平衡树

开发技术 开发技术 5小时前 3次浏览

二分查找树( BST )

(operatorname{BST}) 树满足性质:

  1. 每一个节点关键码 不小于左子树中 任意节点关键码。

  2. 每一个节点关键码 不大于右子树中 任意节点关键码。

  3. 整棵树 中序遍历单调递增

  • 建立:由两个节点( (+inf~&~-inf) )构成 。

  • 查询:从根开始一个个比较,逐渐来到查询的点 。

  • 插入:若已经有了这个点,那么 (cnt++) ;否则新建一个叶子节点 。与查询操作类似 。

  • 前驱(后继):先向左(右)走,在一直往右(左)走,直至不能走为止 。

  • 删除:

    • 只有左子树或右子树 :直接删除 (x) ,令 (x) 的子节点代替 (x) 的位置 。

    • 既有左子树又有右子树 :在 (x) 子树中找出 (x) 的后继 (next) ,令 (next) 代替 (x) 的位置,删除 (next)

期望复杂度 (O(log~n)) ,但是极易退化为 (O(n))


Treap

即在 (operatorname{BST}) 的基础上加入 旋转 操作 。

每一个节点仅记录了左右子节点,不记录父亲节点 。(operatorname{Treap}) 通过 左旋(operatorname{zag}) )和 右旋(operatorname{zig}) ),通过 随机数据 保持平衡 。(operatorname{Treap}) 给每一个节点赋予了一个随机值,用来满足堆性质 。

对于 插入 操作:同 (operatorname{BST}) 的加入方式,自下而上依次检查,当某个节点不满足大根堆性质时就进行单旋操作 。

特别对于 删除 操作:

  • 如果只有一个儿子:用它的儿子代替它并替代它 。

  • 若果有两个儿子:把需要删除的节点旋转到只有一个儿子 。

总而言之:(operatorname{Treap}) 通过适当的单旋操作,在 维持关键码满足 (operatorname{BST}) 性质 的同时,还 使每个节点上生成的额外权值满足大根堆性质

复杂度:都是 (O(log~n))

  • P3369 【模板】普通平衡树(弱化版)

对于这道题,要求查询排名,则给每一个节点增加一个值 (size) ,在进行 (ratate) 操作时也要对 (size) 进行更改 。

因为要对 (size) 进行修改,所以查询操作用递归的形式 。

$text{Treap}$ 模板代码
#include<bits/stdc++.h>
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x7f7f7f7f
#define Maxn 200005
typedef long long ll;
inline int rd()
{
	 int x=0;
     char ch,t=0;
     while(!isdigit(ch = getchar())) t|=ch=='-';
     while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
     return x=t?-x:x;
}
int n,m,tot,root;
int a[Maxn],b[Maxn];
struct treap
{
	 int randval,val;
	 int ls,rs;
	 int cnt,siz;
}tree[Maxn];
void pushup(int p)
{
	 tree[p].siz=tree[p].cnt+tree[tree[p].ls].siz+tree[tree[p].rs].siz;
}
int New(int val)
{
	 tree[++tot].val=val,tree[tot].randval=rand();
	 tree[tot].cnt=tree[tot].siz=1;
	 tree[tot].ls=tree[tot].rs=0;
	 return tot;
}
void build()
{
	 New(-inf),New(inf);
	 tree[1].rs=2,root=1;
	 pushup(root);
}
void zag(int &x) // Make ls turn right
{
	 int p=tree[x].ls;
	 tree[x].ls=tree[p].rs,tree[p].rs=x;
	 pushup(x),pushup(p),x=p;
}
void zig(int &x) // Make rs turn left
{
	 int p=tree[x].rs;
	 tree[x].rs=tree[p].ls,tree[p].ls=x;
	 pushup(x),pushup(p),x=p;
}
void Insert(int &p,int val)
{
	 if(!p) { p=New(val); return; }
	 if(val==tree[p].val) { tree[p].cnt++; pushup(p); return; } // 别忘了 pushup 
	 if(val<tree[p].val)
	 {
	 	 Insert(tree[p].ls,val);
	 	 if(tree[p].randval<tree[tree[p].ls].randval) zag(p);
	 }
	 else
	 {
	 	 Insert(tree[p].rs,val);
	 	 if(tree[p].randval<tree[tree[p].rs].randval) zig(p);
	 }
	 pushup(p);
}
void del(int &p,int val)
{
	 if(!p) return;
	 if(val==tree[p].val)
	 {
	 	 if(tree[p].cnt>1) { tree[p].cnt--; pushup(p); return; } // 别忘了 pushup 
	 	 if(tree[p].ls || tree[p].rs)
	 	 {
	 	 	 if(tree[p].rs==0 || tree[tree[p].ls].randval>tree[tree[p].rs].randval)
			   	 zag(p),del(tree[p].rs,val); // 保持大根堆性质 
	 	 	 else zig(p),del(tree[p].ls,val);
	 	 	 pushup(p);
		 }
		 else p=0;
		 return;
	 }
	 if(val<tree[p].val) del(tree[p].ls,val);
	 else del(tree[p].rs,val);
	 pushup(p);
}
int query_val(int p,int rank)
{
	 if(!p) return inf;
	 if(tree[tree[p].ls].siz>=rank) return query_val(tree[p].ls,rank);
	 if(tree[tree[p].ls].siz+tree[p].cnt>=rank) return tree[p].val;
	 return query_val(tree[p].rs,rank-tree[tree[p].ls].siz-tree[p].cnt);
}
int query_rank(int p,int val)
{
	 if(!p) return 0;
	 if(val==tree[p].val) return tree[tree[p].ls].siz+1;
	 if(val<tree[p].val) return query_rank(tree[p].ls,val);
	 return query_rank(tree[p].rs,val)+tree[tree[p].ls].siz+tree[p].cnt;
}
int pre(int val)
{
	 int p=root,ans=1; // 无穷小 
	 while(p)
	 {
	 	 if(val==tree[p].val)
	 	 {
	 	 	 if(tree[p].ls)
			 {
			 	 for(p=tree[p].ls;tree[p].rs;p=tree[p].rs);
			 	 ans=p;
			 }
			 break;
		 }
		 if(tree[p].val<val && tree[p].val>tree[ans].val) ans=p; // 及时更新 
		 if(val<tree[p].val) p=tree[p].ls;
		 else p=tree[p].rs;
	 }
	 return tree[ans].val;
}
int nex(int val)
{
	 int p=root,ans=2; // 无穷大 
	 while(p)
	 {
	 	 if(val==tree[p].val)
	 	 {
	 	 	 if(tree[p].rs)
	 	 	 {
	 	 	 	 for(p=tree[p].rs;tree[p].ls;p=tree[p].ls);
	 	 	 	 ans=p;
			 }
			 break;
		 }
		 if(tree[p].val>val && tree[p].val<tree[ans].val) ans=p;
		 if(val<tree[p].val) p=tree[p].ls;
		 else p=tree[p].rs;
	 }
	 return tree[ans].val;
}
int main()
{
     //freopen(".in","r",stdin);
     //freopen(".out","w",stdout);
	 n=rd(),build();
	 int opt,x;
	 for(int i=1;i<=n;i++)
	 {
	 	 opt=rd(),x=rd();
	 	 if(opt==1) Insert(root,x);
	 	 if(opt==2) del(root,x);
	 	 if(opt==3) printf("%dn",query_rank(root,x)-1);
	 	 if(opt==4) printf("%dn",query_val(root,x+1));
	 	 if(opt==5) printf("%dn",pre(x));
	 	 if(opt==6) printf("%dn",nex(x));
	 }
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}

Splay

特别注意:

  1. 查找 (x) 的前、后驱时要判断有无 (val)(x) 的节点!不能直接返回前、后驱。

  2. 记得每次操作进行中、进行后(视不同函数而定)(text{Splay})

  3. 清楚数组下标是节点编号,不是 (val)

  4. 及时 (text{update}) 更新信息

  5. 父子节点之间有双向的连接,缺一不可

  6. (text{kth}) 中)要判断查询的 $k $是否正好为 (siz[ls]+dots) 所以应该判断 (kle 0)

  7. (text{del}) 中)清楚 (root) 以及各种信息的更改顺序,防止在赋值之前信息已经被清空

  8. (text{del}) 中)删除有两个儿子的根节点是应该先 (text{Splay}) 前驱 (pre()) ,再连接右子树。

    • (在 (text{Splay(pre())}) 后,(pre()) 成为根的同时原先的根 (rt) 会成为根的右儿子,同时 (rt) 原先的右儿子会变为左儿子)
  9. (text{Rank}) 中)在没有 (val)(x) 的节点是返回 (1)

  10. (text{Rank}) 中)(rank) 是比 (x) 小的个数 (+1) !!!

  11. (text{Rank}) 中)查找节点时小心子节点是空的!此时直接返回

  12. (text{Splay}) 中)如果节点 (x) 已经在根节点,不需要修改。

  13. (text{Splay},dots) 中)及时更新 (root)

P6136 【模板】普通平衡树(数据加强版)

$text{Splay}$ 模板代码
#include<bits/stdc++.h>
using namespace std;
#define infll 0x7f7f7f7f7f7f7f7fll
#define inf 0x7f7f7f7f
#define Maxn 2000005
typedef long long ll;
inline int rd()
{
	 int x=0;
     char ch,t=0;
     while(!isdigit(ch = getchar())) t|=ch=='-';
     while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
     return x=t?-x:x;
}
ll maxll(ll x,ll y){ return x>y?x:y; }
ll minll(ll x,ll y){ return x<y?x:y; }
ll absll(ll x){ return x>0ll?x:-x; }
int n,m,root,tot;
ll ans;
int a[Maxn];
int ch[Maxn][2],fa[Maxn];
struct Splay
{
	 ll val;
	 int cnt,siz;
	 int laz;
}tree[Maxn];
int get(int x) { return x==ch[fa[x]][1]; }
void clear(int x) { ch[x][0]=ch[x][1]=fa[x]=tree[x].cnt=tree[x].val=tree[x].siz=0; }
void pushup(int x) { tree[x].siz=tree[ch[x][0]].siz+tree[ch[x][1]].siz+tree[x].cnt; }
void rotate(int x)
{
	 int y=fa[x],z=fa[y],k=get(x);
	 ch[y][k]=ch[x][k^1];
	 if(ch[x][k^1]) fa[ch[x][k^1]]=y;
	 fa[y]=x,ch[x][k^1]=y;
	 fa[x]=z;
	 if(z) ch[z][y==ch[z][1]]=x;
	 pushup(y),pushup(x);
}
void splay(int x,int rt=0)
{
	 if(x==rt) return;
	 for(int f=fa[x];f!=rt;rotate(x),f=fa[x])
	 	 if(fa[f]!=rt) rotate((get(f)==get(x))?f:x);
	 if(!rt) root=x;
}
void pushdown(int x)
{
	 if(tree[x].laz) // 根据不同题目而定 暂时未更新 
	 {
	 }
}
int pre()
{
	 int ret=ch[root][0];
	 while(ch[ret][1]) ret=ch[ret][1];
	 return ret; 
}
int nex()
{
	 int ret=ch[root][1];
	 while(ch[ret][0]) ret=ch[ret][0];
	 return ret;
}
ll kth(int k)
{
	 int cur=root;
	 while(1)
	 {
	 	 pushdown(cur);
	 	 if(ch[cur][0] && k<=tree[ch[cur][0]].siz) cur=ch[cur][0];
	 	 else
	 	 {
	 	 	 k-=tree[cur].cnt+tree[ch[cur][0]].siz;
	 	 	 if(k<=0) break;
	 	 	 cur=ch[cur][1];
		 }
	 }
	 return tree[cur].val;
}
int Rank(ll x)
{
	 int ret=0,cur=root;
	 while(1)
	 {
	 	 if(x<tree[cur].val)
	 	 {
	 	 	 if(!ch[cur][0]) { ret+=1; break;  }
	 	 	 cur=ch[cur][0];
		 }
	 	 else if(x==tree[cur].val) { ret+=tree[ch[cur][0]].siz+1; break; }
	 	 else
	 	 {
	 	 	 ret+=tree[ch[cur][0]].siz+tree[cur].cnt;
	 	 	 if(!ch[cur][1]) { ret+=1; break; }
	 	 	 cur=ch[cur][1];
		 }
	 }
	 splay(cur);
	 return ret?ret:1;
}
void Insert(ll x)
{
	 int cur=root,f=0;
	 while(cur && tree[cur].val!=x) f=cur,cur=ch[cur][x>tree[cur].val];
	 if(cur) tree[cur].cnt++;
	 else
	 {
	 	 cur=++tot;
	 	 if(f) ch[f][x>tree[f].val]=cur;
	 	 clear(cur);
	 	 tree[cur].val=x,fa[cur]=f;
	 	 tree[cur].siz=tree[cur].cnt=1;
	 }
	 splay(cur);
}
void Del(ll x)
{
	 Rank(x);
	 int cur=root;
	 if(tree[root].cnt>1) tree[root].cnt-=1,pushup(root);
	 else if(!ch[root][0] && !ch[root][1]) clear(root),root=0;
	 else if(!ch[root][0]) root=ch[root][1],fa[root]=0,clear(cur);
	 else if(!ch[root][1]) root=ch[root][0],fa[root]=0,clear(cur);
	 else
	 {
	 	 int Last=pre();
	 	 splay(Last);
		 ch[Last][1]=ch[cur][1];
	 	 fa[ch[cur][1]]=Last;
		 clear(cur);
		 pushup(Last);
	 }
}
void print(int p)
{
	 pushdown(p);
	 if(ch[p][0]) print(ch[p][0]);
	 printf("%dn",tree[p].val);
	 if(ch[p][1]) print(ch[p][1]);
}
int main()
{
     //freopen(".in","r",stdin);
     //freopen(".out","w",stdout);
	 n=rd(),m=rd();
	 for(int i=1;i<=n;i++) scanf("%lld",&a[i]),Insert(a[i]);
	 ll x,Last=0;
	 for(int i=1,opt,tmp;i<=m;i++)
	 {
	 	 opt=rd(),scanf("%lld",&x),x^=Last;
	 	 if(opt==1) Insert(x);
		 if(opt==2) Del(x);
	 	 if(opt==3) Last=Rank(x),ans^=Last;
		 if(opt==4) Last=kth(x),ans^=Last;
	 	 if(opt==5)
		 {
		 	 Rank(x);
			 if(tree[root].val>=x) Last=tree[pre()].val,ans^=Last;
			 else Last=tree[root].val,ans^=Last;
		 }
		 if(opt==6)
		 {
		 	 Rank(x);
			 if(tree[root].val<=x) Last=tree[nex()].val,ans^=Last;
			 else Last=tree[root].val,ans^=Last;
		 }
	 }
	 printf("%lldn",ans);
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}

应用 (rightarrow) (text{LCT}) 预备知识 P3391 【模板】文艺平衡树


替罪羊树

咕咕咕


红黑树

咕咕咕


SBT

咕咕咕


程序员灯塔
转载请注明原文链接:平衡树
喜欢 (0)