红黑树也是二叉查找树的一种，但是对于平衡二叉查找树来说，红黑树是更加进步一些的自平衡二叉查找树。红黑树在进行插入和删除操作的时候，会重新自处理达到平衡状态。红黑树顾名思义，其中具备红色和黑色两种节点，而且其具备以下五种特性。

  1. 每个节点要么是黑色，要么是红色，不允许没有颜色或者其他颜色的节点存在。
  2. 红黑树的根节点是黑色的。
  3. 红黑树的所有叶子节点也都是黑色的。
  4. 每个红色节点的两个孩子节点都一定是黑色的。红色节点不能拥有红色父节点和孩子节点。
  5. 任意一个节点都每个叶子节点的路径中都包含有数量相同的黑色节点。
    1. 推论1：如果一个节点存在黑色孩子节点，那么这个节点一定有两个孩子结点。

红黑树所使用的节点类与AVL略有不同，主要是增加了每个节点的颜色属性。以下是红黑树节点的示例。

  1. public class RBNode extends BSTNode {
  2.     private Color color;
  4.     public RBNode(Integer value) {
  5.         super(value);
  6.         this.color = Color.Red;
  7.     }
  9.     public Color getColor() {
  10.         return this.color;
  11.     }
  13.     public void recolor(Color color) {
  14.         this.color = color;
  15.     }
  17.     public bool isBlack() {
  18.         return this.color == Color.Black;
  19.     }
  21.     public bool isRed() {
  22.         return this.color == Color.Red;
  23.     }
  25.     public Optional<RBNode> getSibling() {
  26.            return this.getParent()
  27.                 .map(this.isLeftChild() ? RBNode::getRightChild : RBNode::getLeftChild);
  28.     }
  29.     }
  31.     public static enum Color {
  32.         Red, Black;
  33.     }
  34. }

节点搜索

红黑树的节点搜索与二叉查找树的检索方法相同，其时间复杂度同样为红黑树 - 图1。但是红黑树能够有更高的检索效率，完全来自于其插入操作和删除操作的自平衡特性。

节点插入

与AVL相同，红黑树在插入的时候也是先寻找到要插入节点的父级节点，然后把新节点以叶子节点的身份添加到父级节点的左孩子或者右孩子。除了构造一棵新的红黑树以外，新插入的节点颜色都为红色，这样当相邻的两级节点都为红色的时候，就说明红黑树不再平衡，需要进行再平衡操作。

红黑树的平衡比AVL的平衡多一个步骤，其中对于一个节点的左旋和右旋两个操作是相同的，但是红黑树多了一个变色的操作。这是因为在执行了旋转之后，树的平衡已经发生了变化，节点的颜色需要能够立刻标识出这种变化带来的结果。

在红黑树中进行节点插入操作，一般会有以下八种情况出现。

  1. 红黑树是空树，新节点直接作为根节点插入，节点颜色变为黑色。
  2. 红黑树中有节点的值与新节点相同，此时可根据实际需求更新树中的节点或者报错。
  3. 定位到的父节点为黑色，新节点可以直接插入。
  4. 定位到的父节点为红色，则父节点不可能为根节点，必定存在祖父节点。则情况可以细分为以下几种。
    1. 父节点存在红色的兄弟节点，那么祖父节点必定为黑色。此时需要将祖父节点变为红色，父节点及其兄弟节点变为黑色，之后将新节点插入，最后重新平衡祖父节点。
    2. 父节点不存在兄弟节点或者存在黑色的兄弟节点，父节点是祖父节点的左孩子，此时需要以新节点的插入位置来确定后续的操作。
      1. 如果新节点是父节点的左孩子，那么就需要将祖父节点变为红色，父节点变为黑色，之后将祖父节点进行右旋。
      2. 如果新节点是父节点的右孩子，那么就需要先对父节点进行左旋，然后以父节点作为新节点执行（4.b.i）的操作。
    3. 父节点不存在兄弟节点或者存在黑色的兄弟节点，父节点是祖父节点的右孩子，此时也同样需要以新节点的插入位置来确定后续的操作。
      1. 如果新节点是父节点的右孩子，那么需要将祖父节点变为红色，父节点变为黑色，之后将祖父节点进行左旋。
      2. 如果新节点是父节点的左孩子，那么需要先对父节点进行右旋，然后以父节点作为新节点执行（4.c.i）的操作。

当兄弟节点是黑色而祖父节点是红色的时候，说明兄弟节点所在的子树黑色节点比父节点所在的子树中的黑色节点数量要多，所以需要进行旋转。每次进行旋转的节点都是红色节点。

以上八种情况就像是红黑树进行自平衡的公式，在插入节点的时候只需要直接照做即可。以下是实现自平衡的代码。

  1. public class RBTree {
  2.     /* 自平衡方法所接受的节点是已经加入到红黑树的节点，
  3.      * 这个方法需要在每次插入新节点之后调用。
  4.      */
  5.     public class rebalance(RBNode newNode) {
  6.         if (!newNode.getParent().isPresent()) {
  7.             newNode.recolor(RBNode.Color.Black);
  8.             return;
  9.         }
  10.         if (newNode.getParent().map(RBNode::isBlack).get()) {
  11.             return;
  12.         }
  13.         Optional<RBNode> parent = newNode.getParent();
  14.         Optional<RBNode> sibling = parent.map(RBNode::getSilbling);
  15.         Optional<RBNode> grand = parent.map(RBNode::getParent);
  16.         if (silbling.isPresent() && sibling.map(RBNode::isRed).orElse(false)) {
  17.             newNode.getParent().ifPresent(node -> node.recolor(RBNode.Color.Black));
  18.             sibling.ifPresent(node -> node.recolor(RBNode.Color.Black));
  19.             grand.ifPresent(node -> {
  20.                 node.recolor(RBNode.Color.Red);
  21.                 this.rebalance(node);
  22.             });
  23.             return;
  24.         }
  25.         if (!sibling.isPresent() || sibling.map(RBNode::isBlack).orElse(false)) {
  26.             if (parent.map(RBNode::isLeftChild().orElse(false)) {
  27.                 if (newNode.isRightChild()) {
  28.                     this.leftRotate(parent.get());
  29.                     newNode = parent.get();
  30.                     parent = newNode.getParent();
  31.                     grand = parent.map(RBNode::getParent);
  32.                 }
  33.                 parent.ifPresent(node -> node.recolor(RBNode.Color.Black));
  34.                 grand.ifPresent(node -> {
  35.                     node.recolor(RBNode.Color.Red);
  36.                     this.rightRotate(node);
  37.                 });
  38.             }
  39.             if (parent.map(RBNode::isRightChild).orElse(false)) {
  40.                 if (newNode.isLeftChild()) {
  41.                     this.rightRotate(parent.get());
  42.                     newNode = parent.get();
  43.                     parent = newNode.getParent();
  44.                     grand = parent.map(RBNode::getParent);
  45.                 }
  46.                 parent.ifPresent(node -> node.recolor(RBNode.Color.Black));
  47.                 grand.ifPresent(node -> {
  48.                     node.recolor(RBNode.Color.Red);
  49.                     this.leftRotate(node);
  50.                 });
  51.             }
  52.         }
  53.     }
  54. }

节点删除