2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树 [2020/05/15 20:52] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:自平衡二叉查找树 [2020/05/22 20:40] (当前版本) shaco |
||
|---|---|---|---|
| 行 13: | 行 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的左孩子。\\ | ||
| 行 40: | 行 40: | ||
| {{:2020-2021:teams:no_morning_training:shaco:知识点:数据结构:021523324347436.gif?400|}}\\ | {{:2020-2021:teams:no_morning_training:shaco:知识点:数据结构:021523324347436.gif?400|}}\\ | ||
| 这样的重新着色不会影响G及以下的性质，但可能出现G与其父节点同红的情况，此时需要遵循上述方式向上递归地进行调整。 | 这样的重新着色不会影响G及以下的性质，但可能出现G与其父节点同红的情况，此时需要遵循上述方式向上递归地进行调整。 | ||
| - | === 删除 === | + | === 删除 ===</hidden> |
| ==== AVL树 ==== | ==== AVL树 ==== | ||
| === 特征 === | === 特征 === | ||
| 行 47: | 行 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/知识点/数据结构/自平衡二叉查找树.1589547173.txt.gz · 最后更改: 2020/05/15 20:52 由 shaco
