学习目标：
- 理解红黑树添加节点后的平衡操作缘由，用4阶B树辅助记忆平衡操作。
特别说明！！！
平衡操作的基础操作包括：染色，左旋和右旋。为简洁起见，本文不详细介绍左旋和右旋具体操作，请自行搜索资料进行学习。
学习内容：
- 红黑树所有性质中与添加节点后平衡相关的性质
- 红黑树添加节点步骤
- 红黑树添加节点后的平衡——“双红修正”
- 双红修正流程
一、红黑树所有性质中与添加节点后平衡相关的性质
性质2. 根结点是黑色。
性质4. 不能有相连的红色结点。
性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
二、红黑树添加节点步骤
- 判断是否为空树，空树则把插入的节点染黑（性质2）并作为树的根节点。
- 不是空树，以二叉搜索树的搜索方式寻找是否已经存在该节点，节点已存在则退出。
- 不是空树，以二叉搜索树的搜索方式寻找是否已经存在该节点，节点不存在则插入新节点，默认颜色为红色。
- 检查插入节点和插入节点的父亲是否都是红色（性质5），如果都是红色则需要进行平衡，如果插入节点的父亲是黑色，则插入完成
讯享网
三、红黑树添加节点后的平衡——“双红修正”
由于性质5的存在和默认插入的节点是红色节点的缘故，如果插入位置的父节点是红色节点，出现双红现象就会违反性质5，为此需要进行修正，我所使用的学习视频称其为“双红修正”。
首先，在进行插入的时候，我们要先明确一点：插入节点的位置的父节点在4阶B树中必然是叶节点，这句话可以从两个角度进行理解，如下：1）B树是一种自下向上生长的树，因此插入节点是从叶节点插入的；2）根据B树性质之：对于非叶节点，当该节点是n节点时，它必须有n-1个关键字和n个孩子，而在红黑树中插入位置必然是一个空节点，与非叶节点的n节点必然有n个孩子相悖。
3.1 根据插入所在节点的类型分类讨论
回顾4阶B树的生长，我们针对插入所在节点的类型分类讨论：
3.1.1 二节点
不会出现双红现象，不需要双红修正。
3.1.2 三节点
如下图所示，从红黑树的视角可以发现：如果1）"插-父-祖父"的位置关系呈现“\”型：我们只需要父 祖父左旋+父&祖父颜色互换即可 ；2）“插-父-祖父”的位置关系呈现“>”型：我们需要 父右旋+祖父左旋+插&祖父颜色互换即可。对于镜像情况进行镜像旋转即可。
思考：其实我们从红黑树角度就可以看出如何修正，那为什么需要4阶B树进行辅助理解呢？
我的想法： 我们没有办法证明当我们从红黑树角度这样的一番修改就能使整棵树平衡，即我们只处理了局部关系，怎么知道这个局部的修改能使整体平衡？所以需要4阶B树进行辅助理解，再4阶B树中，这一切只发生在某一个节点的内部，只是在这个节点内部进行关键字颜色的转换，对于该节点以外的任何节点没有影响，即没有修改整体的关系。
3.1.2 四节点
四节点的情况比较特殊，因为涉及到了B树的生长，即会有几个关键字加入到父节点的位置，如下图渐变色节点所示，它有可能是黑的，此时这个节点是根节点，它也有可能是红的，因为相当于在非叶节点加入了一个节点，而加入一个节点默认是用红色的（还有另一个解释，每个节点只能有一个黑色关键字，这个关键字加入到父节点后，只能变成红色来满足“每个节点只能有一个黑色关键字”）。
在红黑树的角度，我们只需要 父&叔染黑+祖父染红+以祖父为插入节点迭代双红修正至根节点。
以祖父为插入节点迭代双红修正至根节点必然能使整棵树平衡。
3.2 处理方案选择
我们知道了二、三和四节点的双红现象对应于红黑树如何修正，但是红黑树并没有二、三和四节点这些概念，当出现双红现象时如何判断是对应4阶B树哪种节点？观察红黑树角度下三、四节点的异同：
观察图中粉红色的圈，可以发现，三节点中，“插”节点没有叔叔节点（或者说叔叔是黑色节点，因为nill默认是黑色节点）；而四节点都有一个红色的叔叔节点！
四、双红修正流程
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/13815.html