用户工具

站点工具


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

差别

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

到此差别页面的链接

后一修订版
前一修订版
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树 [2020/05/15 20:36]
shaco 创建
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树 [2020/05/22 20:40] (当前版本)
shaco
行 1: 行 1:
 ====== 自平衡二叉查找树 ====== ====== 自平衡二叉查找树 ======
 +未完待续..(例题代码什么的再补)
 ===== 二叉查找树(BST) ===== ===== 二叉查找树(BST) =====
 在二叉树中查找一个节点的复杂度是O(n)。我们可以构建二叉查找树来改善查询时间。 在二叉树中查找一个节点的复杂度是O(n)。我们可以构建二叉查找树来改善查询时间。
行 12: 行 13:
 3.若f(k)<​f(p),​则k一定在p的左子树中,将p的左孩子视作p;反之则k一定在p的右子树中,将p的右孩子视作p。回到1。 3.若f(k)<​f(p),​则k一定在p的左子树中,将p的左孩子视作p;反之则k一定在p的右子树中,将p的右孩子视作p。回到1。
 === 删除节点 === === 删除节点 ===
-设该节点为p,​左孩子为l,​右孩子为r。+设该节点为p,​左孩子为l,​右孩子为r。\\
 1.若无r,​则l代替p;​反之若无l,​则r代替p。\\ 1.若无r,​则l代替p;​反之若无l,​则r代替p。\\
 2.r无左孩子,​则r代替p,​将l作为r的左孩子。\\ 2.r无左孩子,​则r代替p,​将l作为r的左孩子。\\
行 30: 行 31:
   - 从任一节点到其后代任一叶子节点的路径上的黑色节点的数量相同   - 从任一节点到其后代任一叶子节点的路径上的黑色节点的数量相同
 === 插入 === === 插入 ===
-按照BST的插入方式在计算出的位置插入一个红节点。 +按照BST的插入方式在计算出的位置插入一个红节点。设该节点为K,父节点为P,​P父节点为G,P的兄弟节点为S。\\ 
- +1.若P为黑色,则符合红黑树的性质,不需要做改动。\\ 
-=== 删除 ===+2.若P为红色:​\\ 
 +$\quad\quad $2a.若S是黑色或为空,则需要进行旋转,分为四种情况,前两种情况是P是G的左孩子,后两种情况为P是右孩子。\\ 
 +{{:​2020-2021:​teams:​no_morning_training:​shaco:​知识点:​数据结构:​021519393874306.gif?​400|}}\\ 
 +{{:​2020-2021:​teams:​no_morning_training:​shaco:​知识点:​数据结构:​021521439021512.gif?​400|}}\\ 
 +$\quad\quad $2b.若S是红色,则需要对P、S、G重新着色:将P和S着色为黑色,将G着色为红色。\\ 
 +{{:​2020-2021:​teams:​no_morning_training:​shaco:​知识点:​数据结构:​021523324347436.gif?​400|}}\\ 
 +这样的重新着色不会影响G及以下的性质,但可能出现G与其父节点同红的情况,此时需要遵循上述方式向上递归地进行调整。 
 +=== 删除 ===</​hidden>​
 ==== AVL树 ==== ==== AVL树 ====
 === 特征 === === 特征 ===
行 39: 行 47:
 按照二叉查找树 按照二叉查找树
 === 删除 === === 删除 ===
 +==== splay ====
 +=== 特征 ===
 +通过不断地将查询的、插入的节点进行旋转操作,实现将查找频率高的点搬至根节点附近的动作。
 +=== rotate ===
 +{{:​2020-2021:​teams:​no_morning_training:​shaco:​知识点:​数据结构:​1101696-20171125194733656-1618296206.png?​200|}}
 +以这个图为例。要将x旋转至y,需要进行的操作是:
 +  * 将x的 x相对于y的方向的 相反方向 的儿子,作为y的 x相对于y的方向的 儿子。
 +  * 将y作为x的 x相对于y的方向的 相反方向的 儿子。
 +  * 以x取代y相对于p的位置。
 +{{:​2020-2021:​teams:​no_morning_training:​shaco:​知识点:​数据结构:​1101696-20171125200053250-822796586.png?​200|}}结果如图。其他所有情况均如上述操作即可。
 +=== splay ===
 +这个操作是让某一个点通过不断旋转移动到某一个位置,在这个过程中的旋转起到了调整树结构的作用。\\
 +分为三种情况
 +1.若目标点是选择点的父亲,则直接rotate。\\
 +2.目标点、父亲、祖父在一条线上,先rotate父亲再rotate选定点。如果直接rotate选定点两次,那么这个结构中依旧存在长度为2的路径,而使用这里的方法可以消灭这条长度为二的路径。\\
 +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/知识点/数据结构/自平衡二叉查找树.1589546166.txt.gz · 最后更改: 2020/05/15 20:36 由 shaco