【数据结构之红黑树】深入原理与实现

从这篇文章开始我们来介绍红黑树这种数据结构，由于红黑树有二分搜索树和 AVL 树的性质，对于红黑树的操作同样依赖于这些性质。所以，如果理解了二分搜索树和 AVL 树之后再来理解红黑树其实相对来讲还是比较简单的。

红黑树是由 Robert Sedgewick 发明的，你如果不知道 Robert 是谁，网上很多文章都推荐一本书叫《算法 4》，这本书就是 Robert 写的。如果你不知道《算法 4》这本书，那你一定知道 Donald Knuth（中文名叫唐纳德），如果你连唐纳德也不知道那就应该去补补课了。可以说，如果没有唐纳德我们就没有衡量数据结构算法性能的方法，相应的我们也就没有提升算法性能的依据了，这就相当于是现实世界没有了尺子和秤，对于计算机科学的重要性不言而喻。他写过一套书叫《The Art of Computer Programming》 中文叫《计算机编程的艺术》。没错，微软在最鼎盛时期，比尔盖茨说读了这本书，并且读懂了，你可以把简历直接发给比尔盖茨。

我第一次去认真学习红黑树是看《算法导论》但当时备受打击，我给你看一下算法导论对红黑树的说明你就知道了。 一棵红黑树是满足下面红黑性质的二叉搜索树 1. 每个节点或是红色的，或是黑色的 2. 根节点是黑色的 3. 每个叶结点（NIL）是黑色的 4. 如果一个节点是红色的，则它的两个子节点都是黑色的 5. 对每个节点，从该节点到其所有子节点的简点路径上，均包含相同数量的黑色节点 如果第一次看到这 5 条性质，相信大部分人和我一样是有点蒙的，个人觉得对于红黑树的讲解比较好的还是《算法 4》这本书。可能跟作者是红黑树的发明者有关系吧。

这篇文章我们最终就是要把红黑树的这几条性质搞明白。但如果直接上来就讲红黑树还是有些吃力。所以，我们从另一种树结构，2-3 树作为切入点。

什么是 2-3 树

2-3 树的特点是同一个节点可以保存一个元素，也可以保存两个元素，如下图：

​对于一颗 2-3 树，节点可以有 1 个元素或者 2 个元素，如果节点只有 1 个元素，其最多只有两个子节点，左子节点比当前节点小，右子节点比当前节点大。如果一个节点有两个元素，左子节点比小的那个元素小，右子节点比大的那个元素大，中间的子节点介于两个元素之间。最后，对一颗 2-3 树一定是一颗绝对平衡树，也就是平衡因子为 0，回忆一下我们讲 AVL 树的时候对平衡因子的说明，我们说对于任一节点，其平衡因子等于左子树和右子树的层高差。

C/C++Linux服务器开发高级架构师/C++后台开发架构师​免费学习地址

【文章福利】另外还整理一些 C++后台开发架构师 相关学习资料，面试题，教学视频，以及学习路线图，免费分享有需要的可以自行添加：Q群：720209036 点击加入~ 群文件共享

​

2-3 树插入节点

2-3 树节点的插入，主要还是在于维护树的绝对平衡性质，同时又不破坏 2-3 树的性质，下面我们通过画图的方式推演一遍 2-3 树插入的过程。

​在一开始，2-3 树只有一个节点 42，我们插入一个节点 37，最终结果 37 和 42 融合成为了一个三节点。\

​插入一个节点 12， 将 12，37，42 融合成一个 4 节点，但 4 节点明显不符合 2-3 树的性质。所以，我们将 37 抽出来融合成一个 2 节点，完成节点 12 的插入。

​插入节点 18， 将 12 和 18 融合成一个 3 节点，完成节点 18 的插入操作。

​插入节点 6，先将 6，12，18 临时融合成一个 4 节点。同样的，此时已经不符合 2-3 树的性质了，我们将 12 向上融合成一个 2 节点，但此时破坏了树的绝对平衡性质。所以将 12 继续向上和 37 融合成一个 3 节点，完成节点 6 的插入操作。

​插入节点 11，此时只需将 11 和 6 进行融合形成一个 3 节点，完成节点 11 的插入。

​最后我们插入一个节点 5， 先将 5，6，11 融合成一个 4 节点，此时破坏了 2-3 树的性质，将节点 6 继续向上和 12，37 融合成一个 4 节点，此时还是破坏了 2-3 树的性质，将节点 12 向上融合成一个 2 节点，完成节点 5 的插入操作。

2-3 树和红黑树的关系

我们上面费了这么大力气讲了 2-3 树，那么 2-3 树和红黑树之间到底有什么关系呢？

我们先回顾一下前面提到的红黑树 5 条性质里的第一条：每个节点或者是红色，或者是黑色。那么对应到 2-3 树的 2，3 节点是什么样子的呢？我们来看一张图，如下：

​2-3 树里的 2 节点，我们可以对应红黑树里的黑色节点，我们用黑色表示，这里面有几层意思。首先，我们引申出前面提到了的红黑树的 5 条性质里的第二条，根节点是黑色的，那么对于节点 a，是一颗只有一个节点的红黑树，那么它自然是黑色的。其次，红黑树的每个节点要么是黑色，要么是红色，对应红黑树 5 条性质里的第一条。

然后我们看 3 节点，对于一个三节点，就是包含了两个元素的节点，对应红黑树我们可以把左边的 b 抽出来当作 c 节点的一个左子节点。那么，我们如何表示 b 和 c 之间的关系呢？这里我们将 b 节点标记成了红色，表示 b 和 c 之间对应 2-3 树里的 3 节点。

好了，对于 2-3 树和红黑树之间的关系我们就讲完了，下面我们来看一个 2-3 树转成红黑树的例子，如下图：

​左边是一颗 2-3 树，右边第一颗树我们以 2-3 树的样子排列成的一颗红黑树，然后将改造后的红黑树拉伸之后大家可以看到此时这就是一颗树二叉树，只不过此的二叉树满足红黑树的性质，你可以对照图思考一下。如果这张图看懂了，基本上就对红黑树有了概念。

对照上面的图，我们来看一下红黑树剩下的 3 三性质：

第 3 条，每一个叶子节点（最后空节点）是黑色的，这是什么意思呢？对于上面的这颗树，我们没有画出来的，其实都有一个对应为 NULL 的子节点，你可以理解为左子树或者右子树指向的是一个空指针，这些节点的颜色是黑色的。

第 4 条，如果一个节点是红色的，那么他的孩子节点都是黑色的，如果理解了 2-3 树的话这个也好理解，我们可以简单理解红色和黑色融合为一个 3 节点，如果红色节点相邻节点出现了红色节点，就说明可以融合成一个大于 3 节点的节点。所以，红色节点的子节点一定都是黑色。

第 5 条，从任意一个节点到叶子节点，经过的黑色节点是一样的，这个怎么理解呢？我们先看 2-3 树，左、右子树的层高一定是一样的，因为 2-3 树是一颗绝对平衡的二叉树，那么对于应到红黑树，我们在上面说我们可以简单理解红色节点和黑色节点融合成一个 3 节点，由此，我们可以推导出红黑树从凭单节点到叶子节点所经过的黑色节点一定是一样多的。对此，我们回忆一下 AVL 树，我们说保持 AVL 树的平衡其实是维护树中任一节点的平衡因子小于等于 1。那么，对于红黑树而言，根据其性质在最坏的情况下，隔层会出现一个红色节点，那么极端情况下，左右层高差可能相差 2 倍，这也是红黑树和 AVL 树最大的区别之一，我们知道，树的层越高，查询的时间复杂度也会相应变高。所以，单纯的从随机读的性能来看，似乎红黑树还不如 AVL 树。那为什么说在实际工程中我们更多的使用的是红黑树而不是 AVL 树呢？这主要是因为红黑树的插入性能会比 AVL 树要好，从统计意义上来讲我们认为红黑树的性能要比 AVL 树更好，这里的统计意义涉及到一些数学知识，三两句话讲不明白，如果有兴趣可以自己查一些资料。

好了，通过将 2-3 树和红黑色进行对应，我们将红黑树的 5 条性质都讲明白了，下面我们要解决的问题是如何向红黑树中插入节点。

插入节点

我们假设，一开始创建出来的节点是红色，当插入完成再去调整颜色，如下图：

​上面我们创建了一红黑树，第一个节点为 42，一开始是红色，因为整颗树只有一个节点，42 就是整颗树的根节点，所以，将节点 42 调整为黑色。紧接着，插入节点 37，同样的，一开始节点 37 也是红色，由于 37 比 42 小所以我们插入到节点 42 的左子树。此时，整颗树已经是一颗合法的红黑树了，不用做其它操作。

左旋转

上面我们讲了一种情况，就是插入的节点在左侧，并且父亲节点是黑色，我们将节点直接插入到父亲节点的左侧就完成了。下面我们看另外一种情况，如下图：

​我们看到第一个节点是 37，然后我们插入 42，这时，42 比 37 要大，按照二分搜索树的性质，我们要将 42 放在 37 的右子树。但是，回忆我们前面讲到的 2-3 树和红黑树的对应关系，小的节点我们是放在左边的，那么，很明显，此时这颗红黑树已经不是一颗合法的红黑树了，这就是我们要讲的左旋转。

我们将这颗红黑换一种表现方式，如下图：

​节点 37 是我们要待插入元素的父亲节点，我们用 node 表示，42 是待插入节点我们用 x 表示，37 和 42 的子节点我们分别用 T1、T2、T3 表示。然后我们将 node 节点做一次左旋转，如下图：

​首先，我们将 node 的右子节点指向 x 的左子节点也就是 T3，然后我们将 x 的左子节点指向 node 节点，完成左旋转。此时，虽然结构正确了，但还没有完，我们需要继续调整节点的颜色，如下图：

​我们将 x 的颜色染成和 node 节点一样，然后将 node 节点的颜色染成红色，这里有一个小陷阱，就是如果 node 节点的颜色本身就是红色，那调整过后不就破坏了红黑树的性质吗？其实，这里只是维护红黑树过程中的一个子步骤，调整完之后我们还需要继续进入上一层进行同样的操作，在上一层一定会帮我们调整正确，这里可能需要结合递归的思想仔细思考一下。

下面，我们来看一下左旋转的核心代码：

public Node leftRotate(Node node) {        // 先将x记下来        Node x = node.right;            // 旋转操作        node.right = x.left;        x.left = node;​        // 调整颜色        x.color = node.color;        node.color = RED;​        // 最后将x返回        return x;}

好了，到此为止我们左旋转就完成了。

颜色翻转

假如我们要插入的父亲节点已经有了一个红色的左子节点，此时我们要插入到其右边，我们应该怎么处理，下面我们通过一张图看一下这个过程，如图：

​在原有的红黑树，里面有两个节点 37 和 42，然后我们插入一个新的节点 66，此时，按照二分搜索树的性质我们应该插入到节点 42 的右子树，同样的，一开始插入的节点 66 是红色的，那么对应到 2-3 树就相当于是融合了一个临时的 4 节点，但显然，此时是不符合 2-3 树的性质的，我们需要将 42 继续向上融合成一个 2 节点，那么对应到红黑树，我们就需要将节点 42 的颜色染成红色，将 37、66 节点的颜色染成黑色，这样我们就完成了节点的插入，如果对这个还比较疑惑，可以回过头去看一下 2-3 树插入元素的过程。

下面我们看一下颜色翻转的代码：

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

颜色翻转代码还是比较简单的，可以对照图仔细再对一下。

右旋转

我们前面说红黑树的红色节点的最近的子节点一定是黑色，那么假如我们插入的节点的父亲节点是一个红色节点，我们应该怎么处处理呢？同样的，我们先通过一张图还看一下这个过程，如图：

​我们看到节点 10 比 37 要小，此时节点 37 也是一个红色节点。其实也很简单，我们只需要对节点 42 做一次右旋转，如下图：

​我们用 node 表示节点 42，用 x 表示 37，然后将 node 的左子节点指向 T1，接下来我们再将 x 的右子节点指向 node 就完成了右旋转，和前面说的左旋转是一个对称的操作，如图：

​和左旋转一样，我们也需要调整颜色，如下图：

​可以看到，相对于左旋转，我们多了一步颜色翻转，你可以对照上面我们讲的颜色翻转那一节来看。

我们同样看一下右旋转的核心代码：

publicNode rightRotate(Node node) {        // 先记下x        Node x = node.left;​        // 旋转操作        node.left = x.right;        x.right = node;​        // 调整颜色        x.color = node.color;        node.color = RED;            return x;}

可以看到，右旋转和左旋转非常像，其实右旋转就是左旋转的对称操作。好了，到此我们的右旋转也就完成了。

但其实还有一种情况，就是插入的节点在黑色节点的左子节点的右边，如果黑色节点的左子节点是红色，如下图:

对于这种情况，我们可以先对节点 37 做一次左旋转，得到一个和我们需要使用右旋转的结构，如图：

然后我们就可以进行右旋转的过程了，如下图：

​好了，到这里红黑树插入节点的所有情况我们都讲完了，下面我们来总结一下红黑树插入节点的整个过程，如下图：

​我们可以通过判断插入点的颜色，来决定是直接插入，还是左旋转又或者是右旋转，再或者是否要进行颜色反转，这几个过程其实都有可能，过程之间不是互斥的条件，等下看代码的时候就明白了。

下面我们将关键代码再理一遍。首先，我们定义了一个 Node 的内部类来表示红黑树的一个节点，代码如下：

publicstatic final boolean RED = true;public static final boolean BLACK = false;​private class Node {        private K key;        private V value;        private Node left,right;        private boolean color;​        public Node(K key, V value) {                this.key = key;                this.value = value;                this.left = null;                this.right = null;                this.color = RED;        }}

然后我们再看一下添加节点的核心逻辑，代码如下：

private Node add(Node node, K key, V value) {        if (node == null) {                size++;                return new Node(key, value);        }        // 节点插入的主流程和二分搜索树是一样的        if (key.compareTo(node.key) < 0)                 node.left = add(node.left, key, value);        else if (key.compareTo(node.key) > 0)                 node.right = add(node.right, key, value);        else                 node.value = value;            // 如果节点的右子节点是红色，右子节点是黑色，进行左旋转        // 这里可对照我们左旋转那一节的图来看        if (isRed(node.right) && !isRed(node.left))                 node = leftRotate(node);            // 如果大子节点和左子节点的左子节点都是红色，进行右旋转            if (isRed(node.left) && isRed(node.left.left))                 node = rightRotate(node);            // 如果左、右子节点都是红色，需要进行一次颜色的翻转            if (isRed(node.left) && isRed(node.right))                flipColor(node);​        return node;}

前面我们说左旋转、右旋转、颜色翻转这几个步骤不是互斥的，通过上面的代码应该就能够有比较直观的理解了，我们并没有使用 else if 这类逻辑。

好了，红黑树的插入就讲完了。其实，总结下来，红黑树的插入就是左旋转、右旋转、颜色翻转这简单几步，但如果你不理解这背后的原理，不理解二分搜索树和 AVL 树的性质理解起来还是有些困难的。

对红黑树的介绍我们就只讲到这里了，红黑树的节点删除，相对是比较复杂的，要讲清楚其实是不容易的，我也不想罗列一堆规则在这里，没有太多意义，在平时的开发中，真正要从头到尾写一颗红黑这种场景是极少的，除非你是做一些特别底层的开发。

其实我们这里介绍的红黑树是一颗左倾的红黑树，如果你有印象我们在前面是假设在 2-3 树的 3 节点上，左边的元素是对应红黑树里的那个红色节点，而且对此我们是做了一些特殊处理的。红黑树的实现不止这一种方式，这一点需要你知道。

总结一下，我们回顾一下二分搜索树和 AVL 树，二分搜索树的性质是对于任意节点的左子节点一定比右子节点要小，但如果我们插入的数据是有序的时候，二分搜索树会退化成一个链表，相应的随机读的时间复杂度也退化成了 O(n)。所以，我们需要去维护树的平衡性来阻止其退化成链表，这时我们介绍了 AVL 树，我们说 AVL 树对于任意节点的左子树和右子树的层高差不大于 1，为了维护树的平衡，我们介绍了树的左右旋转。但是，AVL 树维护平衡的代价是比较大的。所以，我们又介绍了红黑树这种数据结构，这是因为红黑树插入的效率相对 AVL 树是比较高的，在统计意义上来讲红黑树在插入和查找综合上效率是比较高的，这也是为什么红黑树为什么广泛应用在计算机各个方面。

参考资料

推荐一个零声教育 C/C++后台开发的免费公开课程，个人觉得老师讲得不错，分享给大家：C/C++后台开发高级架构师，内容包括Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

原文链接：【数据结构之红黑树】深入原理与实现 - 掘金