【C++】红黑树讲解及实现

前言：

        AVL树与红黑树相似，都是一种平衡二叉搜索树，但是AVL树的平衡要求太严格，如果要对AVL树做一些结构修改的操作性能会非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此，如果要对一个结构经常修改，AVL树就不太适合，这时就需要运用对平衡要求不太严格的红黑树。

---

一，红黑树的认识

        红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

        红黑树确保没有一条路径会比其他路径长出俩倍的原因是由红黑树的性质决定。

红黑树的性质

        1. 每个结点不是红色就是黑色。 

        2. 根节点是黑色的。

        3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的。即从上层到下层不存在连续的红节点。

        4. 对于每个结点，从该结点到其所有后代叶子结点的简单路径上（包含此节点），均包含相同数目的黑色结点，即每条路径均包含相同数量的黑色节点。

        5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。这里所到最终节点指的就是空节点。如上图中NIL空节点为黑色。

        红黑树就是满足以上的性质才确保没有一条路径会比其他路径长出两倍。至于原因我们可来设想一下极端情况。由于任意一个节点到其所有后代叶子结点的黑色节点相同，且红色节点不能连续出现，所以极端情况下，我们令一个节点的左边为最短路径——全部黑色，高度h，右边为最长路径——黑色节点之间每隔一个都有一个红色节点，高度最大为2*h。这样我们得出最大路径刚好是最小路径的两倍。由此看来，红黑树下任意节点的路径之差在 [h，2h] 区间。

        红黑树对比AVL树可得，红黑树对平衡的要求不是那么严格，比较宽松，虽说效率逊于AVL树，但是综合性能比AVL树高。而且AVL树的高度很接近 logN，红黑树高度很接近 2*logN，logN 的数值足够小，两者之间效率基本微乎其微，基本可忽略不计。

---

二，红黑树的插入操作

2-1，红黑树节点的定义

        红黑树的结点定义大致跟AVL树一样，唯一要不同的是红黑树中没有平衡因子，只包含颜色。

//节点的颜色——这里用枚举表示

enum Color
{
    RED,       //红色
    BLACK   //黑色
};

//红黑树节点的结构

template <class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _parent;   //双亲节点
    RBTreeNode<K, V>* _left;        //左孩子节点
    RBTreeNode<K, V>* _right;     //右孩子节点
    Color _color;                             //节点颜色
    pair<K, V> _kv;                         //节点数据

    RBTreeNode(const pair<K, V>& kv)   //为了后面插入方便，这里构造为红色节点
        : _parent(nullptr)
        , _left(nullptr)
        , _right(nullptr)
        , _color(RED)    
        , _kv(kv)
    {    }
};

2-2，红黑树的插入操作

        红黑树的插入跟AVL树一样，都是在二叉搜索树的基础上加上了平衡限制，因此可分为两步：1，按照二叉搜索树的规则进行插入。2，检测插入后的红黑树是否造到平衡破坏，若平衡被破坏，这里要进行旋转或变色（由于这里的平衡是根据颜色来控制的，插入后若平衡别破坏颜色管理一定失调，但插入后颜色失调不一定会导致平衡破坏，这里可想象一下当平衡满足AVL平衡时插入的场景）。

        红黑树由于要满足左右所有路径上的黑色节点相同，若插入黑色节点会引发上面一系列结构问题和不平衡现象，因此这里最好插入红色节点。

       首先我们先来考虑什么情况下插入新节点后不会发生旋转和变色。这里很显然，若我们在黑色节点后面插入新节点（红色节点）是不会影响颜色管理，至于是否影响平衡还要看极端情况。在极端情况下插入发生平衡失调，这绝对不会插入在黑色节点后面。因此若插入新节点在黑色节点后面我们可放任不管。

        若我们插入的新节点cur在红色节点后面，此时的红色结点必然无孩子且一定要进行变色（恢复红黑树颜色规则），还可能要进行旋转（恢复红黑树平衡规则），因为若此时红色结点存在一个孩子，那么这个孩子必然是黑色的，这样一来就违背了红黑树的左右路径黑色结点数量相同的性质。此情况下，因为cur的双亲结点是红色的，所以必然会存在黑色的爷爷结点，所以，这里的情况可分为三类谈论：1，存在cur的叔叔节点（双亲结点的兄弟结点）且为红。2，不存在cur的叔叔结点。3，存在cur的叔叔结点且为黑。其中情况二和情况三在代码实现中可分为一种情况，具体原因下面会说明。

情况一：（存在cur的叔叔节点u且为红）

        我们来看新插入结点cur的叔叔结点为红色时的情况。根据已有条件可知，cur的双亲结点parent（简写：p）为红色，那么cur的爷爷结点grandparent（简写：g）必为黑色，叔叔结点uncle（简写：u）为红色。如下图：

       我们先来观察a结构。这里先只看以p为根节点的子树，由于p为红色，且插入cur之前p的左边路径为1，所以a要么为空，要么只有一个黑色结点。当为黑色结点时，左右路径的黑色结点数量不相等，所以a只能为空。b和c同理，只看以g为根节点的子树结构，b和c不能为黑色，但b和c为红色，这里也不能为红色，所以只能为空。如下：

        这种情况下是否需进行旋转暂不明确，但显然违反了颜色规则——红色结点之间相连，需进行颜色变换。颜色变色这块需明白，当一个结点变色后是不会影响此节点的下层颜色规则，只会影响上面结构。因此，这里变色规则是p和u变黑色，g变红色，控制原本黑色结点的数量不变（保证上层结构）。如果g是根节点再将其变黑色，然后结束操作；如果g不是根节点，需要继续往上查看，因为这里虽说满足黑色结点数量的规则，但是g变成了红色，g的双亲结点可能为红色或黑色。当g的双亲结点为黑色时颜色变色后满足规则，可直接结束；当g的双亲结点为红色时，这里就要将重复操作，即将cur = g，继续排查，直到遇到p为黑色或cur为根节点为止。注意：这里往上排查过程中也可能遇到情况2（u结点不存在）或情况3（u结点存在且为黑色），这里先提前说一下，其实排查过程中不可能遇到情况2，至于原因和遇到情况3下面会详细说明。

        这里有两个问题。1，p结点和g结点是否存在，即是否为空。2，平衡是否被破坏，即是否需要进行旋转。

问题一：

        p结点可能为空，此时cur结点为根节点，对照上面cur为根节点直接处理情况，若在刚开始p为空，此时新插入结点cur为根节点，插入后直接返回即可。

        g结点这里一定不为空，因为当g结点为空时，p结点就是根节点，p结点一定为黑色。我们使用g结点的前提条件是p结点为红色，若p是黑色直接退出，根本就没有g结点这一环节。

问题二：

        这种条件下平衡一定不会被破坏。插入新节点后平衡被破坏的前提是插入前结构必为极端情况，而在极端情况下cur必有叔叔结点u且为黑或无叔叔结点u。因此，此种情况只需变色，无需旋转。从这可说明，发生旋转和变色的只有cur存在叔叔结点u且为黑色或无叔叔结点u。

        注意，在情况一下又可划分为四种情况，如下：

                1，p是g的左孩子，u是g的右孩子，新插入结点cur是p的左孩子。（如上图）

                2，p是g的左孩子，u是g的右孩子，新插入结点cur是p的右孩子。

                3，p是g的右孩子，u是g的左孩子，新插入结点cur是p的左孩子。

                4，p是g的右孩子，u是g的左孩子，新插入结点cur是p的右孩子。

        这里划分的四种情况都可看成一种情况，因为这里只需变色无需旋转，针对的目标是p、u、g三结点的颜色，至于谁是左孩子谁是右孩子根本不理会。      

情况二：（不存在cur的叔叔结点u）

        当不存在叔叔结点u时插入新节点cur时显然违反了平衡规则——左右最大高度与最小高度不满足二倍关系，至于怎么旋转我们从AVL树中可知需看cur、p的具体位置（前文中已有AVL树旋转的详细讲解以及原理，若这里不明白的请看前文AVL树讲解），然而这里存在四种小情景：        

        1，p是g的左孩子，新插入结点cur是p的左孩子。p一定没有右孩子，因为p为红色且插入前无左孩子。此种情景跟AVL树中插入在g的左子树的左侧相似，进行右单旋，旋转后还要变色。为了保证这里黑色结点数量不变（保证上层结构）且在此子树下的左右路径黑色结点数量相同（保证本层子树结构，即最底层结构），需将g变为红色，p变为黑色，如下图：

        2，p是g的左孩子，新插入结点cur是p的右孩子。p一定没有左孩子，因为p为红色且插入前无右孩子。此种情景跟AVL树中插入在g的左子树的右侧相似，进行左右旋，旋转后也要变色。这里的变色规则跟上面一样，即将g变为红色，cur变为黑色，如下图：

        3，p是g的右孩子，新插入结点cur是p的左孩子。与上同理，这里p一定无右孩子。此种情景跟AVL树中插入在g的右子树的左侧相似，进行右左旋，旋转后也要变色。这里的变色规则跟上面一样，即将g变为红色，cur变为黑色。

        4，p是g的右孩子，新插入结点cur是p的右孩子。与上同理，p一定无左孩子。此种情景跟AVL树中插入在g的右子树的右侧相似，进行左单旋，旋转后还要变色，需将g变为红色，p变为黑色。

        当出现此种情况时，cur绝不可能是往上排查中的情况，必定为新插入结点，因为在这种情况下，以g为根节点的子树左右路径之差根本不满足红黑树的性质，例如以上面情景四为例，当cur不是新插入的结点时，g的左边高度固定为1，右边高度大于3。

        这里当发生这种情况时，旋转变色后可直接退出，因为无论出现以上哪四种场景，旋转后都将恢复原本平衡，变色后在g位置的结点都为黑色，根本不影响上层结点情况或g为根节点情况。

情况三：（存在cur的叔叔结点且为黑）

         首先，我们先来观察cur为新插入结点时遇到此情况的时候。

        我们来分析以上情况，这里叔叔结点u为黑色，根据红黑树性质，这里以g为根节点的子树中a结构必须有一个黑色结点，但在插入前图中p没有左孩子，这里以p为根节点的子树中情景跟上面一样，a结构必须为空，与上形成矛盾，因此cur为新插入结点的情况根本不可能出现，也就是说cur的叔叔结点为黑色的情况下只能是cur不为新插入的结点，即情况一中往上排查中遇到的情况（遇到情况二一步操作后直接退回）。    

        从情况一中的问题二可知，发生旋转和变色的情况只有在cur必有叔叔结点u且为黑色或无叔叔结点u的条件下，其中无叔叔结点只能是在刚插入时的情况，而此情况只能在上层中遇到，但注意，当遇到此种情况时还不能说明平衡一定被破坏，即平衡可能被破坏也可能没有被破坏。为了方便起见，这里处理的方式是无论平衡是否被破坏都进行旋转处理，因为旋转调节后我们严格遵守红黑树的颜色管理，也就间接不会破坏平衡；而且旋转的本质是将高度大的一方减一，高度小的一方加一，此种情况又是在上层结构中遇到的，当平衡时旋转调节后一定不会破坏这里的平衡。当平衡被破坏时，路径最长的是2*h+1（新插入结点的一方），路径最短的是h，旋转之后路径最长的变为2*h，路径最短的变为h+1，满足条件。

        旋转之前我们来分析已确定的条件。首先，这里叔叔既然存在且为黑，那么必然存在g结点。其次，这里的cur结点是情况一中往上排查时上一次的g结点——原本是黑色的现在变成红色的，相当于又一次检验，因此cur是红色的，那么p结点也是红色的，如果p是黑色的，在情况一中就直接退出了，根本不会进行到下一轮，且就算叔叔结点u是黑色的，但若双亲结点p是黑色的根本不可能出现不平衡现象，即颜色失调现象。最后，由于p是红色的，那么g是黑色的。总的来说，当发生这种情况时，就已确定g结点和u结点是黑色的，p结点和cur结点是红色的。

        此种情况跟情况二相似，对应的也有四种不同位置的场景，由于需要进行旋转，所以这里都要进行讨论。

        1，cur是p的左孩子，p是g的左孩子，u是g的右孩子。

        这里我们要明白是左右中的哪里高度出现了问题，需在哪里进行旋转。上面说过，存在叔叔节点u且为黑时进行旋转必然是插入前已处于极端情况下，此处高度大的一方就是cur的一方，因此此场景的旋转类似于AVL树中插入在g的左子树的左侧，进行右单旋。旋转后这里违背了颜色分配规则，具体的变化规则必须要依据插入前的原结构。插入前a、b、c、d、e结构尚未可知，但除去a、b、c、d、e结构外，g结点位置的左边无黑色结点，右边有一个黑色结点，g位置上是黑色结点（防止上面的双亲结点），除了这里已知结点外，还要注意a、b、c、d、e结构中头节点的颜色（为了周全，这里最好全部都看成不为空时的情况），即a、b、c的头节点必定为黑，d、e未知，因此这里需注意d、e为红的情况——若为红色，它们的双亲必须是黑色；若为黑色，它们的双亲可随意。旋转后必须也要满足此条件和以上注意情况，否则颜色分配这里可能就会出问题，因此，这里颜色的变化是将p变为黑色，g变为红色，如下图。

        2，cur是p的右孩子，p是g的左孩子，u是g的右孩子。

        这里高度大的一方还是cur的一方，原因与上一样。此时场景如同AVL树中插入在g的左子树的右侧，旋转的方式是左右旋——先左旋后右旋。颜色变化更上面场景原理一样，除去a、b、c、d、e结构，g位置的右边有一个黑色结点，g位置的左边没有黑色结点，g位置上是一个黑色结点（为了防止g位置的双亲结点）。这里还是将a、b、c、d、e子树结构看成都不为空时的情况，其中a、b、c的根节点必是黑色的，d、e的根节点可能是红色的，因此，这里旋转后连接d、e的结点必须也是黑色的。具体的颜色变化是将cur变成黑色，g变成红色，如下图：

        3，cur是p的左孩子，p是g的右孩子，u是g的左孩子。

        这里cur高度超出范围，与上一样。此时的旋转跟AVL树中插入在g的右子树的左侧时进行的旋转一样——进行左右旋（先左单旋后右单旋）。旋转后颜色的变化逻辑思想与上相同，g位置上是黑色结点，g位置左边有一个黑色结点，g位置右边没有黑色结点，且d、e子树结构的根节点可能是红色的。变色后应满足以上规则且连接d、e子树结构的结点必须是黑色的。因此，这里的颜色变色规则是g变成红色，cur变成黑色，如下图：

        4，cur是p的右孩子，p是g的右孩子，u是g的左孩子。

        这里cur高度超出范围，与上一样。此时的旋转跟AVL树中插入在g的右子树的右侧时进行的旋转一样——进行左单旋。旋转后颜色的变化逻辑思想与上相同，g位置上是黑色结点，g位置左边有一个黑色结点，g位置右边没有黑色结点，且d、e子树结构的根节点可能是红色的。变色后应满足以上规则且连接d、e子树结构的结点必须是黑色的。因此，这里的颜色变色规则是g变成红色，p变成黑色，如下图：

        这里不难发现，处于这种情况下的无论哪种场景，叔叔结点u以及叔叔结点u下层的结构不做任何改变，至于p和cur下层的结构若不为空，根节点必为黑色，这里完全不影响上面结点的颜色。仔细思考可发现，这里发生的旋转和不同场景下颜色的改变跟情况二中无叔叔结点时一摸一样—，即g结点的位置是黑色的且满足颜色分配，旋转变色后可直接退出，可归为一类。

代码实现   

        总上所述，这里红黑树的插入操作逻辑大致是这样：当插入结点的双亲结点是黑色的不做任何处理；当插入结点的双亲结点是红色的，这时分两种情况来判断：1，存在叔叔结点且为红。2，存在叔叔结点且为黑或不存在叔叔结点。当存在叔叔结点且为红，这种情况只用于变色并向上做出排查，直到排查到根节点；当不存在叔叔结点或存在叔叔结点且为黑，直接进行旋转并变色后退出。由于情况一需要对叔叔结点进行变色，而情况二需要确定叔叔结点的位置以便确定哪种旋转，所以这里可再分两种小情况进行讨论——叔叔结点u是g的左孩子或叔叔结点u是g的右孩子。于情况一而言，这里只用变色，无需注意其它结点位置；于情况二而言，由于需要旋转，只确定p和u的位置还不够，还需确定cur的具体位置。代码如下：

bool Insert(const pair<K, V>& kv)
{
    //1，插入节点
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_color = BLACK;
        return true;
    }
    Node* cur = _root;
    Node* parent = _root->_parent;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }
    if (parent->_kv.first > kv.first)
    {
        parent->_left = new Node(kv);
        cur = parent->_left;
    }
    else
    {
        parent->_right = new Node(kv);
        cur = parent->_right;
    }
    cur->_parent = parent;

    //2，旋转或变色
    //只用处理插入结点cur的双亲结点是红色时的情况，要注意cur是根节点的情况
    while (parent && parent->_color == RED) 
    {
        //存在parent且parent是红色时，由于根节点是黑，所以一定存在它的双亲结点
        Node* grandparent = parent->_parent;
        //cur双亲结点parent在左，叔叔结点uncle在右
        if (parent == grandparent->_left)
        {
            Node* uncle = grandparent->_right;
            //情况一: 存在叔叔结点且为红
            //这种情况平衡不会被破坏，不用关心结点的具体位置，只需变色
            if (uncle && uncle->_color == RED)
            {
                //变色
                grandparent->_color = RED;
                parent->_color = uncle->_color = BLACK;
                //往上排查
                cur = grandparent;
                parent = cur->_parent;
            }
            //情况二: 存在叔叔结点且为黑或不存在叔叔结点
            else 
            {
                //情景一: p是g的左孩子，u是g的右孩子，cur是p的左孩子
                if (cur == parent->_left)
                {
                    //旋转
                    RotateR(grandparent);
                    //变色
                    grandparent->_color = RED;
                    parent->_color = BLACK;
                }
                //情景二: p是g的左孩子，u是g的右孩子，cur是p的右孩子
                else
                {
                    //旋转
                    RotateLR(grandparent);
                    //变色
                    grandparent->_color = RED;
                    cur->_color = BLACK;
                }
                break;//旋转变色后直接退出
            }
        }
        //cur双亲结点parent在右，叔叔结点uncle在左
        else
        {
            Node* uncle = grandparent->_left;
            //情况一: 存在叔叔结点且为红
            //情况以上一样，这里只需变色无需旋转
            //这里之所以不能单独列出来是因为叔叔结点不确定是否存在
            if (uncle && uncle->_color == RED)
            {
                //变色
                grandparent->_color = RED;
                parent->_color = uncle->_color = BLACK;
                //继续往上排查
                cur = grandparent;
                parent = cur->_parent;
            }
            //情况二: 存在叔叔结点且为黑或不存在叔叔结点
            else 
            {
                //情景三: p是g的右孩子，u是g的左孩子，cur是p的左孩子
                if (cur == parent->_left)
                {
                    //旋转
                    RotateRL(grandparent);
                    //变色
                    grandparent->_color = RED;
                    cur->_color = BLACK;
                }
                //情景四: p是g的右孩子，u是g的左孩子，cur是p的右孩子
                else
                {
                    //旋转
                    RotateL(grandparent);
                    //变色
                    grandparent->_color = RED;
                    parent->_color = BLACK;
                }
                break;//旋转变色后直接退出
            }
        }
    }
    //直接暴力解决cur为根节点情况
    _root->_color = BLACK;
    return true;
}

//旋转算法
void RotateL(Node* parent) //左单旋
{
    Node* cur = parent->_right;
    Node* curL = cur->_left;
    Node* pparent = parent->_parent;

    //旋转
    parent->_right = curL;
    if (curL)
        curL->_parent = parent;

    //更新节点
    if (parent == _root)
    {
        _root = cur;
        _root->_parent = nullptr;
    }
    else
    {
        if (pparent->_left == parent)
        {
            pparent->_left = cur;
            cur->_parent = pparent;
        }
        else
        {
            pparent->_right = cur;
            cur->_parent = pparent;
        }
    }

    //旋转
    cur->_left = parent;
    parent->_parent = cur;
}

void RotateR(Node* parent) //右单旋
{
    Node* cur = parent->_left;
    Node* curR = cur->_right;
    Node* pparent = parent->_parent;

    //旋转
    parent->_left = curR;
    if (curR)
        curR->_parent = parent;

    //更新节点
    if (parent == _root)
    {
        _root = cur;
        _root->_parent = nullptr;
    }
    else
    {
        if (pparent->_left == parent)
        {
            pparent->_left = cur;
            cur->_parent = pparent;
        }
        else
        {
            pparent->_right = cur;
            cur->_parent = pparent;
        }
    }

    //旋转
    cur->_right = parent;
    parent->_parent = cur;
}

void RotateLR(Node* parent) //左右旋
{
    //先左再右两次旋转
    RotateL(parent->_left);
    RotateR(parent);
}

void RotateRL(Node* parent) //右左旋
{
    //先右再左两次旋转
    RotateR(parent->_right);
    RotateL(parent);
}

2-3，红黑树的验证

        红黑树的验证不能根据红黑树的特点判断，即不能根据最长路径不超过最短路径的二倍来判断。红黑树之所以路径会满足此特点是由红黑树的性质决定的，但反过来，满足路径关系却不一定满足红黑树的性质，所以这里要根据红黑树的性质进行验证。

        红黑树的检测分为两步：1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质。

        这里重点说明第二步。红黑树的性质验证的核心检查有三点：1，根节点是黑色的。2，没有连续的红色结点。3，每条路径的黑色结点的数量相等。

        第一点代码很好实现，不做过多说明。第二点直接使用前序遍历整个树，当遍历到此时结点为红色时查看它的双亲结点，若双亲结点也是红色的验证失败。第三点方法有很多，这里可先从树的根节点选任意一个路径，记录此路径黑色结点的数量作为标杆，然后不断前序遍历所有路径，若有任意一个路径的黑色结点数量与之不同，那么遍历失败。原因很简单，树的所有路径都可看成从根节点开始的路径的子路径，只要我们在每个结点到叶子结点路径上遇到黑色结点的数量加上上面从根节点开始到此路径的黑色结点数，就如同从根节点开始的一条路径黑色结点数，即任意一个结点（这里是根节点）到后代所有路径的黑色结点数比较。

//核心检查三步:1，根节点是黑色的。2，没有连续的红色结点。3，每条路径的黑色结点的数量相等。
bool IsBalance()
{
    //核心检查1—根节点是黑色的
    if (_root && _root->_color == RED)
        return false;
    //核心检查3—每条路径的黑色结点的数量相等
    Node* cur = _root;
    //检查3中，先检查红黑树的左子树黑色结点总共的个数，即标杆
    size_t sign = 0;
    while (cur)
    {
        if (cur->_color == BLACK)
            sign++;
        cur = cur->_left;
    }
    return Check(_root, 0, sign);
}
bool Check(const Node* root, size_t blacknum, size_t sign)
{
    //一条路径结束，开始判断黑色结点数量是否相同
    if (!root)
    {
        if (blacknum != sign)
            return false;
        return true;
    }
    //核心检查2—没有连续的红色结点
    Node* parent = root->_parent;
    if (root->_color == RED && parent->_color == RED) //root结点是红色时一定不是根节点
        return false;
    //检查3中，然后以标杆做依据，遍历每个路径的黑色结点也之是否相同
    if (root->_color == BLACK)
        blacknum++;
    return Check(root->_left, blacknum, sign) && Check(root->_right, blacknum, sign);
}