红黑树定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

  • 性质1：每个节点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子节点（NIL）是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

图1就是一颗简单的红黑树。其中Nil为叶子结点，并且它是黑色的。(值得提醒注意的是，在Java中，叶子结点是为null的结点。)

红黑树 - 图2

红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以红黑树这种平衡为黑色完美平衡。
对于红黑树一些结点的叫法，如图2所示。
红黑树 - 图3

红黑树能自平衡靠的是三种操作：左旋、右旋和变色。

  • 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
  • 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
  • 变色：结点的颜色由红变黑或由黑变红。

红黑树 - 图4
图3 左旋
红黑树 - 图5
图4 右旋

上面所说的旋转结点也即旋转的支点，图4和图5中的P结点。
我们先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。
左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。
但要保持红黑树的性质，结点不能乱挪，还得靠变色了。怎么变？具体情景又不同变法，后面会具体讲到，现在只需要记住红黑树总是通过旋转和变色达到自平衡。

节点的默认颜色为红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

  1. public static class TreeNode {
  2.     public TreeNode parent;
  3.     public TreeNode left;
  4.     public TreeNode right;
  5.     public boolean red;
  6.     public int value;
  8.     public TreeNode(int value) {
  9.         this.value = value;
  10.         this.red = true;
  11.     }
  12. }
  1. public class RBTree {
  3.     private TreeNode rootNode;
  5.     private boolean isRed(TreeNode treeNode) {
  6.         return treeNode.red;
  7.     }
  9.     private boolean isBlack(TreeNode treeNode) {
  10.         return !treeNode.red;
  11.     }
  13.     private void setRed(TreeNode treeNode) {
  14.         treeNode.red = true;
  15.     }
  17.     private void setBlack(TreeNode treeNode) {
  18.         treeNode.red = false;
  19.     }
  20. }

红黑树插入

插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。所有插入情景如图7所示。

红黑树 - 图6

在插入时，节点之间的关系如图下

红黑树 - 图7

插入情景1：红黑树为空树

直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。
处理：把插入结点作为根结点，并把结点设置为黑色。

  1.     TreeNode treeNode = new TreeNode(value);
  2.     if (rootNode == null) {
  3.         treeNode.red = false;
  4.         rootNode = treeNode;
  5.         return;
  6.     }

插入情景2：插入结点的key已存在

插入情景3：插入结点的父结点为黑结点

由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
处理：直接插入。

插入情景4：插入结点的父结点为红结点

如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。红黑树的性质2：根结点是黑色。
情景4又分为很多子情景

插入情景4.1：叔叔结点存在并且为红结点

从红黑树性质4可以，祖父结点肯定为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。如图9和图10所示。
处理：

  • 将P和S设置为黑色
  • 将PP设置为红色
  • 把PP设置为当前插入结点

红黑树 - 图8
图9 插入情景4.1_1
红黑树 - 图9
图10 插入情景4.1_2
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。
试想下PP刚好为根结点时，那么根据性质2，我们必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。
我们还可以总结出另外一个经验：红黑树的生长是自底向上的。这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。

  1.     TreeNode parent;
  2.     TreeNode gparent;
  3.     while (((parent = node.parent) != null) && isRed(parent)) {
  4.         gparent = parent.parent;
  6.         if (gparent.left != null && parent == gparent.left) {
  7.             TreeNode uncle = gparent.right;
  9.             if (uncle != null && isRed(uncle)) {
  10.                 setRed(gparent);
  11.                 setBlack(parent);
  12.                 setBlack(uncle);
  13.                 node = gparent;
  14.                 continue;
  15.             }
  16.         }
  17.     }

插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

单纯从插入前来看，也即不算情景4.1自底向上处理时的情况，叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质5。后续情景同样如此。
前文说了，需要旋转操作时，肯定一边子树的结点多了或少了，需要租或借给另一边。插入显然是多的情况，那么把多的结点租给另一边子树就可以了。
插入情景4.2.1：插入结点是其父结点的左子结点
处理：

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行右旋

红黑树 - 图10
图11 插入情景4.2.1
由图11可得，左边两个红结点，右边不存在，那么一边一个刚刚好，并且因为为红色，肯定不会破坏树的平衡。
咦，可以把PP设为红色，I和P设为黑色吗？答案是可以！看过《算法：第4版》的同学可能知道，书中讲解的就是把PP设为红色，I和P设为黑色。但把PP设为红色，显然又会出现情景4.1的情况，需要自底向上处理，做多了无谓的操作，既然能自己消化就不要麻烦祖辈们啦～

插入情景4.2.2：插入结点是其父结点的右子结点
这种情景显然可以转换为情景4.2.1，如图12所示，不做过多说明了。
处理：

  • 对P进行左旋
  • 把P设置为插入结点，得到情景4.2.1
  • 进行情景4.2.1的处理

红黑树 - 图11
图12 插入情景4.2.2

  1. private void rotateRL(TreeNode treeNode) {
  2.     TreeNode parent = treeNode.parent;
  3.     TreeNode pparent = parent.parent;
  4.     TreeNode left = treeNode.left;
  6.     treeNode.left = parent;
  7.     parent.right = left;
  8.     if (pparent != null && parent == pparent.left) {
  9.         pparent.left = treeNode;
  10.     }
  11.     if (pparent != null && parent == pparent.right) {
  12.         pparent.right = treeNode;
  13.     }
  14.     if (pparent == null) {
  15.         this.rootNode = treeNode;
  16.     }
  17.     treeNode.parent = pparent;
  18.     parent.parent = treeNode;
  19. }
  1.  if (node == parent.right) {
  2.     rotateRL(node);
  3.     parent = node;
  4. }

插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景4.2，只是方向反转，不做过多说明了，直接看图。
插入情景4.3.1：插入结点是其父结点的右子结点
处理：

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行左旋

红黑树 - 图12
图13 插入情景4.3.1
插入情景4.3.2：插入结点是其父结点的右子结点
处理：

  • 对P进行右旋
  • 把P设置为插入结点，得到情景4.3.1
  • 进行情景4.3.1的处理

红黑树 - 图13
图14 插入情景4.3.2

  1. private void rotateLR(TreeNode treeNode) {
  2.     TreeNode parent = treeNode.parent;
  3.     TreeNode pparent = parent.parent;
  4.     TreeNode right = treeNode.right;
  6.     treeNode.right = parent;
  7.     parent.left = right;
  8.     if (pparent != null && parent == pparent.left) {
  9.         pparent.left = treeNode;
  10.     }
  11.     if (pparent != null && parent == pparent.right) {
  12.         pparent.right = treeNode;
  13.     }
  14.     if (pparent == null) {
  15.         this.rootNode = treeNode;
  16.     }
  17.     treeNode.parent = pparent;
  18.     parent.parent = treeNode;
  19. }
  1.     rotateLR(parent);
  2.     setBlack(parent);
  3.     setRed(gparent);

好了，讲完插入的所有情景了。可能又同学会想：上面的情景举例的都是第一次插入而不包含自底向上处理的情况，那么上面所说的情景都适合自底向上的情况吗？答案是肯定的。理由很简单，但每棵子树都能自平衡，那么整棵树最终总是平衡的。

好吧，在出个习题，请大家拿出笔和纸画下试试（请务必动手画下，加深印象）：
习题1：请画出图15的插入自平衡处理过程。（答案见文末）
红黑树 - 图14

完整代码

  1. package com.lizhouwei.suanfa.tree;
  4. import java.util.Arrays;
  5. import java.util.List;
  7. /**
  8.  * @Description:
  9.  * @Author: lizhouwei
  10.  * @CreateDate: 2019/9/21 9:19
  11.  * @Modified By:
  12.  */
  13. public class RBTree {
  15.     private TreeNode rootNode;
  17.     public void insert(int value) {
  18.         TreeNode treeNode = new TreeNode(value);
  19.         if (rootNode == null) {
  20.             treeNode.red = false;
  21.             rootNode = treeNode;
  22.             return;
  23.         }
  24.         TreeNode parentNode = rootNode;
  25.         while (parentNode != null) {
  26.             if (parentNode.value < value && parentNode.right != null) {
  27.                 parentNode = parentNode.right;
  28.             } else if (parentNode.value > value && parentNode.left != null) {
  29.                 parentNode = parentNode.left;
  30.             } else {
  31.                 break;
  32.             }
  33.         }
  35.         if (parentNode.value > value) {
  36.             parentNode.left = treeNode;
  37.         } else if (parentNode.value < value) {
  38.             parentNode.right = treeNode;
  39.         }
  40.         treeNode.parent = parentNode;
  41.         //修复节点
  42.         insertFixUp(treeNode);
  44.     }
  46.     public void insertFixUp(TreeNode node) {
  47.         TreeNode parent;
  48.         TreeNode gparent;
  49.         while (((parent = node.parent) != null) && isRed(parent)) {
  50.             gparent = parent.parent;
  52.             if (gparent.left != null && parent == gparent.left) {
  53.                 TreeNode uncle = gparent.right;
  55.                 if (uncle != null && isRed(uncle)) {
  56.                     setRed(gparent);
  57.                     setBlack(parent);
  58.                     setBlack(uncle);
  59.                     node = gparent;
  60.                     continue;
  61.                 }
  63.                 if (node == parent.right) {
  64.                     rotateRL(node);
  65.                     parent = node;
  66.                 }
  68.                 rotateLR(parent);
  69.                 setBlack(parent);
  70.                 setRed(gparent);
  72.             } else {
  73.                 TreeNode uncle = gparent.left;
  75.                 if (uncle != null && isRed(uncle)) {
  76.                     setRed(gparent);
  77.                     setBlack(parent);
  78.                     setBlack(uncle);
  79.                     node = gparent;
  80.                     continue;
  81.                 }
  83.                 if (node == parent.left) {
  84.                     rotateLR(node);
  85.                     parent = node;
  86.                 }
  88.                 rotateRL(parent);
  89.                 setBlack(parent);
  90.                 setRed(gparent);
  91.             }
  92.         }
  93.         // 将根节点设为黑色
  94.         setBlack(this.rootNode);
  95.     }
  97.     private boolean isRed(TreeNode treeNode) {
  98.         return treeNode.red;
  99.     }
  101.     private boolean isBlack(TreeNode treeNode) {
  102.         return !treeNode.red;
  103.     }
  105.     private void setRed(TreeNode treeNode) {
  106.         treeNode.red = true;
  107.     }
  109.     private void setBlack(TreeNode treeNode) {
  110.         treeNode.red = false;
  111.     }
  113.     private void inOrder(TreeNode node) {
  114.         if (node == null) {
  115.             return;
  116.         }
  117.         inOrder(node.left);
  118.         System.out.print(node.value + " ");
  119.         inOrder(node.right);
  120.     }
  123.     public static class TreeNode {
  124.         public TreeNode parent;
  125.         public TreeNode left;
  126.         public TreeNode right;
  127.         public boolean red;
  128.         public int value;
  130.         public TreeNode(int value) {
  131.             this.value = value;
  132.             this.red = true;
  133.         }
  134.     }
  137.     private static final List<Integer> data = Arrays.asList(10, 40, 30, 60, 90, 70, 20, 50, 80);
  139.     public static void main(String[] args) {
  140.         RBTree RBTree = new RBTree();
  141.         System.out.printf("== 原始数据: ");
  142.         data.stream().forEach((item) -> {
  143.             System.out.print(item + " ");
  144.             RBTree.insert(item);
  145.         });
  146.         RBTree.inOrder(RBTree.rootNode);
  147.     }
  148. }

红黑树删除

红黑树 - 图15

将红黑树内的某一个节点删除。需要执行的操作依次是：
首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；
然后，通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：

第一步：将红黑树当作一颗二叉查找树，将节点删除。

这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：

  1. 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
  2. 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
  3. 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给”被删除节点”之后，再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了，下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空，就意味着”该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况1 “进行处理；若只有一个儿子，则按”情况2 “进行处理。

第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。

因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。

红黑树 - 图16

删除情景1：替换结点是红色结点

我们把替换结点换到了删除结点的位置时，由于替换结点时红色，删除也了不会影响红黑树的平衡，只要把替换结点的颜色设为删除的结点的颜色即可重新平衡。
处理：颜色变为删除结点的颜色

删除情景2：替换结点是黑结点

当替换结点是黑色时，我们就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。
删除情景2.1：替换结点是其父结点的左子结点

删除情景2.1.1：替换结点的兄弟结点是红结点
若兄弟结点是红结点，那么根据性质4，兄弟结点的父结点和子结点肯定为黑色，不会有其他子情景，我们按图21处理，得到删除情景2.1.2.3（后续讲解，这里先记住，此时R仍然是替代结点，它的新的兄弟结点SL和兄弟结点的子结点都是黑色）。
处理：**

  • 将S设为黑色
  • 将P设为红色
  • 对P进行左旋，得到情景2.1.2.3
  • 进行情景2.1.2.3的处理

红黑树 - 图17
图21 删除情景2.1.1

删除情景2.1.2：替换结点的兄弟结点是黑结点
当兄弟结点为黑时，其父结点和子结点的具体颜色也无法确定（如果也不考虑自底向上的情况，子结点非红即为叶子结点Nil，Nil结点为黑结点），此时又得考虑多种子情景。
删除情景2.1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子树又又红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。如图22所示。
处理：

  • 将S的颜色设为P的颜色
  • 将P设为黑色
  • 将SR设为黑色
  • 对P进行左旋

红黑树 - 图18
图22 删除情景2.1.2.1
平衡后的图怎么不满足红黑树的性质？前文提醒过，R是即将替换的，它还参与树的自平衡，平衡后再替换到删除结点的位置，所以R最终可以看作是删除的。另外图2.1.2.1是考虑到第一次替换和自底向上处理的情况，如果只考虑第一次替换的情况，根据红黑树性质，SL肯定是红色或为Nil，所以最终结果树是平衡的。如果是自底向上处理的情况，同样，每棵子树都保持平衡状态，最终整棵树肯定是平衡的。后续的情景同理，不做过多说明了。
删除情景2.1.2.2：替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
兄弟结点所在的子树有红结点，我们总是可以向兄弟子树借个红结点过来，显然该情景可以转换为情景2.1.2.1。图如23所示。
处理：

  • 将S设为红色
  • 将SL设为黑色
  • 对S进行右旋，得到情景2.1.2.1
  • 进行情景2.1.2.1的处理

红黑树 - 图19
图23 删除情景2.1.2.2
删除情景2.1.2.3：替换结点的兄弟结点的子结点都为黑结点
好了，此次兄弟子树都没红结点“借”了，兄弟帮忙不了，找父母呗，这种情景我们把兄弟结点设为红色，再把父结点当作替代结点，自底向上处理，去找父结点的兄弟结点去“借”。但为什么需要把兄弟结点设为红色呢？显然是为了在P所在的子树中保证平衡（R即将删除，少了一个黑色结点，子树也需要少一个），后续的平衡工作交给父辈们考虑了，还是那句，当每棵子树都保持平衡时，最终整棵总是平衡的。
处理：

  • 将S设为红色
  • 把P作为新的替换结点
  • 重新进行删除结点情景处理

红黑树 - 图20
图24 情景2.1.2.3

删除情景2.2：替换结点是其父结点的右子结点
好啦，右边的操作也是方向相反，不做过多说明了，相信理解了删除情景2.1后，肯定可以理解2.2。
删除情景2.2.1：替换结点的兄弟结点是红结点
处理：

  • 将S设为黑色
  • 将P设为红色
  • 对P进行右旋，得到情景2.2.2.3
  • 进行情景2.2.2.3的处理

红黑树 - 图21
图25 删除情景2.2.1
删除情景2.2.2：替换结点的兄弟结点是黑结点
删除情景2.2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
处理：

  • 将S的颜色设为P的颜色
  • 将P设为黑色
  • 将SL设为黑色
  • 对P进行右旋

红黑树 - 图22
图26 删除情景2.2.2.1
删除情景2.2.2.2：替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
处理：

  • 将S设为红色
  • 将SR设为黑色
  • 对S进行左旋，得到情景2.2.2.1
  • 进行情景2.2.2.1的处理

红黑树 - 图23
图27 删除情景2.2.2.2
删除情景2.2.2.3：替换结点的兄弟结点的子结点都为黑结点
处理：

  • 将S设为红色
  • 把P作为新的替换结点
  • 重新进行删除结点情景处理

红黑树 - 图24
图28 删除情景2.2.2.3
综上，红黑树删除后自平衡的处理可以总结为：

  1. 自己能搞定的自消化（情景1）
  2. 自己不能搞定的叫兄弟帮忙（除了情景1、情景2.1.2.3和情景2.2.2.3）
  3. 兄弟都帮忙不了的，通过父母，找远方亲戚（情景2.1.2.3和情景2.2.2.3）

哈哈，是不是跟现实中很像，当我们有困难时，首先先自己解决，自己无力了总兄弟姐妹帮忙，如果连兄弟姐妹都帮不上，再去找远方的亲戚了。这里记忆应该会好记点～
最后再做个习题加深理解（请不熟悉的同学务必动手画下）：
*习题2：请画出图29的删除自平衡处理过程。
红黑树 - 图25