CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 自平衡二叉查找树 ======
未完待续..（例题代码什么的再补）
===== 二叉查找树(BST) =====
在二叉树中查找一个节点的复杂度是O(n)。我们可以构建二叉查找树来改善查询时间。
=== 特征 ===
在二叉查找树中每一个节点的左子树中所有结点的值都小于该结点的值，右子树中所有结点的值都大于该结点的值。\\
=== 查询 ===
根据特征我们自然可以得出查找的方式。如果二叉树分布比较“像一棵树”我们可以接近理想状态的O(logn),但如果树退化成直线复杂度将达到最坏情况的O(n)。
=== 插入节点 ===
设新节点为k,每次考虑的节点为p,点的值为f(x)。\\
1.若p为空，则k直接放在这个位置。\\
2.若f(k)=f(p),则用户试图重复插入一个值，根据要求处理。\\
3.若f(k)<f(p),则k一定在p的左子树中，将p的左孩子视作p；反之则k一定在p的右子树中，将p的右孩子视作p。回到1。
=== 删除节点 ===
设该节点为p,左孩子为l,右孩子为r。\\
1.若无r,则l代替p;反之若无l,则r代替p。\\
2.r无左孩子,则r代替p,将l作为r的左孩子。\\
3.r有左孩子，则r的左子树中左下的最深的节点，即r的左子树中值最小的点，代替p。l、r不变。
===== 自平衡二叉查找树 =====
如果树中节点的数量为 n，则一棵满足O($log_2{n}$) 渐进运行时间的树的高度应接近于比$log_2{n}$小的最大整数。\\
对于一棵二叉查找树，往往不能事先知道所有的数据从而并不能保证树的形状合适，例如在不断输入数据并且不断查询的情况下。\\
如果我们能实时调整树使其满足最高效率的形状就好了。为此我们有自平衡二叉查找树。\\
有多种自平衡结构，如AVL树、红黑树、2-3树、2-3-4树、伸展树、B树等等。
==== 红黑树 ====
=== 特征 ===
首先是节点具有颜色：红、黑二色；其次是存在一种NIL节点，作为伪叶子节点连接着内点。
满足性质：
  - 根节点是黑色
  - NIL节点是黑色
  - 如果节点的颜色是红色，则其子节点均为黑色
  - 从任一节点到其后代任一叶子节点的路径上的黑色节点的数量相同
=== 插入 ===
按照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树 ====
=== 特征 ===
对于每一个节点，其左右子树的高度差不超过1。
=== 插入 ===
按照二叉查找树
=== 删除 ===
==== 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。
=== 前驱/后继 ===
以前驱为例。\\
以查找的方式逐层下降即可。若关注的节点值小于给定值就更新差值，若相等就直接得到（这一点根据题目要求改变）。


未完待续（代码例题再补）
CVBB ACM Team

用户工具

站点工具

页面工具
