织梦企业网站管理系统,山东网站推广有限公司,电商推广专业术语,加强服务保障满足群众急需i文章目录引入概念全套模板变量声明updaterotate旋转splay操作insert插入delete删除查找x的位置查找第k大前驱/后继极小值-inf和极大值inf的作用例题#xff1a;P3369 【模板】普通平衡树题目code声明一下#xff0c;许多代码的注解都在模板代码里面写了的#xff0c;所以正文…
文章目录引入概念全套模板变量声明updaterotate旋转splay操作insert插入delete删除查找x的位置查找第k大前驱/后继极小值-inf和极大值inf的作用例题P3369 【模板】普通平衡树题目code声明一下许多代码的注解都在模板代码里面写了的所以正文可能不会很多 其次是splaysplaysplay很多操作treaptreaptreap我都已经详解过了只需要掌握不一样的旋转板块即可
引入概念
在这之前大家要了解二叉搜索树或者treap再或者非旋treap也可以不了解我会再次尽全力详细的给大家讲懵splay 二叉搜索树是一种数据结构每个点都存有各自的键值按中序遍历这棵树按键值生成的序列是有序的 显而易见对于给定的序列nnn它的二叉搜索树不是唯一的 煮个栗子123451\ 2\ 3\ 4\ 51 2 3 4 5就能画出很多不一样的二叉搜索树 伸展树Splay Tree也叫分裂树是一种二叉排序树它能在O(logn)O(logn)O(logn)内完成插入、查找和删除操作 它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的 在伸展树上的一般操作都基于伸展操作 假设想要对一个二叉查找树执行一系列的查找操作为了使整个查找时间更小被查频率高的那些条目就应当经常处于靠近树根的位置 于是想到设计一个简单方法 在每次查找之后对树进行重构把被查找的条目搬移到离树根近一些的地方 伸展树应运而生 伸展树是一种自调整形式的二叉查找树它会沿着从某个节点到树根之间的路径通过一系列的旋转把这个节点搬移到树根去 它的优势在于不需要记录用于平衡树的冗余信息 假设想要对一个二叉查找树执行一系列的查找操作 为了使整个查找时间更小被查频率高的那些条目就应当经常处于靠近树根的位置 于是想到设计一个简单方法 在每次查找之后对树进行重构把被查找的条目搬移到离树根近一些的地方 splay tree应运而生。splay tree是一种自调整形式的二叉查找树它会沿着从某个节点到树根之间的路径通过一系列的旋转把这个节点搬移到树根去 ———————百度百科老师亲身授课讲懵一群中华少年 这张图太好看了忍不住盗过来 重点的就是模板模板的原理会在该模板板块介绍不要慌~~
全套模板 变量声明
我用的是结构体treetreetree方便学习LCTLCTLCT暴露了 后面的封装 tree[i].valtree[i].valtree[i].val表示该点的值 tree[i].cnttree[i].cnttree[i].cnt表示该点在树上的出现次数 tree[i].siztree[i].siztree[i].siz表示该点的子树大小包括自己在内 tree[i].ftree[i].ftree[i].f表示该点的爸爸诶真乖 tree[i].son[2]tree[i].son[2]tree[i].son[2]表示该点的两个儿子son[0]son[0]son[0]左儿子son[1]son[1]son[1]右儿子 这个没有什么值得讲的不同的题肯定会有添加或更改比如最大值就应该写成 tree[x].maxxmax(tree[tree[x].son[0]].maxx,tree[tree[x].son[1]].maxx,tree[x].val)tree[x].maxx max(tree[tree[x].son[0]].maxx,tree[tree[x].son[1]].maxx,tree[x].val)tree[x].maxxmax(tree[tree[x].son[0]].maxx,tree[tree[x].son[1]].maxx,tree[x].val) 这里以求和为例
update
void update ( int x ) {tree[x].siz tree[tree[x].son[0]].siz tree[tree[x].son[1]].siz tree[x].cnt;
}rotate旋转
在treaptreaptreap期间我们了解了单旋转只旋一次但是splaysplaysplay则是用双旋 接着因为是二叉树双旋就分为了两种情况直线型旋转和折线型旋转 直线型旋转即三点成一条直线 这种情况的旋转规则先旋转父亲再旋转自己 折线型旋转 这种情况的旋转规则旋转完自己再旋转自己自转两次 总结一张图
void rotate ( int x ) {//x是要旋转的点 int fa tree[x].f;//x的父亲(father缩写) int Gfa tree[fa].f;//x的祖父/fa的父亲(grandfather缩写(*^__^*))int k ( tree[fa].son[1] x );//x是fa的哪一个儿子 0左儿子 1右儿子if( Gfa) tree[Gfa].son[tree[Gfa].son[1] fa] x;//儿子非要当爹 取代了爹原来在祖父下的位置tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];if( tree[x].son[k ^ 1] ) tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );//别忘了更新信息update ( x );
}//0^11 1^10 其实也可以用取反(!)代替 splay操作
我们使用双旋的做法因为如果单旋将xxx旋到想要的位置毒瘤会卡到我们n2n^2n2 那么如果想旋转到根的话可以给第二个参数传0
void splay ( int x, int goal ) {//将x旋转到goal的儿子 如果goal是0意味着将x转到根while ( tree[x].f ! goal ) {int fa tree[x].f, Gfa tree[fa].f;if ( Gfa ! goal )//如果fa不是根节点就是两类(直线 折线)旋转( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );//有点技巧但也很好理解 前两坨^0就是直线的意思rotate ( x );}if ( ! goal )root x;//如果goal是0 将根节点更新为x
}insert插入
先用个动图直观感受一下 跟treaptreaptreap是孪生兄弟从根开始根据值的大小比较判断是往左走(xtree[root].valxtree[root].valxtree[root].val)还是往右走(xtree[root].valxtree[root].valxtree[root].val)
void insert ( int x ) {int u root, fa 0;//当前位置u及u的父节点fwhile ( u tree[u].val ! x ) {//仍有点且并未移动到想要的值 fa u;u tree[u].son[x tree[u].val];//x大于当前点的值就在右儿子里面找 否则向左找 }if ( u ) //已经建过x这个值的位置了 tree[u].cnt ;else {u Size;//新节点的位置 if ( fa ) tree[fa].son[x tree[fa].val] u;tree[u].son[0] tree[u].son[1] 0;//新点目前肯定没有儿子tree[u].val x;tree[u].f fa;tree[u].cnt tree[u].siz 1;}splay ( u, 0 );//把当前位置移到根保证结构平衡 因为前面更改了子树大小必须splay去update保证siz的正确
}delete删除
思路是首先分别找到xxx的前驱p1p1p1和后继p2p2p2那么在当前树上就满足p1xp2p1xp2p1xp2并且中间没有其它数 很妙的就是我们把p1p1p1旋转到根此时所有值比p1p1p1的都在右子树然后把p2p2p2旋转到p1p1p1的儿子处此时p2p2p2的左儿子就是xxx且只有一个因为p2p2p2的左子树要满足p1p1p1p2p2p2显而易见因为定义这里面只能插xxx那么直接对p2p2p2的左子树进行操作即可
void Delete ( int x ) {int pre PreSuf ( x, 0 ), suf PreSuf ( x, 1 );splay ( pre, 0 );splay ( suf, pre );//pre有可能为0 但这个时候suf就应该旋转到根int u tree[suf].son[0];if ( tree[u].cnt 1 ) {tree[u].cnt --;splay ( u, 0 );}elsetree[suf].son[0] 0, splay( suf, 0 );
}查找x的位置
我相信给个图大家就懂了 与插入是一个意思此处就不过多解释
void find ( int x ) {//查找x的位置并旋转到根节点 if ( ! root ) //树是空的return;int u root;while ( tree[u].son[x tree[u].val] x ! tree[u].val )//存在儿子并且当前点不是我们要找的 u tree[u].son[x tree[u].val];splay ( u, 0 );
}查找第k大
不要多说废话了不理解可以移步上面的treaptreaptreap讲解
int findkth ( int x ) {if ( tree[root].siz x )//整棵树的大小都没有k即不存在 return -1;int u root;while ( 1 ) {if ( x tree[tree[u].son[0]].siz )u tree[u].son[0];else if ( x tree[u].cnt tree[tree[u].son[0]].siz )return u;else {x - ( tree[tree[u].son[0]].siz tree[u].cnt );u tree[u].son[1];}}
}前驱/后继
前驱后继的思路很妙我们以前驱为例把xxx旋到根那么左子树就是比xxx小的然后就在左儿子里面一直往右儿子走likethis↓like\ this↓like this↓ 但是如果树上没有我们要找的xxx怎么办呢这个时候的树根究竟是什么根据我们findfindfind的原理写法可以知道我们一定是找的最接近于xxx的值不是它的前驱就是它的后继那么这个时候根就有可能是答案 我们就在findfindfind后加入两个特判
int PreSuf ( int x, int f ) {//f0找前驱 f1找后继 find ( x );//查找后因为splay此时树根就是要查询节点if ( tree[root].val x f )//如果当前节点的值大于x并且要查找的是后继因为find原因可以直接返回了 return root;if ( tree[root].val x ! f )//与找后继同理 return root;int u tree[root].son[f];if ( ! u )return 0;while ( tree[u].son[f ^ 1] )u tree[u].son[f ^ 1];return u;
}极小值-inf和极大值inf的作用
在没看到这个之前如果你就拿着模板跑了恭喜你流失了一天甚至更多的青春 因为上述模板都是在插入了哨兵的前提下才能运行的接下来让本蒟蒻来给你错误的讲讲哨兵的优秀
如果有哨兵存在那么这些点永远都不会是死在最前面或者死的时候垫在最下面就帮助我们少考虑很多边界我昨天没有加哨兵不停地补刀做手术还是千疮百孔病很多都是并发症医不过来加了个哨兵自己就好了
最后简单提一下封装的好处显然就是整个在一坨方便整体移动和调试。代码分层也很清晰。可以用结构体
struct node {里面放所有splay的操作
}T;
调用函数需要写成 T.insert() 之类的还可以
namespace splay {里面放所有splay操作
}
调用函数需要写成 splay :: insert() 之类的通常是题目解法涉及到多种算法时常按算法将各自模板进行封装。这样你可以很清楚地知道某个函数是属于哪一层的算法。
例题P3369 【模板】普通平衡树
题目
送你离开千里之外
code
#include cstdio
#define maxn 100005
#define INF 0x7f7f7f7f
struct node {int f, cnt, val, siz, son[2];
}tree[maxn];
int n, Size, root;void update ( int x ) {tree[x].siz tree[tree[x].son[0]].siz tree[tree[x].son[1]].siz tree[x].cnt;
}void rotate ( int x ) { int fa tree[x].f; int Gfa tree[fa].f;int k ( tree[fa].son[1] x );tree[Gfa].son[tree[Gfa].son[1] fa] x;tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );update ( x );
}void splay ( int x, int goal ) {while ( tree[x].f ! goal ) {int fa tree[x].f, Gfa tree[fa].f;if ( Gfa ! goal )( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}if ( ! goal )root x;
}void insert ( int x ) {int u root, fa 0;while ( u tree[u].val ! x ) {fa u;u tree[u].son[x tree[u].val]; }if ( u ) tree[u].cnt ;else {u Size; if ( fa ) tree[fa].son[x tree[fa].val] u;tree[u].son[0] tree[u].son[1] 0;tree[u].val x;tree[u].f fa;tree[u].cnt tree[u].siz 1;}splay ( u, 0 );
}void find ( int x ) {if ( ! root )return;int u root;while ( tree[u].son[x tree[u].val] x ! tree[u].val )u tree[u].son[x tree[u].val];splay ( u, 0 );
}int PreSuf ( int x, int f ) { find ( x );if ( tree[root].val x f )return root;if ( tree[root].val x ! f )return root;int u tree[root].son[f];if ( ! u )return 0;while ( tree[u].son[f ^ 1] )u tree[u].son[f ^ 1];return u;
}void Delete ( int x ) {int pre PreSuf ( x, 0 ), suf PreSuf ( x, 1 );splay ( pre, 0 );splay ( suf, pre );int u tree[suf].son[0];if ( tree[u].cnt 1 ) {tree[u].cnt --;splay ( u, 0 );}elsetree[suf].son[0] 0;
}int findkth ( int x ) {if ( tree[root].siz x )return -1;int u root;while ( 1 ) {if ( x tree[tree[u].son[0]].siz )u tree[u].son[0];else if ( x tree[u].cnt tree[tree[u].son[0]].siz )return u;else {x - ( tree[tree[u].son[0]].siz tree[u].cnt );u tree[u].son[1];}}
}int main() {insert ( INF );insert ( -INF );scanf ( %d, n );int opt, x;for ( int i 1;i n;i ) {scanf ( %d %d, opt, x );switch ( opt ) {case 1 : insert ( x ); break;case 2 : Delete ( x ); break;case 3 : {find ( x );printf ( %d\n, tree[tree[root].son[0]].siz );break;}case 4 : {int u findkth ( x 1 );printf ( %d\n, tree[u].val );break;}case 5 : {int u PreSuf ( x, 0 );printf ( %d\n, tree[u].val );break;}case 6 : {int u PreSuf ( x, 1 );printf ( %d\n, tree[u].val );break;}}}return 0;
}#include cstdio
#define maxn 100005
#define INF 0x7f7f7f7f
struct SplayTree {struct node {int f, cnt, val, siz, son[2];void init ( int Val, int fa ) {val Val;cnt siz 1;f fa;son[0] son[1] 0;}}tree[maxn];int root, Size;void update ( int x ) {tree[x].siz tree[tree[x].son[0]].siz tree[tree[x].son[1]].siz tree[x].cnt;}void rotate ( int x ) { int fa tree[x].f; int Gfa tree[fa].f;int k ( tree[fa].son[1] x );tree[Gfa].son[tree[Gfa].son[1] fa] x;tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );update ( x );}void splay ( int x, int goal ) {while ( tree[x].f ! goal ) {int fa tree[x].f, Gfa tree[fa].f;if ( Gfa ! goal )( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}if ( ! goal )root x;}void insert ( int x ) {int u root, fa 0;while ( u tree[u].val ! x ) {fa u;u tree[u].son[x tree[u].val]; }if ( u ) tree[u].cnt ;else {u Size; if ( fa ) tree[fa].son[x tree[fa].val] u;tree[u].son[0] tree[u].son[1] 0;tree[u].val x;tree[u].f fa;tree[u].cnt tree[u].siz 1;}splay ( u, 0 );}void find ( int x ) {if ( ! root )return;int u root;while ( tree[u].son[x tree[u].val] x ! tree[u].val )u tree[u].son[x tree[u].val];splay ( u, 0 ); }int PreSuf ( int x, int f ) { find ( x );if ( tree[root].val x f )return root;if ( tree[root].val x ! f )return root;int u tree[root].son[f];if ( ! u )return 0;while ( tree[u].son[f ^ 1] )u tree[u].son[f ^ 1];return u;}void Delete ( int x ) {int pre PreSuf ( x, 0 ), suf PreSuf ( x, 1 );splay ( pre, 0 );splay ( suf, pre );int u tree[suf].son[0];if ( tree[u].cnt 1 ) {tree[u].cnt --;splay ( u, 0 );}elsetree[suf].son[0] 0;}int findkth ( int x ) {if ( tree[root].siz x )return -1;int u root;while ( 1 ) {if ( x tree[tree[u].son[0]].siz )u tree[u].son[0];else if ( x tree[u].cnt tree[tree[u].son[0]].siz )return u;else {x - ( tree[tree[u].son[0]].siz tree[u].cnt );u tree[u].son[1];}}}}T;
int n;int main() {T.insert ( -INF );T.insert ( INF );scanf ( %d, n );int opt, x;for ( int i 1;i n;i ) {scanf ( %d %d, opt, x );switch ( opt ) {case 1 : T.insert ( x ); break;case 2 : T.Delete ( x ); break;case 3 : {T.find ( x );printf ( %d\n, T.tree[T.tree[T.root].son[0]].siz );break;}case 4 : {int u T.findkth ( x 1 );printf ( %d\n, T.tree[u].val );break;}case 5 : {int u T.PreSuf ( x, 0 );printf ( %d\n, T.tree[u].val );break;}case 6 : {int u T.PreSuf ( x, 1 );printf ( %d\n, T.tree[u].val );break;}}}return 0;
}
