红黑树的增加(插入)和删除
☼ 红黑树之介绍：
-----------形态上是特殊的二叉搜索树【特殊体现在颜色上，同时在逻辑上它是等价于4阶B树的】
❀ 红黑树是怎么等价于4 阶B 树的？ ---------红黑树要变成B树：需要将红结点和黑结点进行合并（黑色作为根【也是中间元素】）。
✿ 红黑-->B 树： 结点有四种情况是：①红-黑-红、②红-黑、③黑-红、④黑
● 可以插入的位置的所有情况：
1. 节点是 RED 或者 BLACK 2. 根节点是 BLACK 3. 叶子节点（外部节点，空节点）都是 BLACK 4. RED 节点的子节点都是 BLACK: ✓ RED 节点的 parent 都是 BLACK ✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点 5. 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点 |
一、红黑树结点的添加(插入)--添加必是添加到 -B树叶子子结点的位置：
(1) 4阶 B 树的叶子结点一般有以下四种情况：
① 红<---黑--->红 ② 红<---黑 ③ 黑--->红 ④ 黑
(2) 分类讨论：
（2-1）当父结点是黑色（有四种情况）时【上图的 7、8、11、12】，直接插入；【有可能是第一个结点-根(记得染黑根)】;
（2-2）剩下8种情况根据 叔父结点是否为红色进行划分：
（2-2-1）叔父是红色时【上图的 1、2、3、4】，举个栗子： 红(新插入的)<---红<---黑【根】--->红 （对于4阶B树而言，发生了上溢了，需要，进行分裂处理，根（染红）上去，然后父结点、叔父结点染黑）；即 ：
（2-2-2）叔父不是红色时【上图的 5、6、9、10】，举个栗子： 红(新插入的)<---红<---黑【根】：为了满足红黑树定义的性质四：
红(新插入的)<---红(变黑)<---黑【根】(变红，因为B树的结点组合中是红黑红（只有一个黑作为中间元素的根））
● 现在需要修改：中间的黑色为根，需要修改那个<---的方向：改为：
红(新插入的)<---红(变黑) 【根】--->黑【根】(变红)
[观察此刻情况，修改这种修改，符合右旋，再观察其实就是跟AVL 的LL型原理一致啦]
❀ 红黑树整个添加之后的处理的代码如下：
@Override protected void afterAdd(Node<E> node) { // 判断父结点 Node<E> parent = node.parent; // 添加的是根【当添加第一个结点时】/ 或者上溢到了根结点时 if (parent == null) { black(node); return; } // 若父结点是黑色时，不用处理，直接返回 if (isBlack(parent)) return; // 若叔父结点是红色的[B 树的上溢] Node<E> uncle = parent.sibling(); Node<E> grand = red(parent.parent); if (isRed(uncle)) { // 染黑爸爸、叔叔，把祖父染成红色，相当于新插入的结点 black(uncle); black(parent); // red(grand); // afterAdd(grand); // ① 上溢时，也要染红祖父结点 // afterAdd(red(grand)); afterAdd(grand); return; } //观察一下，对代码进行优化，共同拥有的抽到外部之类的 // 来到这里叔父不是红色 if (parent.isLeftChild()) { // L // ② 旋转时，也要 染红结点 // red(grand); if (node.isLeftChild()) { // LL //染黑父结点，染红祖父结点 black(parent); // red(grand); //右旋 // rotateRight(grand); } else { // LR //染红自己、染黑祖父结点 black(node); // red(grand); //左旋后右旋 rotateLeft(parent); // rotateRight(grand); } rotateRight(grand); } else { // R // ② 旋转时，也要 染红结点 // red(grand); if (node.isLeftChild()) { // RL //染红自己、染黑祖父结点 black(node); // red(grand); //左旋后右旋 rotateRight(parent); // rotateLeft(grand); } else { // RR //染黑父结点，染红祖父结点 black(parent); // red(grand); //左旋 // rotateLeft(grand); } rotateLeft(grand); } }
1，分类：（具体过程需要根据父结点作为左结点、右结点进行对称） （1）不需要调整： ■ 当前结点是根，染黑即可； ■ 父结点是黑，不用处理。 （2）需要调整： ■ case1：叔父是红色，当前结点x 可左可右，染黑 父、叔，染红爷，回溯到结点爷处。 ■ case2：叔父是黑色，当前结点x 是右孩子【红红是LR型】，先进行左旋，转化成case3；（先考虑当前结点是右孩子，因为它处理一下就变成了case3）【小细节，当前结点x 指向 父结点时，旋转x(其实旋转的是原先的父结点的位置)】 ■ case3：叔父是黑色，当前结点x 是左孩子【红红是LL型】，染黑父，染红爷，然后右旋 |
二、红黑树结点的删除--删除必是 -B树叶子子结点的位置：
● 可以删除的位置的所有情况：
(1) 4阶 B 树的叶子结点一般有以下四种情况：
① 红<---黑--->红 ② 红<---黑 ③ 黑--->红 ④ 黑
(2) 分类讨论：
(2-1) 删除的直接是红色结点时【上图的 1、3、5、6】【2也一样（因为它是度为2，最终删除的要么是前驱的1或者后驱的3）】，就直接删除，不用处理。
(2-2) 删除的是黑色的结点：
（2-2-1）用来替代的结点是红色时【上图的 4、7】，处理：将替代的结点【5、6】染成黑色（因为替代成为了B树的叶子结点了，根是黑色的）。
（2-2-2）用来替代的结点是黑色时【上图的 8】，处理：
❀ 红黑树整个删除结点之后的处理的代码如下：
@Override protected void afterRemove(Node<E> node) { //要删除结点是红色，直接删除，不用处理 // if(isRed(node)) return; //要删除的结点是黑色 ，然后用于替换删除结点的子结点是红色，然后替换结点即可 if(isRed(node)) { //这里的处理是包含了上面if(isRed(node))的情况 black(node); return; } Node<E> parent = node.parent; //删除的是根结点，也是直接删除不用处理 if(parent == null) return; // 要删除结点是黑色，而且是叶子结点，没有可以替换的结点时， // 判断被删除的node 是左还是右，直接通过sibling 去拿就已经不准了，因为叶子结点已经删除了，拿不到哦 了 // 需重新判断一下 boolean left = parent.left == null || node.isLeftChild(); Node<E> sibling = left ? parent.right : parent.left; if (left) { // 被删除的是左边的，兄弟结点在右边 if (isRed(sibling)) { // 兄弟结点是红色，相当于以前删除时，先考虑删除度为2，将度为2的进行第一步处理后，它就变成了与删除度为1、0 的情况一致了 black(sibling); // 等下变成根 red(parent); rotateLeft(parent);// 通过左边旋转，侄子变成了我的兄弟了 // 更换兄弟 sibling = parent.right; } // 现在来到这里的兄弟都是黑色的啦 if (isBlack(sibling.left) && isBlack(sibling.right)) { // 黑兄弟的孩子是黑色的，不能借【没有红色结点可以外借】 // 借不了，只能让父结点下来进行跟兄弟合并【将父结点染黑（变成根），兄弟染红】 // 染色之前还需要考虑父结点原先是不是黑色【黑色会导致下溢】 boolean parentBlack = isBlack(parent); black(parent); red(sibling); if (parentBlack) { // 下溢，递归处理，相当于父结点被删除 afterRemove(parent); } } else { // 兄弟结点至少有一个红色子结点【可以外借时】 // 即接下来的情况： 黑【根】->红 红<-黑【根】 红<-黑【根】->红 // 兄弟结点的右边是黑色，兄弟要先旋转【即先处理情况： 黑->红，处理完后，接下来变成了 RR的情况，与后边两者是一样只需要左旋转】 if (isBlack(sibling.right)) { rotateRight(sibling); sibling = parent.right; // 修改兄弟结点位置 } // 染色处理【上去的兄弟，要保证颜色与原来的相同，结构不变 】 color(sibling, colorOf(parent)); // 兄弟的儿子【可以借的结点】要上去作为根 black(sibling.right); // 父结点要旋转下来作为根 black(parent); rotateLeft(parent); } } else { // 删除结点是在右边的，兄弟结点在左边的 if (isRed(sibling)) { // 兄弟结点是红色，相当于以前删除时，先考虑删除度为2，将度为2的进行第一步处理后，它就变成了与删除度为1、0 的情况一致了 black(sibling); // 等下变成根 red(parent); rotateRight(parent);// 通过右边旋转，侄子变成了我的兄弟了 // 更换兄弟 sibling = parent.left; } // 现在来到这里的兄弟都是黑色的啦 if (isBlack(sibling.left) && isBlack(sibling.right)) { // 黑兄弟的兄弟是黑色的，不能借【没有红色结点可以外借】 // 借不了，只能让父结点下来进行跟兄弟合并【将父结点染黑（变成根），兄弟染红】 // 染色之前还需要考虑父结点原先是不是黑色【黑色会导致下溢】 boolean parentBlack = isBlack(parent); black(parent); red(sibling); if (parentBlack) { // 下溢，递归处理，相当于父结点被删除 afterRemove(parent); } } else { // 兄弟结点至少有一个红色子结点【可以外借时】 // 即接下来的情况： 黑【根】->红 红<-黑【根】 红<-黑【根】->红 // 兄弟结点的左边是黑色，兄弟要先旋转【即先处理情况： 黑->红，处理完后，接下来变成了 LL的情况，与后边两者是一样只需要右旋转】 if (isBlack(sibling.left)) { rotateLeft(sibling); sibling = parent.left; // 修改兄弟结点位置 } // 染色处理【上去的兄弟，要保证颜色与原来的相同，结构不变 】 color(sibling, colorOf(parent)); // 兄弟的儿子【可以借的结点】要上去作为根 black(sibling.left); // 父结点要旋转下来作为根 black(parent); rotateRight(parent); } } }
