用户工具

站点工具


2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树 [2020/05/22 15:43]
shaco
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树 [2020/05/22 20:40] (当前版本)
shaco
行 62: 行 62:
 1.若目标点是选择点的父亲,则直接rotate。\\ 1.若目标点是选择点的父亲,则直接rotate。\\
 2.目标点、父亲、祖父在一条线上,先rotate父亲再rotate选定点。如果直接rotate选定点两次,那么这个结构中依旧存在长度为2的路径,而使用这里的方法可以消灭这条长度为二的路径。\\ 2.目标点、父亲、祖父在一条线上,先rotate父亲再rotate选定点。如果直接rotate选定点两次,那么这个结构中依旧存在长度为2的路径,而使用这里的方法可以消灭这条长度为二的路径。\\
-3.目标点、父亲、祖父不在一条线上,rotate选定点两次。\\ +3.目标点、父亲、祖父不在一条线上,rotate选定点两次。
-=== +
  
 +在很多操作之后都需要将目标点splay至根。
 +=== 删除 ===
 +删除操作是基于查找操作的,查找操作又需要将找到的点splay至根,因此删除操作是针对根的。\\
 +分为几种情况:
 +  * 该点的计数值大于1,直接减1。
 +  * 该点有左儿子,找到左子树中值最大的点作根。
 +  * 该点有右儿子,将右儿子作为根。
 +  * 无左右儿子,整个变成空树。
 +(下面的情况默认上面的条件不成立)
 +=== 查询给定值排名 ===
 +以从小到大的排名为例。\\
 +如果能找到这个值的话,直接旋至根,左子树大小+1即为排名。\\
 +否则就逐层下降,和查找的方式一样,向右侧走的时候就加上左子树和根节点的size,向左侧走就不加。
 +=== 查询指定排名的数 ===
 +以从小到大的排名为例。\\
 +逐层下降。剩余排名在左子树size+1和左子树size+关注节点size之间则为关注到的节点;小于左子树size+1下降至左子树;大于左子树size+关注节点size下降至右子树。\\
 +降至右子树时将剩余排名减去左子树size+关注节点size。
 +=== 前驱/​后继 ===
 +以前驱为例。\\
 +以查找的方式逐层下降即可。若关注的节点值小于给定值就更新差值,若相等就直接得到(这一点根据题目要求改变)。
  
 +
 +未完待续(代码例题再补)
  
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/自平衡二叉查找树.1590133414.txt.gz · 最后更改: 2020/05/22 15:43 由 shaco