360免费建站软仵下载,wordpress制作婚礼网页,龙岗做商城网站建设,wordpress婚礼主题一个比线段树代码还要又臭又长的数据结构#xff0c;各式各样的函数#xff0c;咱也不知道别人怎么记住的#xff0c;咱也不敢问 SPLAY的性质 1.某个节点的左子树全部小于此节点#xff0c;右子树全部大于此节点 2.中序遍历splay输出的序列是按从小到大的顺序 #xff08;…一个比线段树代码还要又臭又长的数据结构各式各样的函数咱也不知道别人怎么记住的咱也不敢问 SPLAY的性质 1.某个节点的左子树全部小于此节点右子树全部大于此节点 2.中序遍历splay输出的序列是按从小到大的顺序 我当时忽略了性质2以为大小关系只存在于单独的左右儿子和父节点后来问了同学才知道我没看过二叉排序树我能怎么办 询问左右儿子 就是查询一下x是fa的左儿子还是右儿子 int get(int x)
{return a[a[x].fu].son[1]x;
} 更新数据 由于每次翻转之后左右儿子的信息都会改变所以需要更新一下size void gx(int x)
{a[x].sizea[a[x].son[0]].sizea[a[x].son[1]].sizea[x].js;
} 上旋 什么是上旋呢简单来说就是儿子想当爹然后他还成功了也不知道这个爹会不会被气死就是把自己父节点变成自己的一个儿子但是对于一个有两个子节点的子节点显然父节点没地方去又因为需要保证平衡树的性质左子树小于父节点小于右子树所以肯定子节点的某一个叶节点要去给父节点当儿子根据splay性质中的大小关系如果子节点是父节点的左儿子那父节点就要去当子节点的右儿子此时根据splay的性质直接让子节点的右儿子去当父节点的左儿子即可这样就完成了一次翻转并且没有改变splay的性质若子节点是父节点的右儿子同理交换儿子总结一下就是假设右旋xx是fa的0儿子就让x的1儿子去当fa的0儿子fa变成x的1儿子0和1就是一个左一个右 void sx(int x)
{int fa[x].fu,ffa[f].fu;int z1get(x),z2get(f);a[f].son[z1]a[x].son[z1^1]; a[a[x].son[z1^1]].fuf;a[x].son[z1^1]f; a[f].fux;a[ff].son[z2]x; a[x].fuff;gx(f); gx(x);
} 双旋 我觉得双旋就是上旋中的一种特殊情况就是子节点父节点祖父节点在同一条线上这时需要先上旋父节点据说直接上旋慢不够优秀而且双旋好像还可以减小期望深度我并没有模拟同一条线的话特判一下就可以了记得更新根节点 void splay(int x,int mb)
{while(a[x].fu!mb){int fa[x].fu,ffa[f].fu;int z1get(x),z2get(f);if(ff!mb){if(z1z2) sx(f);else sx(x);}sx(x);}if(mb0) rootx;
} 几个基本操作 1.插入节点 插入的话我觉得和权值线段树那种递归的原理差不多遍历来找到合适的位置加入已经有这个点就直接cnt如果没有的话就新建一个节点新建之后的话把新建的点旋到根维护下树就可以了 void cr(int x)
{int dqroot,f0;while(a[dq].w!xdq!0){fdq;dqa[dq].son[a[dq].wx];}if(dq!0) {a[dq].js; gx(dq);}else{dqnum;if(f!0) a[f].son[a[f].wx]dq;a[dq].size1; a[dq].js1;a[dq].fuf; a[dq].wx;}splay(dq,0);
} 2.删除结点 删除还是和插入一样有两种情况如果这个节点的个数不为一直接cnt--然后旋到根如果为一的话删除这个点又不能影响其他点但是你没办法保证删除的每一个点都没有叶子节点这个时候就需要上旋来保证删除的点没有叶子结点具体操作就是把前驱旋到根后继旋到前驱下面这样的话被删除的点就变成了叶子节点直接清零删除就可以了 void sc(int x)
{int qqqqq(x),hjhhj(x);splay(qqq,0); splay(hjh,qqq);int za[hjh].son[0];if(a[z].js1) {a[z].js--; gx(z); splay(z,0);}else a[hjh].son[0]0;
} 3.查询某值排名 查询排名先要找到这个值在树中的位置当然如果没有这个值的话会一直找的叶子节点也不一定是最接近查询值的点我运行了一下发现他会找到第一个比这个值小的值而不是最接近这个数的值这种操作的话可以搜极大值和极小值来找到树中最大值和最小值找到这个值之后就简单了把这个值上旋到根的位置他左边都是比他小的右边都是比他大的那么他左子树的size1就是这个值的排名 int find(int x)
{int dqroot;while(a[dq].w!xa[dq].son[a[dq].wx]!0)dqa[dq].son[a[dq].wx];return dq;
}
int cpm(int x)
{splay(find(x),0);return a[a[root].son[0]].size;
} 关于find函数的运行结果1为插入2为find查询 4.查询某值的前驱/后继 x的前驱小于x的最大的数 x的后继大于x的最小的数 用find函数查找x把x上旋到根的位置由于x可能不存在而find查到的又是第一个比他小的值所以有可能上旋后根节点就是要查询的前驱所以要特判但是根据我的运行结果来说我认为后继不需要特判如果怕不保险特判也无所谓反正特判应该是肯定对的那个如果有x这个值那么前驱就是他的左子树的最右叶子节点同理后继就是他右子树的最左叶子节点一直向下搜就可以了 int qq(int x)
{splay(find(x),0);int dqroot;if(a[dq].wx) return dq;dqa[dq].son[0];while(a[dq].son[1]!0) dqa[dq].son[1];return dq;
}
int hj(int x)
{splay(find(x),0);int dqroot;if(a[dq].wx) return dq;dqa[dq].son[1];while(a[dq].son[0]!0) dqa[dq].son[0];return dq;
} 5.查询第k小值 跟主席树求第k小有点相似通过记录左右子树包含的元素个数与k进行比较选择暴力递归左儿子或者右儿子如果当前节点的左子树元素个数小于k那么第k小就在右子树中k减去左子树元素个数当前点的cnt值还有这个元素自己后暴力搜索右子树如果左子树元素个数大于k直接搜索左子树假如k介于左子树右子树的size之间一定要想清为什么有范围因为同一个值可能出现多次导致他自己代表的值就不唯一我死在这好久那么当前点就是第k小 int csz(int x)
{int dqroot;while(1){int lsa[dq].son[0];if(a[ls].sizex) dqls;else if(a[ls].sizea[dq].jsx){x-a[ls].sizea[dq].js;dqa[dq].son[1];}else return a[dq].w;}
} 到此普通平衡树就可以搞定了 关于插入结点那一块虽然最后的splay执行中会更新结点但是我还是觉得在直接更新cnt之后更新一下节点信息比较好 现在思路是理出来了也不知道代码能不能打下来我依旧是个蒟蒻 第一次完整的整理了一个知识点还有点兴奋转载于:https://www.cnblogs.com/hzjuruo/p/11110279.html
