【模板篇】splay(填坑)+模板题(普通平衡树)

划着划着水一不小心NOIP还考的凑合了…

所以退役的打算要稍微搁置一下了…

要准备准备省选了….

但是自己已经啥也不会了…

所以只能重新拾起来…

从splay开始吧…

splay我以前扔了个板子来着, 之前理解的还是不够深入于是就一直没有填坑…

现在又重新拾了一下就来填坑…

不过讲平衡树要画好多图的说OvO

BST(二叉查找树)大家应该都知道吧, 所以就不讲了…

大家也都知道BST会被卡成一条链, 复杂度动不动就退化成 O(n)

所以就出现了各种各样的二叉平衡树…

splay是个很年轻的数据结构…好像是什么1985年由tarjan提出的…

splay的主要特点就是不怎么平衡, 但是一直在转所以深度并不会太深…

而且会将最近访问的条目放在根的附近, 这样重复访问的时候效率会加快..

(听上去好像挺有用, 但实际生活更多用的还是RBT之类的吧?)

splay的主要操作就是rotate和splay(招牌)的说…

其他的操作就是BST的操作了Emmmm…

我们一个一个讲:

rotate

rotate跟很多其他什么二叉平衡树是一样的…

由题意, 如图示, 尽管箭头画的丑的一笔大小都不一样但是凑合着看吧…旋转完还是保持二叉排序树性质的~

我们来分析一下旋转的过程

假如我们要旋转4号节点(下面称为 x <script type="math/tex" id="MathJax-Element-11">x</script>), 就是上面左图箭头指的那个节点..

因为他是左儿子, 所以要右旋(有些人喜欢分左右旋, 但是你把左儿子左旋是几个意思←_←)

然后就是中图红色和绿色的拆边和建边:

说明好麻烦啊, 上伪代码吧:

if grandfa->ch[0]==fa fa_dir=0 else fa_dir=1 //确定父亲是祖父的哪个儿子grandfa->ch[fa_dir]=x //将这个儿子置为xif fa->ch[0]==x dir=0 else dir=1 //确定x是父亲的哪个儿子fa->ch[dir]=x->ch[dir^1] //将x父亲的dir儿子置为x的dir另一侧的儿子 (为了保持性质,这很显然)x->ch[dir^1]=fa //将x变为x原来父亲的父亲(没大没小..) (为了保持性质,要放在dir的对侧)//当然这里要更新所有改变父子关系中所有的父亲咯~

以上几步如果不乱的话应该顺序是无所谓的吧…(不过还是形成一个正确的板子背过的好, 不然老是挂(这几天都不知道把rotate里面的句子调了多少遍了))

然后我们就能整理出这样的代码:

void rotat(node *now){ //这里强行去掉一个e是防止与STL冲突(虽然好像无所谓??)int wh=now->getwh(); node *fa=now->fa,*fafa=fa->fa;if(fafa!=null) fafa->ch[fa->getwh()]=now;fa->setch(wh,now->ch[wh^1]); now->setch(wh^1,fa); //这里的setch是包括设置儿子和父亲的now->fa=fafa;}

rotate就是这样…

其实自己多画一画就比较方便理解…

splay

splay之所以叫splay是因为splay有个叫splay的操作..(绕口令)

我们说过, splay会把最近访问的点转到根上…(其实就是伸个懒腰….把这个点扭上去)

这里的splay操作有一种很显然的做法: 就是不停的rotate

这种操作叫做单旋(敲黑板) 这么显然的做法显然是会被卡的…比如转着转着就特别特别不平衡了什么的…

(丧心病狂的出题人可能会先问这个端点, 再问那个端点, 就炸了…)

这么写的做法我们亲切地称为spaly(来找不同啊)

所以我们为了保持比较平衡的splay(其实仍然歪七扭八的…) 我们要双旋(又敲黑板)

Emmmm

双旋的过程, 我们要判断x和x的父亲是不是同向的(即都是自己父亲的左儿子or右儿子)

- 如果是同向的, 就要先转父亲再转x

- 否则转2遍x…

其实为什么这样做还是挺明显的, 可以自己画一下rotate的过程看看不同的顺序会对平衡产生什么差异(才不是懒得画呢╭(╯^╰)╮)

由于rotate已经写好了, 我们的splay就呼之欲出了

//将节点now转到tar的下一位上(Emmmm..这个地方划重点,不是转到tar上哦~) 若tar为null则表示转到根上void splay(node *now,node *tar){for(;now->fa!=tar;rotat(now)) //因为不是转到tar上所以是fa!=tar...if(now->fa->fa!=tar) //防止双旋转过,如果只转一下就到那就不双旋了//反正双旋的第二步都是转我们就只转第一步就好了(因为第二步被压到for循环里去了2333)now->getwh()==now->fa->getwh()?rotat(now->fa):rotat(now);if(tar==null) rt=now; //转到根上就要重置根...}

反正就是这样… 剩下的就是bst的操作了OvO

用其他的什么树也都能搞定了OvO

例题的话我们就用普通平衡树吧OvO 门

我们来逐个分析操作:

1.插入一个数x

这不是bst操作么… 用从根开始找到该插入的位置插入即可…

void insert(int val){node *last = null, *now = rt, *nnow = NEW(); //NEW是自定义函数(不太会重载new)nnow->val = val; nnow->cnt = nnow->sz = 1; //申请新节点while (now != null){last = now; //last存储父亲if (nnow->val == now->val){ //如果树上已经有了数值相同的点now->cnt++; now->sz++; //直接修改cnt和size就行了splay(now, null); return; //把最近访问的节点旋到根上}if (nnow->val<now->val) now = now->ch[0]; //如果比当前节点值小显然要往左走else now = now->ch[1]; //否则往右走}if (last == now) rt = nnow; //如果没有根当前点就是根else if (nnow->val<last->val) last->setch(0, nnow); //如果小于最后走到的位置就设为左叶子else last->setch(1, nnow); //否则右叶子splay(nnow, null); //转到根上}

2.删除数x

在此之前我们要先找到x是不是OvO…

所以……bst的查找!!!

node *find(int val){node *now = rt;while (now != null){if (now->val == val) break; //找到了if (now->val<val) now = now->ch[1]; //当前节点小于要查询的值 往右走 else now = now->ch[0]; //否则往左走}if (now != null) splay(now, null); //找到了就转到根上return now;}

找到这个点的位置之后删掉就完了OvO.. 不过要分类讨论(注意这里并没有回收内存所以并不是真的删掉了OvO 如果开始的时候里面有点那要池子要开双倍的)

void delet(int val){ //不要问我为啥去个e... delete是关键字啊= =node *tar = find(val); //找到的时候就旋到根上了 这就很和善..if (tar == null) return; //没找到删个毛线啊if (tar->cnt>1){tar->cnt--; tar->sz--; return; //如果是重复的减去一个就行了很省事..}//无聊的分类讨论if (tar->ch[0] == null&&tar->ch[1] == null)rt = null; //如果这就是根 删了就完了else if (tar->ch[0] == null)tar->ch[1]->fa = null, rt = tar->ch[1]; //如果没有左子树,直接将右儿子作为根else if (tar->ch[1] == null)tar->ch[0]->fa = null, rt = tar->ch[0]; //如果没有右子树,直接将左儿子作为根else{ //左右儿子都有是最麻烦 但是最常见的..node *rch = tar->ch[0];while (rch->ch[1] != null) rch = rch->ch[1]; //我们要找到左儿子中最右的儿子来当新根...splay(rch, null); //把这个点转到根上rch->setch(1, tar->ch[1]); //把右儿子接到上面rch->fa = null; rt = rch; //更新一下新根信息}}

3.查询x数的排名

这个嘛= = 我们要维护每个点子树的大小…

我们写一个update函数…

void node::update(){sz=ch[0]->sz+ch[1]->sz+cnt; //左子树大小+右子树大小+该数值的个数}

只要改变树形态(修改儿子的时候)调用就好了…(常数在哭泣…)

查排名的时候就可以:

int rank(int val){int ls = 0; //记录比走到当前节点前一定更小的数的个数..node *now = rt;while (now != null){if (now->val == val){//找到这个值就把小的数的个数和他左子树的大小+1作为名次..int ans = ls + now->ch[0]->sz + 1;//把当前查询的点转到根上..splay(now, null);return ans;}//还是比较大小然后分往左右走..if (now->val<val) ls += now->ch[0]->sz + now->cnt, now = now->ch[1];else now = now->ch[0];}return -1;}

4.查排名为x的数

不想写文字说明了OvO

int pos(int k){int ls = 0; node *now = rt;while (now != null){int po = ls + now->ch[0]->sz;if (po + 1 <= k&&k <= po + now->cnt){splay(now, null); return now->val; //如果当前点符合要求就是他了(记得转到根上)}//还是判断左右...if (po<k) ls = po + now->cnt, now = now->ch[1];else now = now->ch[0];}return -1;}

5.查询前驱(后继一样我就一起写了)

int pre(int val){int ans = -INF; node *now = rt;while (now != null){//一路左右找就行...反正相等也不满足条件...if (now->val<val)ans = max(ans, now->val), now = now->ch[1];else now = now->ch[0];}return ans;}int nxt(int val){int ans = INF; node *now = rt;while (now != null){if (now->val <= val) now = now->ch[1];else ans = min(ans, now->val), now = now->ch[0];}return ans;}

就这样咯~ 下面附上完整的代码:

#include <cstdio>const int N = 100010;const int INF = ~0U >> 1;inline int gn(int a = 0, char c = 0, int f = 1){for (; (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') c = getchar(), f = -1;for (; c >= '0'&&c <= '9'; c = getchar()) a = a * 10 + c - '0'; return a*f;}inline int max(const int &a, const int &b){ return a>b ? a : b; }inline int min(const int &a, const int &b){ return a<b ? a : b; }struct node{int sz, val, cnt;node *ch[2], *fa;void update();int getwh();void setch(int wh, node *child);}*rt, *null, pool[N]; int tot = 0;void node::update(){sz = ch[0]->sz + ch[1]->sz + cnt;}int node::getwh(){return fa->ch[0] == this ? 0 : 1;}void node::setch(int wh, node *child){ch[wh] = child;if (child != null) child->fa = this;update();}node *NEW(){node *now = pool + ++tot;now->sz = now->cnt = now->val = 0;now->ch[0] = now->ch[1] = now->fa = null;return now;}void init(){null = pool;null->ch[0] = null->ch[1] = null;null->cnt = null->sz = null->val = 0;rt = null;}void rotate(node *now){node *fa = now->fa, *fafa = fa->fa;int wh = now->getwh();if (fafa != null) fafa->ch[fa->getwh()] = now;fa->setch(wh, now->ch[wh ^ 1]);now->setch(wh ^ 1, now->fa);now->fa = fafa;}void splay(node *now, node *tar){for (; now->fa != tar; rotate(now))if (now->fa->fa != tar)now->getwh() == now->fa->getwh() ? rotate(now->fa) : rotate(now);if (tar == null) rt = now;}node *find(int val){node *now = rt;while (now != null){if (now->val == val) break;if (now->val<val) now = now->ch[1];else now = now->ch[0];}if (now != null) splay(now, null);return now;}void insert(int val){node *last = null, *now = rt, *nnow = NEW();nnow->val = val; nnow->cnt = nnow->sz = 1;while (now != null){last = now;if (nnow->val == now->val){now->cnt++; now->sz++;splay(now, null); return;}if (nnow->val<now->val) now = now->ch[0];else now = now->ch[1];}if (last == now) rt = nnow;else if (nnow->val<last->val) last->setch(0, nnow);else last->setch(1, nnow);splay(nnow, null);}void delet(int val){node *tar = find(val);if (tar == null) return;if (tar->cnt>1){tar->cnt--; tar->sz--; return;}//无聊的分类讨论if (tar->ch[0] == null&&tar->ch[1] == null)rt = null;else if (tar->ch[0] == null)tar->ch[1]->fa = null, rt = tar->ch[1];else if (tar->ch[1] == null)tar->ch[0]->fa = null, rt = tar->ch[0];else{node *rch = tar->ch[0];while (rch->ch[1] != null) rch = rch->ch[1];splay(rch, null);rch->setch(1, tar->ch[1]);rch->fa = null; rt = rch;}}int pre(int val){int ans = -INF; node *now = rt;while (now != null){if (now->val<val)ans = max(ans, now->val), now = now->ch[1];else now = now->ch[0];}return ans;}int nxt(int val){int ans = INF; node *now = rt;while (now != null){if (now->val <= val) now = now->ch[1];else ans = min(ans, now->val), now = now->ch[0];}return ans;}int rank(int val){int ls = 0; node *now = rt;while (now != null){if (now->val == val){int ans = ls + now->ch[0]->sz + 1; splay(now, null);return ans;}if (now->val<val) ls += now->ch[0]->sz + now->cnt, now = now->ch[1];else now = now->ch[0];}return -1;}int pos(int k){int ls = 0; node *now = rt;while (now != null){int po = ls + now->ch[0]->sz;if (po + 1 <= k&&k <= po + now->cnt){splay(now, null); return now->val;}if (po<k) ls = po + now->cnt, now = now->ch[1];else now = now->ch[0];}return -1;}void debugtree(node *nod){if (nod->ch[0] != null) debugtree(nod->ch[0]);printf("%d\n", nod->val);if (nod->ch[1] != null) debugtree(nod->ch[1]);}int main(){init(); int n = gn();for (int i = 1; i <= n; ++i){int opt = gn(), x = gn();switch (opt){case 1:insert(x);break;case 2:delet(x); break;case 3:printf("%d\n", rank(x)); break;case 4:printf("%d\n", pos(x)); break;case 5:printf("%d\n", pre(x)); break;case 6:printf("%d\n", nxt(x)); break;}//puts("*********");//debugtree(rt);}}

就这样吧…

终于把自己挖的坑填上了…

自己挖的坑跪着也要填完。。(累觉不爱