【从二叉树到红黑树】清晰理解红黑树的演变---红黑的含义

网上关于红黑树的博文很多，但是多是上来即讲定义，未说其所以然，难以理解且无所营养，甚者示例图有误且概念模糊的比比即是；

由于最近在学习相关知识找到一篇较为透彻且深入剖析的博文特此转载修订

注：原文示例图中有所错误本文中已重新修正，并增加了红黑树相关部分更多内容

前言

红黑树，对不少人来说是个比较头疼的名字，在网上搜资料也很少有讲清楚其演变来源的，多数一上来就给你来五条定义，红啊黑啊与根节点距离相等之类的，然后就开始进行旋转、插入、删除这些操作。一通操作下来，连红色和黑色怎么来的，是什么含义，有什么作用都云里雾里的，能搞清楚就怪了。

本文介绍红黑树，暂时不涉及任何代码，只是帮助你理解红黑树的演变来源，树结构中红黑色具体含义，保证你理解了过后，再去看什么旋转插入的东西，要清晰得多。换句话说，理解本文要描述的内容是从代码级理解红黑树的基础。

开始之前，我还是恳请你保持耐心，一步一步仔细看完，浮躁的话真的做不好任何事情。

正文

红黑树的起源，自然是二叉查找树了，这种树结构从根节点开始，左子节点小于它，右子节点大于它。每个节点都符合这个特性，所以易于查找，是一种很好的数据结构。但是它有一个问题，就是容易偏向某一侧，这样就像一个链表结构了，失去了树结构的优点，查找时间会变坏。

所以我们都希望树结构都是矮矮胖胖的，像这样：

而不是像这样：

在这种需求下，平衡树的概念就应运而生了。

红黑树就是一种平衡树，它可以保证二叉树基本符合矮矮胖胖的结构，但是理解红黑树之前，必须先了解另一种树，叫2-3树，红黑树背后的逻辑就是它。

好吧来看2-3树吧。

2-3树是二叉查找树的变种，树中的2和3代表两种节点，以下表示为2-节点和3-节点。

2-节点即普通节点：包含一个元素，两条子链接。

3-节点则是扩充版，包含2个元素和三条链接：两个元素A、B，左边的链接指向小于A的节点，中间的链接指向介于A、B值之间的节点，右边的链接指向大于B的节点。

2-节点： 3-节点：

在这两种节点的配合下，2-3树可以保证在插入值过程中，任意叶子节点到根节点的距离都是相同的。完全实现了矮胖矮胖的目标。怎么配合的呢，下面来看2-3树的构造过程。

所谓构造，就是从零开始一个节点一个节点的插入。

在二叉查找树中，插入过程从根节点开始比较，小于节点值往右继续与左子节点比，大于则继续与右子节点比，直到某节点左或右子节点为空，把值插入进去。这样无法避免偏向问题。在2-3树中，插入的过程是这样的。

如果将值插入一个2-节点，则将2-节点扩充为一个3-节点。

如果将值插入一个3-节点，分为以下几种情况。

(1).3-节点没有父节点，即整棵树就只有它一个三节点。此时，将3-节点扩充为一个4-节点，即包含三个元素的节点，然后将其分解，变成一棵二叉树。

此时二叉树依然保持平衡。

(2).3-节点有一个2-节点的父节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去。

(3).3-节点有一个3-节点的父节点，此时操作是：3-节点扩充为4-节点，然后分解4-节点，新树父节点向上融合，上面的3-节点继续扩充，融合，分解，新树继续向上融合，直到父节点为2-节点为止，如果向上到根节点都是3-节点，将根节点扩充为4-节点，然后分解为新树，至此，整个树增加一层，仍然保持平衡。

第三种情况稍微复杂点，为了便于直观理解，现在我们从零开始构建2-3树，囊括上面所有的情况，看完所以步骤后，你也可以自己画一画。

我们将{7,8,9,10,11,12}中的数值依次插入2-3树，画出它的过程：

所以，2-3树的设计完全可以保证二叉树保持矮矮胖胖的状态，保持其性能良好。但是，将这种直白的表述写成代码实现起来并不方便，因为要处理的情况太多。这样需要维护两种不同类型的节点，将链接和其他信息从一个节点复制到另一个节点，将节点从一种类型转换为另一种类型等等。

因此，红黑树出现了，红黑树的背后逻辑就是2-3树的逻辑，但是由于用红黑作为标记这个小技巧，最后实现的代码量并不大。(但是，要直接理解这些代码是如何工作的以及背后的道理，就比较困难了。所以你一定要理解它的演化过程，才能真正的理解红黑树)

我们来看看红黑树和2-3树的关联，首先，最台面上的问题，红和黑的含义。红黑树中，所有的节点都是标准的2-节点，为了体现出3-节点，这里将3-节点的两个元素用左斜红色的链接连接起来，即连接了两个2-节点来表示一个3-节点。这里红色节点标记就代表指向其的链接是红链接，黑色标记的节点就是普通的节点。所以才会有那样一条定义，叫“从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点”，因为红色节点是可以与其父节点合并为一个3-节点的，红黑树实现的其实是一个完美的黑色平衡，如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的。所以它并不是一个严格的平衡二叉树，但是它的综合性能已经很优秀了。

借一张别人的图来看：

红链接放平：

所以，红黑树的另一种定义是满足下列条件的二叉查找树： ⑴红链接均为左链接。 ⑵没有任何一个结点同时和两条红链接相连。(这样会出现4-节点) ⑶该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。

理解了这个过程以后，再去看红黑树的各种严格定义，以及其插入，删除还有旋转等操作，相信你脑子里的思路会清晰得多的。

红黑树

注：红黑数是平衡二叉树的一种，插入时遵循二叉树“左右”定律：

该父节点的左子节点：为小于父节点中且子树中最接近父节点值得数。

该父节点的右子节点：为大于父节点中且子树中最接近父节点值得数。

R-B Tree简介

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意： (01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。 (02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

红黑树示意图如下：

红黑树的应用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。 例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

红黑树的时间复杂度和相关证明

红黑树的时间复杂度为: O(lgn) 下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

定理：一棵含有n个节点的红黑树的高度至多为2log(n+1).

证明： "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题是 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。 我们只需要证明逆否命题，即可证明原命题为真；即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。

从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明： 第1点：根据红黑树的"特性(5) ，即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！ 第2点：根据红黑色的"特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的"可知，从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点，则可以得出结论"bh(x) >= h/2"。进而，我们只需证明 "高度为h的红黑树，它的包含的黑节点个数至少为 2bh(x)-1个"即可。

到这里，我们将需要证明的定理已经由 "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 转变成只需要证明 "高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。

下面通过"数学归纳法"开始论证高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。

(01) 当树的高度h=0时， 内节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。

(02) 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的！

下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2bh(x)-1”。

当树的高度为 h 时， 对于节点x(x为根节点)，其黑高度为bh(x)。 对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。 根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2bh(x)-1-1 个"；

所以，节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。 因此，原命题成立。

由(01)、(02)得出，"高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。 因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。补充知识：租用主机

按需购买：根据云主机内存大小，硬盘容量，服务器带宽、操作系统不同所售价格也不同 ①：腾讯云代金券2860礼包（希望对你有所帮助） ②：目前腾讯云3折秒杀活动，价格非常实惠。