14、红黑树

【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

前言

本篇文章我将向大家介绍最负盛名的自平衡二叉查找树——红黑树。

红黑树由鲁道夫.贝尔——一位慕尼黑科技大学信息技术教授发明。1978 年，在罗伯特.塞奇威克发表的一篇论文中为这种数据结构正式命名为红黑树，并提供了完整的复杂度证明。

红黑树虽然繁琐，但是它在实践中有着非常高的效率，因为红黑树是自平衡的（红黑树实现的其实是一种伪平衡，在后文中我们会提到），所以它不会出现像二分搜索树在极端的情况下退化为链表的这种情况，可以在 #card=math&code=O%28logN%29&id=gOzMr) 的时间做元素的查找，插入以及删除操作。因为其优秀的性能，在一些底层数据结构设计中被广泛使用——譬如 Java 语言中的 TreeMap 与 TreeSet 就是红黑树。

接下来，我们就一起探索，红黑树究竟是怎样的一种数据结构。

红黑树与 2-3 树

在介绍大名鼎鼎的红黑树之前，我们先来看一下 2-3 树这种数据结构。提前了解 2-3 树对我们接下来学习红黑树有很大的帮助，因为红黑树与 2-3 树的原理是相通的，并且 2-3 树要比复杂的红黑树更容易理解。

什么是 2-3 树呢？首先，2-3 树是一种绝对平衡的多叉树。

我们都知道平衡二叉树的概念——平衡二叉树是一棵二分搜索树。它或者是一颗空树，或它的左子树与右子树的高度之差（左子树的高度 - 右子树的高度，其别名叫平衡因子：balance factor）的绝对值不超过 1，且一棵平衡二叉树的左右子树均是一棵平衡二叉树。

如下图所示，该树就是一棵平衡二叉树：

而所谓的绝对平衡则比平衡二叉树里面的平衡性要更加严格，绝对平衡的定义是：对于树中任意一个节点，左右子树高度相同。

如上图所示，该示意图表示一棵 2-3 树。这棵树满足了绝对平衡的定义。

除此之外， 2-3 树并不是一棵标准的二叉树，而是一棵多叉树。在上图的 2-3 树中，我们可以看到，有的节点存放了一个元素，有的节点存放了两个元素。存放了一个元素的节点我们称之为 2-节点，而存放了两个元素的节点我们则称之为 3-节点，2-3 树中只具有这两种类型的节点，这也是 2-3 树其名字的由来。

接下来，我将演示向 2-3 树插入元素的操作，让我们一起来看一下 2-3 树究竟是通过什么神奇的操作来维持整棵树是绝对平衡的。

首先，我们向一棵空的 2-3 树中插入一个节点 “42”，然后再插入节点 “37”:

向 2-3 树插入节点的原则与二分搜索树是一样的，不过它还会遵循另外一个原则，那就是：新的节点永远不会插入到一个空的位置上。

如果这棵树是二分搜索树，那么节点 “37” 将会插入到节点 “42” 的左孩子的位置上，不过这样一来，就破坏了 2-3 树的绝对平衡性。所以，节点 “37” 并不会插入到一个空的位置，而是与节点 “42” 融合成为一个新的 3-节点：

接下来，我们向 2-3 树中插入元素 “12”：

依据我们的原则“新的节点永远不会插入到一个空的位置上”，节点 “12” 将会和当前的 3-节点融合成为一个 “4-节点”：

然后，这个 4-节点会分裂成 3 个 2-节点，来维持绝对平衡的状态并保证遵循 2-3 树的定义：

我们继续向当前的 2-3 树中插入元素 ”18“：

向当前的 2-3 树中插入元素 ”6“：

向当前的 2-3 树中插入元素 ”11“：

向当前的 2-3 树中插入元素 ”5“：

通过上面几张模拟图的演示，想必大家已经能够初步地掌握 2-3 树的特点以及在向 2-3 树添加元素时，2-3 树如何维护绝对平衡。

我们之前说过，红黑树和 2-3 树的本质是相同的，如果大家理解了 2-3 树，那么接下来我要介绍的红黑树也就不难理解了。2-3 树中有两种节点：2-节点与 3-节点，2-节点存储一个元素，3-节点存储两个元素。而红黑树则是一种“二叉树形式的 2-3 树”，它使用单个黑色的节点来表示 2-节点，使用 “红-黑” 这两个节点表示一个三节点：

这样一来，红黑树中所有的红色节点必然为左孩子节点，所以我们也将这种红黑树称为“左倾红黑树”（Left-Leaning Red-Black Tree）。

譬如这样的一棵 2-3 树：

转换为红黑树之后就是这个样子：

这也就是为什么我们会说红黑树与 2-3 树是等价的，对于任意的一棵 2-3 树都可以通过这种方式转换为一棵红黑树。

红黑树的实现

红黑树的基本性质

红黑树具有以下五条基本性质：

1. 每个节点或者为红色，或者为黑色。

这一点没什么可说的，毕竟叫做红黑树嘛，节点非红即黑。

2. 根节点的颜色一定是黑色。

我们可以类比考虑一下 2-3 树，2-3 树的节点不是 2-节点就是 3-节点，而无论是哪一种节点作为红黑树的根节点，都会使得根节点的颜色必然是黑色的。

3. 每一个叶子节点（最后的空节点）一定是黑色的。

如果红黑树为空，那么根节点也为空，这一点和第二点可以相互对应起来，因为根节点的颜色必然是黑色的。

4. 如果一个节点是红色的，那么它的孩子节点都是黑色的。

这一点大家同样可以类比下 2-3 树，红黑树中红色节点的左右节点不是 2-节点就是 3-节点，无论是哪一种节点，与红色节点相连的必然都是黑色节点。

5. 从任意一个节点到叶子节点，经过的黑色节点的数量一样多。

上面这棵 2-3 树转换为红黑树之后，是这样的：

从这张图里，我们可以清晰地看出，从任意一个节点到叶子节点，经过黑色节点的数量是一样多的。

这也就是我们所说的——红黑树是一棵保持“黑平衡”的二叉树（黑色节点是绝对平衡的），而严格意义上来讲红黑树并不是一棵平衡二叉树，但是因为红黑树具有黑平衡的特性，所以可以认为红黑树保持的是一种近似的平衡。

从这里我们也可以分析出向红黑树添加，查找，删除元素的时间复杂度。在最差的情况下，从根节点到叶子节点的路径上，红色节点与黑色节点交替出现，其复杂度为 #card=math&code=O%282logN%29&id=T935O)，忽略掉常数项系数，我们可以得到红黑树的增删改查的时间复杂度为 #card=math&code=O%28logN%29&id=amyxF)。

向红黑树中添加元素的代码实现

接下来我们来看一下如何向红黑树中添加元素。

红黑树中节点的定义与实现并不难。因为红黑树本身是一棵二分搜索树，所以节点可以存储元素值，并且内部有指向左，右孩子的指针，这些和二分搜索树中节点的实现是一样的。不过，红黑树的节点有颜色之分，且颜色非红即黑，我们就额外使用一个 boolean 变量表示节点的颜色：

public class Node<E> {
    public E e;
    public Node left;
    public Node right;
    public boolean color;
    public Node(E e) {
        this.e = e;
        left = null;
        right = null;
        color = true; // true 表示红色，false 表示黑色
    }
}

可以看到，我们设定初始化一个节点的颜色为红色。其实不难理解，在介绍 2-3 树时我们就提到了，向 2-3 树中添加节点的原则是新的节点永远不会插入到一个空的位置上。而我们在添加节点时，首先要将待添加的节点与其他节点进行融合，如果初始化节点的颜色为红色，那么就表示新添加的节点与其他节点进行融合这一步骤。

在捋清向红黑树添加一个节点的逻辑之前，我们首先回顾一下向二分搜索树中插入一个节点的逻辑：

如果当前二分搜索树的根节点为空，那么新插入的节点就会成为根节点。

如果当前二分搜索树的根节点不为空，就让根作为当前比较的节点：新插入的节点与当前节点进行比较；如果值比当前节点小就要“向左走”，如果值比当前节点大就要“向右走”，然后让下一层的节点继续作为当前比较的节点，直至走到应该插入的位置。

下图为在向当前的二分搜索树中添加节点“28”的流程：

Java 代码：

/**
 * @param e 向二分搜索树中添加新的元素
 */
public void add(E e) {
    root = add(e, root);
}
/**
 * @param e    向二分搜索树中新插入的节点
 * @param node 当前比较的节点
 * @return 返回二分搜索树的根节点
 */
private Node add(E e, Node node) {
    if (node == null) {
        size++;
        return new Node(e);
    }
    if (e.compareTo((E) node.e) < 0) {
        node.left = add(e, node.left);
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = add(e, node.right);
    }
    return node;
}

我们要满足红黑树的根节点始终为黑色，所以每次插入完一个节点，我们都手动将根节点置为黑色：

public void add(E e) {
    root = add(e, root);
    root.color = BLACK; // false
}

基于向二分搜索树中插入一个节点的逻辑，我们向红黑树中新插入一个节点有以下几种情况：

• 当前插入的节点与 2-节点进行融合
• 当前插入的节点与 3-节点进行融合

如果我们插入到一个 2-节点上，则具有以下两种情况：

第一种情况为，插入的节点比当前的 2-节点的元素值小。

如果是这种情况，我们直接将新的节点与 2-节点融合为一个 3-节点即可：

第二种情况为，插入的节点比当前的 2-节点的元素值大。

将元素 “42” 插入到 “37” 的右孩子的位置上：

此时，当前并不满足左倾红黑树的定义，我们需要以节点 ”37“ 进行一次 “左旋转” 操作（左旋转为逆时针，右旋转为顺时针），并将颜色重置：

为了不失一般性，我在节点 “37” 与节点 “42” 的孩子节点上分别添加了对应的子树，通过上图中伪代码的逻辑，我们看到“左旋转”后的树既保持了红黑树的特性，也保持了二分搜索树的特性。

左旋转操作的 Java 代码如下：

/**
 * 左旋转:
 *
 *        node                      x
 *       /   \                    /  \
 *     T1     x    =========>   node T3
 *          /  \               /   \
 *         T2  T3             T1   T2
 *
 */
private Node leftRotate(Node node){
    Node x = node.right;
    // 左旋转
    node.right = x.left;
    x.left = node;
    x.color = node.color;
    node.color = RED;
    return x;
}

在讨论了新插入的节点与 2-节点进行融合的所有情况后，我们来看一下新插入的节点与 3-节点进行融合的情况。

如果我们插入到一个 3-节点上，则具有以下几种情况：

第一种情况为，新的节点比 3-节点上的黑色节点的值还要大：

插入节点 “66” 后：

这一步操作相当于我们新插入的节点与 3-节点融合成为了一个 4-节点，对应到 2-3 树上，我们的操作是这样的：

接下来，我们需要将当前的 4-节点变成 3 个 2-节点，并让 “42” 继续向上融合：

所以，对应地，在红黑树中，我们应该将节点 “37” 与 “66” 变为黑色的 2-节点，将节点 “42” 置为继续与上一个节点融合的红色节点：

这一步骤的操作叫做 flipColors，顾名思义就是将这三个节点的颜色全部进行翻转，其代码对应如下：

// flipColors
private void flipColors(Node node){
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}

第二种情况为，新的节点比 3-节点上的红色节点的值还要小：

节点 “12” 插入后：

此时，我们需要对节点 “42” 进行一次右旋转：

再进行一次 flipColors：

右旋转的 Java 代码如下：

/**
 * 右旋转:
 *
 *        node                       x
 *       /   \                     /  \
 *     x      T2    ===========>  y   node
 *   /  \                            /   \
 *  y   T1                          T1   T2
 *
 */
private Node rightRotate(Node node) {
    Node x = node.left;
    // 右旋转
    node.left = x.right;
    x.right = node;
    x.color = node.color;
    node.color = RED;
    return x;
}

第三种情况为，新的节点比 3-节点上的红色节点的值要大，但是比黑色节点的值要小：

节点 “40” 插入后：

此时，我们首先对节点 “37” 进行一次左旋转，然后对 “42” 节点进行一次右旋转，最后再执行一次 flipColors 操作即可：

总的来看，向红黑树中添加元素的操作有如下的逻辑：

向红黑树中添加节点的完整 Java 代码如下：

public class RBTree<E extends Comparable<E>> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
    private int size;
    public RBTree() {
        root = null;
        size = 0;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * 判断节点 node 的颜色
     *
     * @param node
     * @return
     */
    public boolean isRed(Node node) {
        if (node == null)
            return false;
        return node.color;
    }
    /**
     * @return 返回红黑树的根节点
     */
    public Node getRoot() {
        return root;
    }
    /**
     * 左旋转:
     *
     *        node                      x
     *       /   \                    /  \
     *     T1     x    ===========> node T3
     *          /  \               /   \
     *         T2  T3             T1   T2
     *
     */
    private Node leftRotate(Node node){
        Node x = node.right;
        // 左旋转
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }
    /**
     * 右旋转:
     *
     *        node                       x
     *       /   \                     /  \
     *     x      T2    ===========>  y   node
     *   /  \                            /   \
     *  y   T1                          T1   T2
     *
     */
    private Node rightRotate(Node node) {
        Node x = node.left;
        // 右旋转
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }
    // 颜色翻转
    private void flipColors(Node node){
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
    /**
     * @param e 向红黑树中添加新的元素
     */
    public void add(E e) {
        root = add(e, root);
        root.color = BLACK;
    }
    /**
     * @param e    向红黑树中新插入的节点
     * @param node 当前比较的节点
     * @return 返回红黑树的根节点
     */
    private Node add(E e, Node node) {
        if (node == null) {
            size++;
            return new Node(e); // 默认插入的是红色节点
        }
        if (e.compareTo((E) node.e) < 0) {
            node.left = add(e, node.left);
        } else if (e.compareTo((E) node.e) > 0) {
            node.right = add(e, node.right);
        }
        if(isRed(node.right) && !isRed(node.left))
            node = leftRotate(node);
        if(isRed(node.left) && isRed(node.left.left))
            rightRotate(node);
        if(isRed(node.left) && isRed(node.right))
            flipColors(node);
        return node;
    }
}

那么至此，向红黑树中插入一个节点的操作就已经介绍完毕了。

以上内容就是我对红黑树的学习总结。关于向红黑树中删除节点的操作，在本篇文章中将不会涉及。

总结

今天我主要向大家分享了红黑树这种数据结构。

我们在介绍红黑树之前首先介绍了 2-3 树。如果理解了 2-3 树，那么理解红黑树其实并不难。

然后我们介绍了红黑树的五大基本特性：

1. 每个节点或者为红色，或者为黑色
2. 根节点的颜色一定是黑色
3. 每一个叶子节点（最后的空节点）一定是黑色的
4. 如果一个节点是红色的，那么它的孩子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点的数量一样多

并且从 2-3 树的原理上对红黑树这 5 条基本特性进行了分析。

最后，我们介绍了如何向红黑树中添加一个节点及它的代码实现。

好啦，至此为止，这篇文章就到这里了～欢迎大家关注我的公众号，在这里希望你可以收获更多的知识，我们下一期再见！