红黑树

数据结构演示网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

预备知识

树的知识框架结构如下图所示：

平衡二叉搜索树

平衡二叉搜索树（Balanced Binary Search Tree），英文简称 BBST。经典常见的平衡二叉搜索树是 AVL 树和红黑树。

二叉搜索树

二叉搜索树（Binary Search Tree）是二叉树的一种，英文简称 BST。又称为二叉查找树、二叉排序树。

它的特点是任何一个结点的值都大于其左子树的所有结点的值，任何一个结点的值都小于其右子树的所有结点的值。

平衡

平衡（Balance）：就是当结点数量固定时，左右子树的高度越接近，这棵二叉树越平衡（高度越低）。而最理想的平衡就是完全二叉树/满二叉树，高度最小的二叉树。

一棵二叉搜索树平均时间复杂度可以认为是树的高度 O(h)。像左边这棵，结点的左右子树的高度接近，属于一棵平衡二叉搜索树，O(h) = O(logn)；而右边这棵，高度达到了最大，已经退化成了链表，O(h)=O(n)。

改进二叉搜索树

当二叉树退化成链表时，性能是很低的，所以我们需要在结点的插入、删除操作之后，想办法让二叉搜索树恢复平衡（减小树的高度）。但是如果为了追求最理想的平衡，而增加了时间复杂度也不是很有必要，因此比较合理的方案就是：用尽量少的调整次数达到适度平衡。

由此引申出 AVL 树的概念。

AVL 树

AVL 树是最早发明的自平衡二叉搜索树之一，它取名自两位发明家的名字：G.M.Adelson-Velsky 和 E.M.Landis。

平衡因子

平衡因子（Balance Factor）：某结点的左右子树的高度差。

每个叶子结点的平衡因子都是 0。看这棵二叉搜索树，红色数字标注了每个结点对应的平衡因子。

举例：

8 的左子树高度为 2，右子树高度为 1，因此它的平衡因子为 1；5 的左子树高度为 0，右子树高度为 3，因此它的平衡因子为 -3；4 的左子树高度为 2，右子树高度为 4，因此它的平衡因子为 -2；

再看这棵 AVL 树和它每个结点对应的平衡因子：

可以看到 AVL 树具有以下特点：

• 每个结点的平衡因子只可能是 -1、0、1（如果绝对值超过 1，则认为是失衡）
• 每个结点的左右子树高度差不超过 1
• 搜索、插入、删除的时间复杂度是 O(logn)

B树

B 树（Balanced Tree）是一种平衡的多路搜索树，多用于文件系统、数据库的实现。这是一个简单的 3 阶 B 树：

特点

• 1 个结点可以存储超过 2 个元素，可以拥有超过 2 个子结点
• 拥有二叉搜索树的一些性质
• 平衡，每个结点的所有子树高度一致
• 比较矮

m 阶 B 树的性质（m ≥ 2）

m 阶 B 树指的是一个结点最多拥有 m 个子结点。假设一个结点存储的元素个数为 x，那么如果这个结点是：

• 根结点：1 ≤ x ≤ m - 1
• 非根结点：┌ m / 2 ┐ - 1 ≤ x ≤ m - 1

如果有子结点，子结点个数为 y = x + 1，那么如果这个结点是：

• 根结点：2 ≤ y ≤ m
• 非根结点：┌ m / 2 ┐ ≤ y ≤ m

向上取整（Ceiling），指的是取比自己大的最小整数，用数学符号 ┌ ┐ 表示。 向下取整（Floor），指的是取比自己小的最大整数，用数学符号 └ ┘ 表示。

比如 m = 3， 子结点个数 2 ≤ y ≤ 3，这个 B 树可以称为（2,3）树、2-3 树；

比如 m = 4， 子结点个数 2 ≤ y ≤ 4，这个 B 树可以称为（2,4）树、2-3-4 树；

比如 m = 5， 子结点个数 3 ≤ y ≤ 4，这个 B 树可以称为（3,5）树、3-4-5 树；

以此类推。

B 树 VS 二叉搜索树

这是一棵二叉搜索树，通过某些父子结点合并，恰好能与上面的 B 树对应。我们可以得到结论：

• B 树和二叉搜索树，在逻辑上是等价的
• 多代结点合并，可以获得一个超级结点，且 n 代合并的超级结点，最多拥有 (2^n) 个子结点 （至少是 (2^n) 阶 B 树）

什么是红黑树

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如在 Java 集合框架中，很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。

由于 TreeMap 就是由红黑树实现的，因此本文将使用 TreeMap 的相关操作的代码进行分析、论证。

黑色高度

从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度。

红黑树的 5 个特性

红黑树在原有的二叉查找树基础上增加了如下几个要求：

1. 每个节点要么是红色，要么是黑色；
2. 根节点永远是黑色的；
3. 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
4. 每个红色节点的两个子节点一定都是黑色；
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

• *

二分查找 和 红黑树的搜索

二分查找复杂度

二分查找（binary search），也称折半搜索，是一种在 有序数组 中 查找某一特定元素 的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

• 时间复杂度:折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。（n代表集合中元素的个数）
• 空间复杂度: O(1)。虽以递归形式定义，但是尾递归，可改写为循环。

代码示例：

递归：

int binarysearch(int array[], int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (array[mid] > target)
        return binarysearch(array, low, mid - 1, target);
    if (array[mid] < target)
        return binarysearch(array, mid + 1, high, target);
    return mid;
}

非递归：

int bsearchWithoutRecursion(int a[], int key) {
    int low = 0;
    int high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] > key)
            high = mid - 1;
        else if (a[mid] < key)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

二分查找中值的计算

这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：

• 算法一： mid = (low + high) / 2
• 算法二： mid = low + (high – low)/2

乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。算法一的做法，在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。

二分查找法的缺陷

二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。

数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。

解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。

红黑树搜索

由于红黑树本来就是平衡二叉搜索树，并且搜索也不会破坏树的平衡，所以搜索算法也与平衡二叉搜索树一致：

具体步骤：

1. 从根结点开始检索，把根结点设置为当前结点；
2. 若当前结点为空，返回 nil。
3. 若当前结点不为空，比较当前结点 key 与搜索 key 的大小；
4. 若当前结点 key 等于搜索 key，那么该 key 就是搜索目标，返回当前结点。
5. 若当前结点 key 大于搜索 key，把当前结点的左子结点设置为当前结点，重复步骤 2；
6. 若当前结点 key 小于搜索 key，把当前结点的右子结点设置为当前结点，重复步骤 2；

红黑树的插入

为了更清楚理解这部分内容，先声明几个概念：

• N - node：当前结点
• P - parent：父结点
• S - sibling：兄弟结点
• U - uncle：叔结点（P 的兄弟结点）
• G - grand：祖结点（P 的父结点）

插入操作包含两部分：定位插入的位置 和 插入自平衡

定位插入的位置

具体步骤：

1. 从根结点开始检索；
2. 若根结点为空，那么插入结点设为根结点，结束。
3. 若根结点不为空，那么把根结点设为当前结点；
4. 若当前结点为 nil，返回当前结点的父结点，结束。
5. 若当前结点 key 等于搜索 key，那么该 key 所在结点就是插入结点，更新结点的值，结束。
6. 若当前结点 key 大于搜索 key，把当前结点的左子结点设置为当前结点，重复步骤4；
7. 若当前结点 key 小于搜索 key，把当前结点的右子结点设置为当前结点，重复步骤4；

自平衡方式：

• 左旋
  • 以某个节点作为支点（旋转节点）
  • 其右子节点变为旋转节点的父节点
  • 右子节点的左子节点变为旋转接点的右子节点。

• 右旋
  • 以某个节点作为支点（旋转节点）
  • 其左子节点变为旋转节点的父节点
  • 左子节点的右子节点变为旋转节点的左子节点

• 变色
  • 节点的颜色黑红互变

建议新添加的结点默认为红色，因此这样能够让红黑树的性质尽快满足。不过如果添加的结点是根结点，设为黑色即可。

红黑树插入可能出现的所有场景：

• 场景 1：红黑树为空树

红黑树的性质2：根结点必须是黑色。

处理：直接把插入结点设成黑色并作为根结点。

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

二叉搜索树中不能插入相同元素，既然结点的 key 已经存在，红黑树也已平衡，无需重复插入。

处理：

• 将插入结点设为将要替换结点的颜色
• 更新当前结点的值为插入结点的值

场景 3：插入结点的父结点为黑色

插入的结点默认是红色的，当它的父结点是黑色时，并不会破坏平衡。

处理：直接插入。

场景 4：插入结点的父结点为红色

如果插入结点的父结点为红色，那么父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，后续的旋转操作需要祖父结点的参与。

场景 4.1：存在叔父结点，且为红色

由红黑树性质4可知：红色结点不能连续。那么此时该插入子树的红黑层数的情况是：黑-红-红。显然最简单的处理方式就是将其改为：红-黑-红。

处理：

• 将父结点和叔父结点变为黑色
• 将祖父结点变为红色
• 将祖父结点设置为当前插入结点

场景 4.2：叔父结点不存在或为黑色，插入结点的父结点是祖父结点的左子结点

这种场景下，叔父结点所在的子树的黑色结点就比父结点所在子树的多，不满足红黑树的性质5。

场景 4.2.1：插入结点是左子树

处理：

• 将父结点变为黑色
• 将祖父结点变为红色
• 将祖父结点右旋

场景 4.2.2：插入结点是左子树

这种场景显然可以转换为 4.2.1。

处理：

• 将父结点进行左旋
• 将父结点设为插入结点，得到场景 4.2.1
• 进行场景 4.2.1 的处理

场景4.3：叔父结点不存在或为黑色，插入结点的父结点是祖父结点的右子结点

相当于场景 4.2 的方向反转，直接看图。

场景 4.3.1：插入结点是左子树

处理：

• 将父结点变为黑色
• 将祖父结点变为红色
• 对祖父结点进行左旋

场景 4.3.2：插入结点是右子树

处理：

• 将父结点进行右旋
• 将父结点设置为插入结点，得到场景 4.3.1
• 进行场景 4.3.1 的处理

下面举个例子，往一棵红黑树中插入元素，整棵树的变换如下图所示：

红黑树删除

红黑树删除操作也分为两步：

定位删除的位置

定位删除位置可以复用红黑树搜索的操作。

如果不存在目标结点，忽略本次操作；如果找到目标结点，删除后进行自平衡处理

删除后实现自平衡

二叉搜索树删除的时候可能出现三种场景：

• 场景一：若删除结点无子结点，==红色==的直接删除即可，黑色的需要自平衡；
• 场景二：若删除结点只有一个子结点，用子结点替换删除结点，得到场景一；
• 场景三：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点，得到场景一或者2。

具体应用，可以借助这张图理解：

我们可以发现，另外两种二叉树的删除场景都可以通过相互转换变为场景一。

在场景二情况下：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为场景三，一直自顶向下转换，总是能转换为场景一。

在场景三情况下：删除结点用后继结点，如果后继结点有右子结点，那么相当于转换为场景二，否则转为场景一。

综上所述，删除的结点可以看作删除替换结点，且替换结点最后总是在树末。

下面总结一下红黑树删除可能出现的所有场景。

为了方面理解，我们先约定一下结点的叫法：

• R - 替换结点
• P - 替换结点的父结点
• S - 替换结点的兄弟结点
• SL - 兄弟结点的左子结点
• SR - 兄弟结点的右子结点
• 灰色 - 结点颜色可能是红色，也可能是黑色

注意：R 是即将被替换到删除结点的位置的替换结点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再替换到删除结点的位置，才算删除完成。

场景 1：替换结点为红色

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

处理：替换结点颜色变为删除结点的颜色。

场景 2：替换结点为黑色

当替换结点是黑色时，就必须进行自平衡处理了，我们可以通过区分替换结点是其父结点的左子结点还是右子结点，来做不同的旋转，使树重新平衡。

场景 2.1：替换结点是左子树

场景 2.1.1：替换结点的兄弟结点为红色

若兄弟结点是红结点，那么根据红黑树性质4，兄弟结点的父结点和子结点肯定为黑色，按照下图方式处理，得到删除场景 2.1.2.3。

处理：

• 将兄弟结点变为黑色
• 将父结点变为红色
• 对父结点进行左旋，得到场景 2.1.2.3
• 进行场景 2.1.2.3 的处理

场景 2.1.2：替换结点的兄弟结点为黑色

当兄弟结点为黑时，其父结点和子结点的具体颜色也无法确定，此时又得考虑多种子场景。

场景 2.1.2.1：替换结点的兄弟结点的右子结点为红色，左子结点任意颜色

即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子结点又是红色，那么我们直接向右子树“借”个红结点来补充黑结点，并进行旋转处理。如图所示：

处理：

• 将兄弟结点的颜色变为父结点的颜色
• 将父结点变为黑色
• 将兄弟结点的右子结点变为黑色
• 对父结点进行左旋

场景 2.1.2.2：替换结点的兄弟结点的右子结点为黑色，左子结点为红色

兄弟结点所在的子树有红结点，又可以向兄弟子树“借”个红结点过来，这就转换回了场景 2.1.2.1。如图所示：

处理：

• 将兄弟结点变为红色
• 将兄弟结点的左子结点变为黑色
• 对兄弟结点进行右旋，得到场景 2.1.2.1
• 进行场景 2.1.2.1 的处理

场景 2.1.2.3：替换结点的兄弟结点的子结点都为黑色

兄弟子树没有红结点可以“借”了，再向父结点“借”。如果父结点是黑色，为了让父结点在所在的子树中保证平衡（替换结点即将删除，少了一个黑色结点，子树也需要少一个）先把兄弟结点变为红色，再让父结点成为新的替换结点。

处理：

• 如果父结点为黑色
  • 将兄弟结点变为红色
  • 将父结点作为新的替换结点
  • 重新进行删除结点的场景处理
• 如果父结点为红色
  • 替换结点的父结点和替换结点的兄弟结点颜色交换
  • 删除结点和替换结点的值交换后，删除替换结点

场景 2.2：替换结点是右子树

实际上是场景 2.1 的镜像操作。

场景 2.2.1：替换结点的兄弟结点为红色

处理：

• 将兄弟结点变为黑色
• 将父结点变为红色
• 对父结点进行右旋，得到场景 2.2.2.3
• 进行场景 2.2.2.3 的处理

场景 2.2.2：替换结点的兄弟结点为黑色

场景 2.2.2.1：替换结点的兄弟结点的左子结点为红色，右子结点任意颜色

处理

处理：

• 将兄弟结点的颜色变为父结点的颜色
• 将父结点变为黑色
• 将兄弟结点的左子结点变为黑色
• 对父结点进行右旋

场景 2.2.2.2：替换结点的兄弟结点的左子结点为黑色，右子结点为红色

处理：

• 将兄弟结点变为红色
• 将兄弟结点的右子结点设为黑色
• 对兄弟结点进行左旋，得到场景 2.2.2.1
• 进行场景 2.2.2.1 的处理

场景 2.2.2.3：替换结点的兄弟结点的子结点都为黑色

处理：

• 如果父结点为黑色
  • 将兄弟结点变为红色
  • 将父结点作为新的替换结点
  • 重新进行删除结点的场景处理
• 如果父结点为红色
  • 替换结点的父结点和替换结点的兄弟结点颜色交换
  • 删除结点和替换结点的值交换后，删除替换结点

红黑树的 Java 实现

红黑树类：

package com.tree;

import com.sun.source.tree.WhileLoopTree;

/**
 * @description:
 * @author: NicZSAMA
 * @date: Created Class in 2020/7/23 3:23 下午
 * @version:
 * @modified By:
 * 
 *       @author: NicZSAMA
 *       @date: Created delete method in 2020/07/25 12:23 下午
 */
public class RBTree<K extends Comparable<K>, V> {
    public static final boolean RED = true;
    public static final boolean BLACK = false;
    /**
     * 树根
     */
    public RBNode root;

    public RBNode getRoot() {
        return root;
    }

    /**
     * 获取当前节点父节点
     */
    private RBNode getParentNode(RBNode node) {
        if (node != null) {
            return node.getParent();
        }
        return null;
    }

    /**
     * 获取当前节点是否是红色
     */
    private boolean isRed(RBNode node) {
        if (node != null) {
            return node.getColor() == RED;
        }
        return false;
    }

    /**
     * 获取当前节点是否是黑色
     */
    private boolean isBlack(RBNode node) {
        if (node != null) {
            return node.getColor() == BLACK;
        }
        return false;
    }

    /**
     * 设置当前节点红色
     */
    private void setRed(RBNode node) {
        if (node != null) {
            node.setColor(RED);
        }
    }

    /**
     * 设置当前节点黑色
     */
    private void setBlack(RBNode node) {
        if (node != null) {
            node.setColor(BLACK);
        }
    }

    /**
     * 中序打印树
     */
    public void inOrderPrint() {
        inOrderPrint(this.root);
    }

    public void inOrderPrint(RBNode node) {
        if (node != null) {
            inOrderPrint(node.left);
            System.out.println("key:" + node.key + ",value:" + node.value);
            inOrderPrint(node.right);
        }
    }


    /**
     * 左旋方法:以 X 节点左旋
     *   P                 P
     *   |                 |
     *   x                 z
     *  / \        ==>    / \
     * y   z             x  z2
     *    / \           / \
     *   z1 z2         y  z1
     * <p>
     * 1. 设置 z1 父节点为 x,设置 x 右节点为 z1
     * 2. 当 x 的父节点不为空时，使 z 节点与 x 的父节点 p 建立父子关系，
     * 3. 设置 x 父节点为 z,z 的左子节点为 x
     */

    private void leftRotate(RBNode x) {
        RBNode z = x.right;
        //设置 z1 父节点为 x,设置 x 右节点为 z1
        x.right = z.left;
        if (z.left != null) {
            z.left.parent = x;
        }
        //当 x 的父节点不为空时，使 z 节点与 x 的父节点建立父子关系，
        if (x.parent != null) {
            z.parent = x.parent;
            if (x == x.parent.left) {
                x.parent.left = z;
            } else {
                x.parent.right = z;
            }
        } else {
            z.parent = null;
            this.root = z;
        }
        //设置 x 父节点为 z,z 的左子节点为 x
        x.parent = z;
        z.left = x;

    }

    ;


    /**
     * 右旋方法:以  z 节点左旋
     *     P                P
     *     |                |
     *     z                x
     *    / \       ==>    / \
     *   x  z2            y   z
     *  / \                  / \
     * y  z1                z1 z2
     * <p>
     * 1. 设置 z1 父节点为 z ,设置 z 左节点为 z1
     * 2. 当 z 的父节点不为空时，使 x 节点与 z 的父节点 p 建立父子关系，
     * 3. 设置 z 父节点为 x,x 的右子节点为 z
     */


    private void rightRotate(RBNode z) {
        RBNode x = z.left;
        z.left = x.right;
        //设置 z1 父节点为 z ,设置 z 左节点为 z1
        if(x.right!=null){
            x.right.parent = z;
        }

        //当 z 的父节点不为空时，使 x 节点与 z 的父节点 p 建立父子关系，
        if (z.parent != null) {
            x.parent = z.parent;
            if (z.parent.left == z) {
                z.parent.left = x;
            } else {
                z.parent.right = x;
            }
        } else {
            x.parent = null;
            this.root = x;
        }
        //设置 z 父节点为 x,x 的右子节点为 z
        z.parent = x;
        x.right = z;

    }

    /**
     * 公开的查询方法
     * @param key
     * @return
     */
    public RBNode getNode(K key){
        RBNode<K, Object> node = this.root;
        while (null != node){
            int cmd = node.key.compareTo(key);
            if(cmd > 0){
               node = node.left;
            }else if (cmd < 0) {
                node = node.right;
            }else {
                return node;
            }

        }
        return null;
    }


    /**
     * 公开的插入方法
     *
     * @param key
     * @param value
     */
    public void insert(K key, V value) {
        RBNode<K, Object> node = new RBNode<>();
        node.setKey(key);
        node.setValue(value);
        //新节点一定是红色
        node.setColor(RED);
        //插入树
        insertNode(node);
    }

    /**
     * 内部插入树方法
     *
     * @param node
     */
    private void insertNode(RBNode node) {
        //查找当前node的父节点
        RBNode parent = null;
        RBNode x = this.root;
        while (x != null) {
            parent = x;
            //  cmp > 0 说明node key大于 x key 需要去右子树找
            //  cmp == 0 说明node key等于 x key 需要执行替换操作
            //  cmp < 0 说明node key小于 x key 需要去左子树找
            int cmp = node.key.compareTo(x.key);
            if (cmp > 0) {
                x = x.right;
            } else if (cmp == 0) {
                x.setValue(node.getValue());
                return;
            } else {
                x = x.left;
            }

        }

        node.parent = parent;
        if (parent != null) {
            if (node.key.compareTo(parent.key) > 0) {
                parent.right = node;
            } else {
                parent.left = node;
            }
        } else {
            this.root = node;
        }

        //平衡方法
        insertFixUp(node);
    }


    /**
     * 红黑树修复方法
     * 1. 红黑树为空树时：将根节点设置为黑色
     * 2. 插入节点已经存在： 执行替换操作（无）不影响黑高，不处理
     * 3. 插入节点的父节点是黑色，插入节点为红色，不影响黑高，不处理
     * <p>
     * 需要处理的
     * 4. 插入节点的父节点是红色：
     * 4.1 叔节点存在且为红色（叔父双红）==》将父节点和叔节点染色为黑色，将祖节点染色为红色，并且将祖节点设置为当前节点进行处理
     * 4.2 叔节点不存在，或者叔节点为黑色
     * 4.2.1 父节点是祖节点左子树
     * 4.2.1.1 插入节点是父节点左节点（双红LL）==》将父节点染色黑色，将祖节点染色红色，然后将祖节点右旋，完成。
     * 4.2.1.2 插入节点是父节点右节点（双红LR）==》将父节点左旋，得到LL，再将父节点设置为当前节点进行LL处理，完成。
     * 4.2.2 父节点是祖节点右子树
     * 4.2.2.1 插入节点是父节点左节点（双红RL）==》将父节点右旋，得到RR，再将父节点设置为当前节点进行RR处理，完成。
     * 4.2.2.2 插入节点是父节点右节点（双红RR）==》将父节点染色黑色，将祖节点染色红色，然后将祖节点左旋，完成。
     */

    private void insertFixUp(RBNode node) {
        //将根节点设置为黑色
        this.root.color = BLACK;
        RBNode parent = getParentNode(node);
        RBNode grand = getParentNode(parent);

        //4 插入节点的父节点是红色：
        if (parent != null && parent.color == RED) {
            //如果parent为red，一定存在grand，因为根节点必定黑色
            RBNode uncle = null;

            //4.2.1 父节点是祖节点左子树
            if (parent == grand.left) {

                uncle = grand.right;
                //4.1 叔节点存在且为红色（叔父双红）
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grand);
                    insertFixUp(grand);
                    return;
                }
                //4.2 叔节点不存在，或者叔节点为黑色
                if (uncle == null || isBlack(uncle)) {
                    //4.2.1.1 插入节点是父节点左节点（双红LL）

                    if (node == parent.left) {
                        setBlack(parent);
                        setRed(grand);
                        rightRotate(grand);
                        return;
                    } else {
                        //4.2.1.1 插入节点是父节点右节点（双红LR）
                        leftRotate(parent);
                        insertFixUp(parent);
                        return;

                    }


                }

                //4.2.2 父节点是祖节点右子树
            } else {
                uncle = grand.left;
                //4.1 叔节点存在且为红色（叔父双红）
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grand);
                    insertFixUp(grand);
                    return;
                }

                //4.2 叔节点不存在，或者叔节点为黑色
                if (uncle == null || isBlack(uncle)) {
                    //4.2.2.1 插入节点是父节点左节点（双红RL）
                    if (node == parent.left) {
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    } else {
                        //4.2.2.2 插入节点是父节点右节点（双红RR）
                       setBlack(parent);
                       setRed(grand);
                       leftRotate(grand);
                        return;

                    }


                }


            }


        }


    }

    /**
     * 外部删除方法
     * @param key
     * @return
     */


    public boolean delete(K key){
        if(null != key){
            if(null != root){
                return deleteNode(key, root, null);
            }
        }
        return false;
    }

    /**
     * 内部删除节点方法
     *
     *
     *
     * @param key
     */

    private Boolean deleteNode(K key, RBNode<K,V> current, RBNode<K,V> parent){
        if(null != current){
            if(key.compareTo(current.key) > 0){
                return deleteNode(key, current.right, current);
            }
            if(key.compareTo(current.key) < 0){
                return deleteNode(key, current.left, current);
            }
            if(key.compareTo(current.key) == 0){
                if((null != current.left) && (null != current.right)){ //将要删除的节点下有两个子节点
                    deleteTwoChildrenNode(current);
                }else{
                    if((null == current.left) && (null == current.right)){
                        //将要删除的节点没有子节点
                        if (current == this.root){
                            this.root = null;
                            return true;
                        }
                        deleteFixUp(current);
                        if(current.key.compareTo(parent.key) > 0){
                            parent.right = null;
                        }else{
                            parent.left = null;
                        }
                    }else{ // 将要删除的节点下有一个子节点,
                        deleteOneChildrenNode(current);
                    }
                }
                return true;
            }
        }
        return false;
    }

    /**
     * 处理删除节点有一个子节点的情况
     * @param node
     */
    private void deleteOneChildrenNode(RBNode node){
        //直接删除
        RBNode replaceNode = (null != node.left)?node.left:node.right;
        deleteLeafNode(node,replaceNode);
    }

    /**
     * 处理删除节点有两个子节点的情况
     * @param node
     */
    private void deleteTwoChildrenNode(RBNode node){
        RBNode replaceNode = getReplaceNode(node);
        if(null == replaceNode.right && null == replaceNode.left) {
            deleteLeafNode(node,replaceNode);
        }else{
            node.key = replaceNode.key;
            node.value = replaceNode.value;
            deleteOneChildrenNode(replaceNode);
        }
    }

    /**
     * 获取兄弟节点
     * @param node
     * @return
     */
    private RBNode getBrother(RBNode node){
        if(null == node){
            return null;
        }
        RBNode parent = node.parent;
        if(null == parent){
            return null;
        }
        if(node.key.compareTo(parent.key) > 0){
            return parent.left;
        }else{
            return parent.right;
        }
    }

    /**
     * 删除的平衡方法
     * @param node
     */
    private void deleteFixUp(RBNode node){


        while((node != root) && (BLACK == node.color)){//场景 2：替换结点为黑色
            RBNode parent = node.parent;
            RBNode brother = getBrother(node);
            if(null != brother) {
                if (node.key.compareTo(parent.key) > 0) { // 场景 2.2：替换结点是右子树

                    if (RED == brother.color) { // 场景 2.2.1：替换结点的兄弟结点为红色
                        brother.color = BLACK;
                        brother.right.color = RED;
                        rightRotate(parent);
                        break;
                    } else {
                        //场景 2.2.2：替换结点的兄弟结点为黑色

                        if ((null == brother.left) && (null == brother.right)) { //场景 2.2.2.3：替换结点的兄弟结点的子结点都为黑色
                            // case4: 兄弟节点是黑色的，且没有子节点
                            brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
                            node = parent;
                        } else {
                            if ((null != brother.left) && (RED == brother.left.color)) {//场景 2.2.2.1：替换结点的兄弟结点的左子结点为红色，右子结点任意颜色
                                // case1: 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的）
                                //case3: 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
                                brother.color = parent.color;
                                parent.color = BLACK;
                                brother.left.color = BLACK;
                                rightRotate(parent);
                                break;
                            } else {//场景 2.2.2.2：替换结点的兄弟结点的左子结点为黑色，右子结点为红色
                                // case2: 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
                                brother.right.color = BLACK;
                                brother.color = RED;
                                leftRotate(brother);
                            }
                        }
                    }
                } else {// 场景 2.1：替换结点是左子树
                    if (RED == brother.color) { // 场景 2.1.1：替换结点的兄弟结点为红色
                        brother.color = BLACK;
                        brother.left.color = RED;
                        leftRotate(parent);
                        break;

                    } else {//场景 2.1.2：替换结点的兄弟结点为黑色

                        if ((null == brother.left) && (null == brother.right)) {
                            // case4: 兄弟节点是黑色的，且没有子节点
                            brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
                            node = parent;
                        } else {

                            if ((null != brother.right) && (RED == brother.right.color)) { //场景 2.1.2.1：替换结点的兄弟结点的右子结点为红色，左子结点任意颜色
                                // case1 : 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
                                // case3 : 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
                                brother.color = parent.color;
                                parent.color = BLACK;
                                brother.right.color = BLACK;
                                leftRotate(parent);
                                break;
                            } else { //场景 2.1.2.2：替换结点的兄弟结点的右子结点为黑色，左子结点为红色
                                // case2: 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的）
                                brother.left.color = BLACK;
                                brother.color = RED;
                                rightRotate(brother);
                            }
                        }
                    }
                }
            }else {
                return ;
            }
        }

        node.color = BLACK;//场景 1：替换结点为红色

    }

    /**
     * 删除一个叶子节点
     * @param node
     */
    private void deleteLeafNode(RBNode node,RBNode replaceNode){
        node.key = replaceNode.key;
        node.value = replaceNode.value;
        deleteFixUp(replaceNode);
        if(replaceNode == replaceNode.parent.right){
            replaceNode.parent.right = null;
        }else{
            replaceNode.parent.left = null;
        }

    }

    /**
     * 获取 后继节点
     * @param node
     * @return
     */
    private RBNode getReplaceNode(RBNode node){
        if (null == node) {
            return null;
        }
        // 获取 后继节点
        RBNode p;
        if (null != node.right) {
            p = node.right;
            while (null != p.left){
                p = p.left;
            }
        }else {
            p = node.parent;
            RBNode c = node;
            while (null != p && c == p .right){
                c = p;
                p = p.parent;
            }
        }
        return p;

    }



    static class RBNode<K extends Comparable<K>, V> {
        public RBNode parent;
        public RBNode left;
        public RBNode right;
        public boolean color;
        public K key;
        public V value;

        public RBNode() {
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public boolean getColor() {
            return color;
        }
    }


}

树结构打印类

package com.tree;

import javax.swing.tree.TreeNode;

/**
 * @description:
 * @author: NicZSAMA
 * @date: Created in 2020/7/23 5:56 下午
 * @version:
 * @modified By:
 */
public class TreeOperation {
    /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

    // 用于获得树的层数
    public static int getTreeDepth(RBTree.RBNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }


    private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) {return;}
        // 先将当前节点保存到二维数组中
        String color =  currNode.color?"R":"B";
        res[rowIndex][columnIndex] = String.valueOf(currNode.key+":"+color );

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) {return;}
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(RBTree.RBNode root) {
        if (root == null) {System.out.println("EMPTY!");}
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

测试类：

package com.tree;

import java.security.Key;
import java.util.Scanner;

/**
 * @description:
 * @author: NicZSAMA
 * @date: Created in 2020/7/23 5:50 下午
 * @version:
 * @modified By:
 */
public class RBTreeTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        RBTree<Integer,Object> rbTree = new RBTree();

        //添加测试
 /*       while (true){
            System.out.println("请输入key：");
            Integer key = Integer.parseInt(scanner.next());
            System.out.println();
            rbTree.insert(key,null);

            TreeOperation.show(rbTree.getRoot());
        }*/

        //查询测试
/*
        rbTree.insert(1,1);
        rbTree.insert(2,2);
        rbTree.insert(3,3);
        rbTree.insert(4,4);
        rbTree.insert(5,5);
        rbTree.insert(6,6);
        rbTree.insert(7,7);
        while (true){
            System.out.println("请输入要查询的key：");
            Integer key = Integer.parseInt(scanner.next());
            System.out.println();
            RBTree.RBNode node = rbTree.getNode(key);
            System.out.println("查询的value是："+node.value);
            System.out.println();
            TreeOperation.show(rbTree.getRoot());
        }*/


        //删除测试


        rbTree.insert(1,1);
        rbTree.insert(2,2);
        rbTree.insert(3,3);
        rbTree.insert(4,4);
        rbTree.insert(5,5);
        rbTree.insert(6,6);
        rbTree.insert(7,7);
        while (true){
            System.out.println("请输入要删除的key：");
            Integer key = Integer.parseInt(scanner.next());
            System.out.println();
            Boolean aBoolean = rbTree.delete(key);
            System.out.println("删除结果是："+aBoolean);
            System.out.println();
            TreeOperation.show(rbTree.getRoot());
        }


    }
}

该文图片及部分笔记整理自 掘金 作者：FiTeen 链接:https://juejin.im/post/5e509b27f265da57455b3f33

源码学习自B站 UP主：小刘讲源码，链接：https://www.bilibili.com/video/BV1UJ411J7CU?p=1

知乎专栏 作者：Cailiang 链接：https://zhuanlan.zhihu.com/p/22800206