17 红黑（R B）树：和平衡二叉树有什么不同？

你好，我是王健伟。

上次我和你分享了“平衡二叉树”这个话题，引出了“平衡性调整”的概念。主要目的是让这棵二叉树左右看起来比较“平衡”，不出现左子树很高、右子树很矮，或者左子树很矮、右子树很高的情形。这样，在进行节点的查找、插入、删除等操作时效率会比较高。

但这同时也带来了缺点——在插入和删除节点时，为了调整平衡，必须对树中的节点进行旋转，从而在一定程度上影响程序的执行效率。

平衡二叉树的一条重要性质是“任一节点的左子树和右子树的高度之差不超过1”。这里引入一个“非严格平衡二叉树”的概念。

非严格平衡二叉树指的是不完全符合前面平衡二叉树的定义，或者说并不是一种严格意义上的平衡二叉树。但这种二叉树最小高度仍旧在$log_{2}^{{n}$（n代表节点数）附近，或者说，查找操作的时间复杂度仍旧为O($log_{2}}$) 。所以，我们仍旧可以认为这种二叉树是一种平衡二叉树。这就引出了这节课要讲解的“红黑树”。

首先一起看一看红黑树的基本概念。

什么是红黑树？

红黑树（Red-Black Tree），简称R-B树，是一种高效的二叉查找树，由Rudolf Bayer在1972年发明的，当时被称为“对称/平衡二叉B树”，后来在1978年由Leo J. Guibas和Robert Sedgewick 修改为“红黑树”。

红黑树首先是一棵二叉查找树，也是一种典型的非严格平衡二叉树，或者你也可以理解成一种特殊/特化的AVL树，甚至在很多资料中，提到平衡二叉树指的就是红黑树。红黑树在插入和删除节点时，会通过特定的操作保持二叉查找树的相对平衡，从而获得比较高的查找效率。既然是相对平衡，所以任一节点的左子树和右子树的高度之差很可能会超过1。

观察图1。

红黑树的节点是有颜色的，颜色分两种——一种是红色，一种是黑色。红黑树有4个性质（特点），实现红黑树代码的时候一定要遵循它们，我们一起来看一下。

性质1：每个节点要么是黑色，要么是红色，而根节点必须是黑色的。向后面看，就可以知道，根节点是黑色，其子节点就很灵活——可以是黑色，也可以是红色。

性质2：每个叶子节点都是黑色的空节点（Nil），这一点和其他树不同。也就是说，叶子节点不存储数据。所以，往往绘制红黑树时，叶子节点会省略不绘制。如果看到一棵树的底端出现的节点是红色（1中的节点55和节点60），则这个节点肯定不是叶子节点，只是下面的叶子节点省略没有绘制而已。

性质3：任何相邻的节点，也就是用线条连接起来的节点，比如当前节点的父或子节点，不能同时为红色（红色节点不能相邻），如果换句话说，可以有下面几种说法，理解任何一种都可以。

红色节点是被黑色节点分隔开的。
红色节点的两个孩子节点或者父亲节点必须是黑色的。
从叶节点到根的所有路径上不可以有两个连续的红色节点。

性质4：红黑树左右子树的高度差很可能会超过1甚至超过更多。红黑树的平衡性指的是对于每个节点，从该节点到达其所能够到达的叶子节点的所有路径都包含相同数量的黑色节点。这个黑色节点数量叫做“黑高度”或者“黑高”，用于保证黑色节点的平衡性。

举个例子。

从节点65要访问到节点20左下叶子节点，需要经过65→40→20→Nil，这其中显然包括了65、20、Nil这三个黑色节点。
从节点65要访问到节点80的左下叶子节点，需要经过65→80→Nil，这三个节点显然都是黑色节点。
从节点65要访问到节点55的左下叶子节点（图中没有画出但仍旧是存在的），需要经过65→40→50→55→Nil，这其中显然包括了65、50、Nil这三个黑色节点。

显然，图2的节点组合情形在红黑树中都不应该存在，其中左侧的上下共2棵红黑树违背了红黑树的性质3，右侧的上下共4棵红黑树违背了红黑树的性质4。

这里我也把图2违背性质的地方列了出来。

编号为1的二叉树红色节点10和红色节点8相邻，违背（红黑树）性质3。
编号为2的二叉树红色节点10和红色节点12相邻，违背性质3。
编号为3的二叉树黑色节点10无左子节点却有黑色的右子节点，违背性质4。
编号为4的二叉树红色节点10无左子节点却有黑色的右子节点，违背性质4。
编号为5的二叉树黑色节点10有黑色的左子节点却无右子节点，违背性质4。
编号为6的二叉树红色节点10有黑色的左子节点却无右子节点，违背性质4。

总结一下就是，红黑树是：

黑色的根；
黑色的叶子；
红色节点不相邻，也就是红色节点的父亲和孩子都是黑色节点；
当前节点到其所有叶节点包含的黑色节点数量相同。

如果你正在思考为什么已经有AVL树了还需要引入红黑树，那么简单来说可以这样理解。

如果AVL树很大，那么在插入和删除操作时会进行大量的旋转操作以达到AVL树的平衡，尤其是删除节点时，可能要经过若干次的旋转操作，甚至可能需要从最底部的节点一直到根节点都进行平衡性调整。
但在红黑树中，当进行插入和删除操作时，维护红黑树的平衡性成本就比较低——多数情况下只需要旋转两次或者不需要旋转只需要对节点的颜色进行修改，也就是把红色修改为黑色。

所以，虽然AVL树比红黑树更加平衡，但针对插入和删除操作，红黑树可以保证平均情况时间复杂度更接近O($log_{2}^{n}$)。换句话说，如果从单纯搜索角度来讲，AVL树更快，但如果频繁进行插入和删除操作，因为红黑树需要更少的旋转，无疑效率会更高，而且红黑树的查找、插入、删除操作性能较稳定。

再进一步看一看红黑树左右子树的高度问题以及如何区分是不是一棵合法红黑树的问题，如下图3。

图3中第1个图是一棵红黑树，如果希望为节点20增加一个新的左孩子节点10，节点10必须是红色以保证红黑树的性质4（65→40→20→10→Nil包含3个黑色节点，到所有其他叶子节点也都包含3个黑色节点），参见图3第2个图，也是一棵红黑树。

如果再为节点10增加一个新的左孩子节点，那么这个新节点无论是红色还是黑色，得到的新树都不会再是一棵红黑树，因为如果增加的节点是红色，则不满足红黑树性质3，如果增加的节点是黑色，则不满足红黑树性质4。

这意味着，对于图3第2个图这棵红黑树，从根节点（65）到叶子节点10的高度为4，不可以比4再大，否则就不再是一棵红黑树。所以数字4在图3第2个图这棵红黑树中被称为从根节点到叶节点的最长路径（红黑节点间隔存在）。

而显然，从根节点65到叶子节点80的高度为2，数字2被称为从根节点到叶节点的最短路径（黑节点紧挨在一起）。

因此，不难得到一个结论：红黑树从根节点到叶子的最长路径不超过最短路径的两倍。在红黑树中因为红色节点不能相邻，所以，必须用黑色节点将红色节点隔开。

这也就意味着红黑树中最短路径（最小高度）是不会超过$log_{2}^{{n}$（二叉树性质五），那么加入红色节点后，最长路径也就不会超过2$log_{2}}$。所以红黑树高度只比AVL树高一倍而已，在执行效率上差不太多，而且往往因为上面提到的其他方面的优势，红黑树效率更高，性能更好。}$，这意味着红黑树的高度大概为2$log_{2}^{n

显然，图3中第3个图也是一棵红黑树。但是如果把这个图中的节点40去掉，那么就变成了一棵只有右子树的二叉查找树，这棵二叉查找树就不再是一棵红黑树了，因为不满足红黑树性质4，很多人看不出来把节点40去掉后为什么就不是一棵红黑树了，此时只需要在图中把黑色的Nil节点画出来，就很容易看出是不是一棵红黑树了，如图3第4个图，显然不满足红黑树性质4。

在具体针对红黑树进行编程时，有几点值得一提。

往往不需要考虑叶子节点，也就是那个黑色的空节点（Nil）不需要考虑。
红黑树的节点查找操作同二叉查找树的节点查找操作（SearchElem成员函数）完全一样，你可以参考前面已经实现的代码。

红黑树的基础实现代码

下面是红黑树的基础实现代码。

//红黑树中每个节点的定义
template <typename T>   //T代表数据元素的类型
struct RBNode
{
    T        data;          
    RBNode* leftChild,   //左子节点指针
          * rightChild,  //右子节点指针
          * parentNd;      //父节点指针，引入方便操作

    bool     isRed;      //是否是红色节点，true：是，false：不是（而是黑色节点）
};

//红黑树的定义
template <typename T>
class RBTree
{
public:
    RBTree()  //构造函数
    {
        root = nullptr;
    }
    ~RBTree() //析构函数
    {
        ReleaseNode(root);
    }   
private:
    void ReleaseNode(RBNode<T>* pnode)
    {
        if (pnode != nullptr)
        {               
            ReleaseNode(pnode->leftChild); 
            ReleaseNode(pnode->rightChild);
        }
        delete pnode;
    }

private:
    RBNode<T>* root; //树根指针
};

小结

这节课我带你学习了红黑树，这个用途最广并且面试中最常出现的一种二叉树。

红黑树的基础概念，长什么模样，我们就不再多说。在频繁进行插入和删除操作的场合，红黑树比平衡二叉树具有更高的效率。这也是已经存在了平衡二叉树，但还要引入红黑树的原因。

依据红黑树的几条性质，我们可以判断红黑树的合法性，具体来说有三点。

根节点必须是黑色。
任何相邻的节点不能同时为红色。
对于每个节点，从该节点到达其所能够到达的叶子节点的所有路径都包含相同数量的黑色节点。

这节课，我也给出了红黑树的基础实现代码。有了这些基础实现代码，就可以将研究的重点放在插入数据和删除数据上了。红黑树插入和删除数据所面临的主要问题是平衡性调整问题，这既是重点也是难点，需要好好学习。

下节课，我们就来看看红黑树插入操作后的平衡性调整以及它的实现代码。

课后思考

你以往是否使用过红黑树，用它做过哪方面的工作？你是否还知道更多的关于红黑树的应用场合，能否举一些例子？当然，也可以通过搜索引擎来寻找答案。

欢迎你在留言区分享自己的经验，如果觉得有所收获，也可以把课程分享给更多的朋友一起学习，我们下节课见！

精选留言（1）

HH🐷🐠 👍（1） 💬（0）
🌝java 工具类 HashMap 就用到了红黑树，防止树退化成链表。
2023-12-26