[怎么用C++自带的指针写数据结构？]
[不会……那就快点学！不要颓！]
第一次用指针完成高级数据结构の[Splay] Splay食用须知 首先，我们要理解什么是Splay树。Splay树是一棵二叉搜索树：二叉搜索树，用LJ的话讲，就是“左边比它小，右边比他大”。我们考虑这样一棵树，树上的任意一个节点满足“他的左子树上的每一个节点的值都比该节点的值小，他的右子树上的每一个节点的值都比该节点的值大”。就像这样：
如果这棵二叉搜索树是完全二叉树的话，很显然，查找一个值的时间是O(logn)。但是万一数据使这棵树被构造成一条链的话(例如最小的元素为根节点，次小的元素是它的左节点，以此类推)，查询一个值的时间复杂度会退化为O(n)，你就会获得0分的好成绩。
那么Splay树如何解决这个问题呢？旋转！每一次操作都旋转！跳跃！闭着眼！把节点旋转到根！在这里，我们把将某一个节点旋转到另一个位置，并且使这棵树保留原来的性质的操作，称为Splay。旋转降低复杂度(玄学)，对OIer来讲是无须证明，只要记住就好了，(如果你一定要看证明 ，你会回来的)。可以感性理解一下，每次操作改变一次结构，被查询频率高的条目会更靠近树根，时间有多有少，平均下来复杂度就会比较低（另外，Splay操作是单旋还是双旋也会影响到复杂度）。
成员变量 我们先考虑Splay树上每一个点应该包含这几个成员变量：
1 2 3 4 5 6 7 8 9 10 11 class node {public : int val,cnt,siz; node* fth; node* son[2 ]; node(int v=0 ,node *f=NULL ){ val=v;fth=f; son[0 ]=son[1 ]=NULL ; cnt=siz=0 ; } }
val:该点的值 cnt:值为该点的值的个数 siz:包括该点与其左右子树的大小
fth:爸爸指向该点的父节点的指针 son:指向该点的左右子节点的指针([0]左[1]右)
Rotate[单旋] 现在我们考虑将一个点旋转到它的父节点的位置:我们称其为Rotate。左子节点旋转到父节点称为右旋，右子节点旋转到父节点称为左旋。
在看Rotate的具体步骤之前，我们先介绍这个函数：
1 2 3 bool sn (void ) return (fth->son[1 ]==this ); }
(注:这个函数是node这个类的成员函数，this是指向自己的指针，可以删去，下面的Rotate函数和Splay函数同理，不清楚可以看文章最后的全代码)
这个函数Sn可以方便地判断this是其父节点的哪个儿子，并返回该儿子的下标。
1 2 3 4 5 6 7 8 9 10 11 12 13 void rotate (void ) node *y=this ->fth; bool a=this ->sn(); y->son[a]=this ->son[!a]; if (this ->son[!a]!=NULL ) this ->son[!a]->fth=y; this ->fth=y->fth; if (y->fth!=NULL ) y->fth->son[y->sn()]=this ; this ->son[!a]=y; y->fth=this ; y->updata(),this ->updata(); }
其中注意，我们可以通过Sn()这个函数判断this是它父节点的哪一个子节点，以此来判断是左旋还是右旋，就不用累赘地写两个函数了。
这样，我们就完成单旋了。单旋Splay就是对某一个节点疯狂做单旋直到它变到目标位置。在多年(我考了十八年NOIP了，连复赛的机子都没摸到过)OI学习中，我们可以感觉到，做事不·能太暴力，单旋Splay是不能彻底改变树的结构的，(稍微卡一卡就咕咕)，于是我们引入了：“双旋Splay”，来彻底做到玄学复杂度。
Splay[双旋]
我们先观察上面的两张图，这次我们要考虑x(this)节点的父亲节点和祖父节点，分别命名为P，Q。如果x和p是同一种子节点(左/右子节点)，执行Zig-Zig操作，将x旋转到Q的位置，反之，执行Zig-Zag操作，将x旋转到Q的位置。这样子旋转两次直到x被旋转到目标节点——这就是双旋Splay。每次做两个Rotate操作，但是要注意的是，如果x与目标节点的深度只差1时，只用执行一次Rotate操作就可以了。(这样就可以保证复杂度的玄学了！)
Zig-Zig操作：先旋转P节点，再旋转X节点；
Zig-Zag操作：旋转两次X节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 bool splay (node* y=NULL ) while (this ->fth!=y){ if (this ->fth==NULL ) return false ; node *p=this ->fth; if (p->fth==y || p->fth==NULL ){ this ->rotate(); continue ; } node *q=p->fth; if (this ->sn()!=p->sn()){ this ->rotate(); this ->rotate(); } else { p->rotate(); this ->rotate(); } } return true ; }
(这里我们考虑返回Bool值，在x转不到目标节点的情况能做出判断，用处不大)
这样子，我们的类-Node就打好了！这样就完成了一个Splay的框架。
类Node的完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class node {public : int val,cnt,siz; node* fth; node* son[2 ]; node(int v=0 ,node *f=NULL ){ val=v;fth=f; son[0 ]=son[1 ]=NULL ; cnt=siz=0 ; } private : bool sn (void ) return (fth->son[1 ]==this ); } void rotate (void ) node *y=this ->fth; bool a=this ->sn(); y->son[a]=this ->son[!a]; if (this ->son[!a]!=NULL ) this ->son[!a]->fth=y; this ->fth=y->fth; if (y->fth!=NULL ) y->fth->son[y->sn()]=this ; this ->son[!a]=y; y->fth=this ; } public : bool splay (node* y=NULL ) while (this ->fth!=y){ if (this ->fth==NULL ) return false ; node *p=this ->fth; if (p->fth==y || p->fth==NULL ){ this ->rotate(); continue ; } node *q=p->fth; if (this ->sn()!=p->sn()){ this ->rotate(); this ->rotate(); } else { p->rotate(); this ->rotate(); } } return true ; } };
Insert[插入] [在一个二叉搜索树中如何插入一个新的节点？]
[找到你的归宿，一层一层剥开。]
对于一个Splay树，我们只记录他的根节点，由root指针指向。所以做什么操作，都要从源头开始。从根出发，如果比根大，就往根的右子树里找，如果比根小，就往根的左子树找。
在树状结构中，这样的查找是不是让人很想用递归实现啊？
1 2 3 4 5 6 7 8 9 10 11 12 13 void _insert(int v,node *p,node *f){ if (p==NULL ){ p=new node(v,f); p->splay(); root=p; return ; } if (v==p->val){ p->cnt++; return ; } if (v<p->val) _insert(v,p->son[0 ],p); if (v>p->val) _insert(v,p->son[1 ],p); }
但是其实可以用循环实现哦~这样子调用函数，传入多个参数，又慢又丑陋，不如这样写:
1 2 3 4 5 6 7 8 9 10 11 12 13 void insert (int v) if (root==NULL ) root=new node(v,NULL ); for (node *t=root;;t=t->son[v>=t->val]){ if (t->val==v){ root=t; t->cnt++; t->splay(); return ; } if (t->son[v>=t->val]==NULL ){ t->son[v>=t->val]=new node(v,t); } } }
如果原有该值的点，则直接cnt++，如果没有，则new一个新的点再cnt++。
(不管怎么样，操作中都要Splay操作结点)
Find[查找] 从root往下找，走向son[v>t->val]——当v大于当前节点的val时，返回1：走向右子树；当v小于当前节点的val时，返回0：走向左子树。
1 2 3 4 5 6 7 8 9 10 node* find (int v) { for (node* t=root;t;t=t->son[v>t->val]){ if (t->val==v){ t->splay(); root=t; return t; } } return NULL ; }
Erase[删除] 先Splay要删去的节点——好，现在我们要删去的节点在根节点上。
接下来，在他的左子树中找到最大的那个节点，（如果没有左子树的话就直接删去根节点就行了），将那个节点Splay到根节点的右子节点，那么此时这个节点是没有右子树的——将根节点的左子树指向这个节点，干脆利落地删除根节点，删除操作完成！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 bool erase (int v,int cnt=1 ) node *t=find(v); if (t==NULL ){ return false ; } if (t->cnt>cnt){ t->cnt-=cnt; return true ; } if (t->son[0 ]==NULL ){ root=t->son[1 ]; if (root!=NULL ) root->fth=NULL ; return true ; } node *p=t->son[0 ]; while (p->son[1 ]!=NULL ) p=p->son[1 ]; p->splay(t); root=p; root->fth=NULL ; p->son[1 ]=t->son[1 ]; if (p->son[1 ]!=NULL ) p->son[1 ]->fth=p; return true ; }
size[子树大小] 在这里，我们在node类中引入updata函数，在Rotate操作中将改变的size值更新。
1 2 3 4 void updata (void ) siz=(son[0 ]?son[0 ]->siz:0 ) +(son[1 ]?son[1 ]->siz:0 )+cnt; }
这是改变后的Rotate操作：
1 2 3 4 5 6 7 8 9 10 11 12 13 void rotate (void ) node *y=this ->fth; bool a=this ->sn(); y->son[a]=this ->son[!a]; if (this ->son[!a]!=NULL ) this ->son[!a]->fth=y; this ->fth=y->fth; if (y->fth!=NULL ) y->fth->son[y->sn()]=this ; this ->son[!a]=y; y->fth=this ; y->updata(),this ->updata(); }
那么返回一个节点及其子树的Size就非常简单了。
1 2 3 4 5 6 int size(void){ return root->siz; } int size(node* x){ return x->siz; }
Kth[第K大数] 如果K在根节点的cnt区间内，则返回根节点;
如果K在左子树区间内，递归处理左子树;
如果K在右子树区间内，将在之后的递归中加入当前左子树和根节点的值，递归处理右子树。
递归处理，简单明了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int kth (int key) int cnt=0 ; if (key>root->siz) return -1 ; for (node* i=root;i;){ int lcnt=(i->son[0 ])?i->son[0 ]->siz:0 ; int mcnt=i->cnt; if (cnt+lcnt<key && cnt+lcnt+mcnt>=key){ i->splay(); return i->val; } if (cnt+lcnt>=key) i=i->son[0 ]; if (key>cnt+lcnt+mcnt){ cnt+=lcnt+mcnt; i=i->son[1 ]; } } }
Next[前驱/后继] 找前驱，在该节点的左子树中向右子树找，找出左子树中最大的节点。
找前驱，在该节点的右子树中向左子树找，找出右子树中最小的节点。
1 2 3 4 5 6 7 node* next (node* x,int s) { node* t=x->son[s]; if (!t) return NULL ; while (t->son[s^1 ]) t=t->son[s^1 ]; t->splay(); return t; }
与Find函数结合，可以先找到该节点，再进行Next操作。
1 2 3 4 5 6 7 int next (int ix,int s) node* x=find(ix); node* t=x->son[s]; if (!t) return -1 ; while (t->son[s^1 ]) t=t->son[s^1 ]; return t->val; }
Main[主程序] 这样，我们的Splay就支持了以下操作：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 int n,tmp,z;string s;Splay tr; int main (void ) for (;;){ cin >>s; if (s=="erase" ){ cin >>tmp; tr.erase(tmp); tr.print(); } if (s=="insert" ){ cin >>tmp; tr._insert(tmp,tr.root,NULL ); tr.print(); } if (s=="find" ){ cin >>tmp; if (tr.find(tmp)) cout <<"true\n" ; else cout <<"false\n" ; tr.print(); } if (s=="size" ){ cout <<tr.size()<<endl ; tr.print(); } if (s=="kth" ){ cin >>tmp; cout <<tr.kth(tmp)<<endl ; tr.print(); } if (s=="next" ){ cin >>tmp>>z; cout <<tr.next(tmp,z)<<endl ; tr.print(); } if (s=="exit" ){ return 0 ; } } }
完整程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 #include <bits/stdc++.h>//祈福无Bug using namespace std ;struct node {public : int val,cnt,siz; node* fth; node* son[2 ]; node(int v=0 ,node *f=NULL ){ val=v;fth=f; son[0 ]=son[1 ]=NULL ; cnt=siz=0 ; } private : bool sn (void ) return (fth->son[1 ]==this ); } void updata (void ) siz=(son[0 ]?son[0 ]->siz:0 ) +(son[1 ]?son[1 ]->siz:0 )+cnt; } void rotate (void ) node *y=this ->fth; bool a=this ->sn(); y->son[a]=this ->son[!a]; if (this ->son[!a]!=NULL ) this ->son[!a]->fth=y; this ->fth=y->fth; if (y->fth!=NULL ) y->fth->son[y->sn()]=this ; this ->son[!a]=y; y->fth=this ; y->updata(),this ->updata(); } public : bool splay (node* y=NULL ) while (this ->fth!=y){ if (this ->fth==NULL ) return false ; node *p=this ->fth; if (p->fth==y || p->fth==NULL ){ this ->rotate(); continue ; } node *q=p->fth; if (this ->sn()!=p->sn()){ this ->rotate(); this ->rotate(); } else { p->rotate(); this ->rotate(); } } return true ; } }; struct Splay { node *root; Splay(node *p=NULL ){ root=NULL ; } int size (void ) return root->siz; } int size (node* x) return x->siz; } void _print(node *x){ if (x==NULL ) return ; cout <<x->val<<" " ; if (x->son[0 ]!=NULL ) cout <<"Left:" <<x->son[0 ]->val<<" " ; else cout <<"Left:NULL " ; if (x->son[1 ]!=NULL ) cout <<"Right:" <<x->son[1 ]->val<<" " ; else cout <<"Right:NULL " ; cout <<"\n" ; _print(x->son[0 ]);_print(x->son[1 ]); } void print (void ) _print(root); } void insert (int v=0 ) if (root==NULL ) root=new node(v,NULL ); for (node *t=root;;t=t->son[v>=t->val]){ if (t->val==v){ root=t; t->cnt++; t->splay(); return ; } if (t->son[v>=t->val]==NULL ){ t->son[v>=t->val]=new node(v,t); } } } void _insert(int v,node *p,node *f){ if (p==NULL ){ p=new node(v,f); p->splay(); root=p; return ; } if (v<p->val) _insert(v,p->son[0 ],p); if (v==p->val){ p->cnt++; return ; } if (v>p->val) _insert(v,p->son[1 ],p); } node* find (int v) { for (node* t=root;t;t=t->son[v>t->val]){ if (t->val==v){ t->splay(); root=t; return t; } } return NULL ; } bool erase (int v,int cnt=1 ) node *t=find(v); if (t==NULL ){ return false ; } if (t->cnt>cnt){ t->cnt-=cnt; return true ; } if (t->son[0 ]==NULL ){ root=t->son[1 ]; if (root!=NULL ) root->fth=NULL ; return true ; } node *p=t->son[0 ]; while (p->son[1 ]!=NULL ) p=p->son[1 ]; p->splay(t); root=p; root->fth=NULL ; p->son[1 ]=t->son[1 ]; if (p->son[1 ]!=NULL ) p->son[1 ]->fth=p; return true ; } int kth (int key) int cnt=0 ; if (key>root->siz) return -1 ; for (node* i=root;i;){ int lcnt=(i->son[0 ])?i->son[0 ]->siz:0 ; int mcnt=i->cnt; if (cnt+lcnt<key && cnt+lcnt+mcnt>=key){ i->splay(); return i->val; } if (cnt+lcnt>=key) i=i->son[0 ]; if (key>cnt+lcnt+mcnt){ cnt+=lcnt+mcnt; i=i->son[1 ]; } } } node* next (node* x,int s) { node* t=x->son[s]; if (!t) return NULL ; while (t->son[s^1 ]) t=t->son[s^1 ]; t->splay(); return t; } int next (int ix,int s) node* x=find(ix); node* t=x->son[s]; if (!t) return -1 ; while (t->son[s^1 ]) t=t->son[s^1 ]; return t->val; } }; int n,tmp,z;string s;Splay tr; int main (void ) for (;;){ cin >>s; if (s=="erase" ){ cin >>tmp; tr.erase(tmp); tr.print(); } if (s=="insert" ){ cin >>tmp; tr._insert(tmp,tr.root,NULL ); tr.print(); } if (s=="find" ){ cin >>tmp; if (tr.find(tmp)) cout <<"true\n" ; else cout <<"false\n" ; tr.print(); } if (s=="size" ){ cout <<tr.size()<<endl ; tr.print(); } if (s=="kth" ){ cin >>tmp; cout <<tr.kth(tmp)<<endl ; tr.print(); } if (s=="next" ){ cin >>tmp>>z; cout <<tr.next(tmp,z)<<endl ; tr.print(); } if (s=="exit" ){ return 0 ; } } }
下一篇文章:Splay区间操作[ft.指针]，过几天会咕咕咕地更新哦。
コメント