C++红黑树设计与实现详解

2.2.红黑树的查找

红黑树的查找和二叉搜索树的查找是一样的，代码也是比较类似的，它们的效率都是 log(N)，所以我就不在细讲了。

Node* Find(const K& key)
{
    Node* cur = _root; //代替根节点去遍历
    while (cur)
    {
        if (cur->_kv.first > key)
        {
            cur = cur->_left;
        }
        else if (cur->_kv.first < key)
        {
            cur = cur->_right;
        }
        else
        {
            return cur;
        }
    }
    return NULL;
}

红黑树的插入

下面我们就进入到了红黑树最难的部分（删除不算）：红黑树的插入，红黑树的插入的复杂程度还是和 AVL 数比较类似的，但是我个人感觉红黑树相对 AVL 树更加抽象一些，因为它不仅仅涉及到了旋转，还有变色的操作，依次来维持它的那四条规则，接下来我们进入红黑树的插入讲解。

在讲插入过程的时候事先说明一下：假设我们把新增的节点叫做 c(cur)，c 的父亲则标记为 p（parent），p 的父亲节点标记为 g（grandfather），p 的兄弟节点叔叔为 u（uncle）。

3.1.红黑树插入一个值的大致过程

插入一个值是按照二叉搜索树的规则来进行的，插入后的值我们需要让其符合红黑树的四条规则。如果是空树插入，那么插入的必然就是黑色节点，因为根节点必须是黑色的；如果是非空树插入，那么插入的节点一定是红色的，因为第四条规则约束着，如果插入的是黑色节点，那么第四条规则就被破坏了。非空树在插入的时候，插入的节点必须是红色节点，如果其父节点是黑色的，那么并没有违法规则，插入成功。如果其父节点是红色的，那么就违反了第三条规则。进一步的分析，c 是红色，p 也是红色，那么 g 必然是黑色的（如果 g 也是红色的那么就说明在没有插入 c 的时候此树已经违反规则了），这三个的颜色都已经定了，所以关键的变化还得看 u 的变化，分别需要分为以下四种情况讨论，在讨论之前，我先把插入的相关代码放到下面（和二叉搜索树差不多）。

bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK; //根节点一定是黑色的
    }
    Node* parent = nullptr;
    Node* cur = _root;
    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;
        }
    }
    //走到这说明插入成功了
    cur = new Node(kv);
    cur->_col = RED; //新插入的结点一定是红色
    //开始进行变色处理
    //和父亲结点进行配对
    if (parent->_kv.first < kv.first)
    {
        //比父亲结点大，插在右边
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent; //这个一定不可以忘掉
}

3.2.情况一：变色

1.讲解

如上图所示，如果 c 是红的，p 为红，g 为黑，u 存在并且是红色的话，那么我们就需要进行变色处理，即将 p 和 u 都变为黑色，g 变红。再把 g 当做新的 c，继续往上进行更新。可能很多读者不晓得我这么做的原因，下面我将进行解释。

因为 p 和 u 均是红色，g 是黑色，把 p 和 u 都变为黑色，左右子树都多增加了一个黑色节点，g 变为了红色，因为着 p 和 u 所在的支路上黑色节点的个数是没有变化的，这样就没有违反规则四，并且同时解决了红色节点的孩子还是红色节点的问题；至于为何让 g 变为新的 c，因为 g 的父节点我们并不知晓是什么颜色的，倘若还是黑色，那就皆大欢喜，不用在往上进行遍历了；但是如果是红色，那么我们还需进行变色处理。不过还有一种情况，就是 g 就是整棵树的根，那么我们就需要把 g 变为黑色，因为红黑树的根节点是黑色的。

当然，上图是属于第一种变色的特殊情况，和 AVL 树类似，我们还需了解抽象状态下的 AVL 树的变色，如下图所示。

上图则是对变色进行了比较抽象的表达，d，e，f 代表着每条路径上有 hb 个黑色节点的子树，a/b 则代表着每条路径上拥有 hb-1 个黑色节点的根为红的子树，其中 hb>=0，下面这个情况就形象的代表了当我们在 a 或者 b 中进行了一次变色，传递到上面时，可能也会让上面进行变色处理。当然，情况一仅仅设计了变色的处理，而不涉及旋转，所以左右子树都是相同的变色处理，以上就是情况一的讲解，下面我们进入代码的讲解。

2.代码

此时我们还需要划分此时的父亲节点是左子树还是右子树，下面我们就单拿左子树为例，因为左右子树都是差不多的，掌握了一种，另一种也是会更为轻松的掌握。

刚开始，我们需要先把 g 节点表示出来，即 p 节点的父亲节点，因为我们进行变色处理以后，需要往上进行更新，所以变色的操作应该是一次次循环的过程。

while (parent && parent->_col == RED)
{
    Node* grandfather = parent->_parent;
}

我们需要通过 if 语句确认 p 节点是在左边的，之后我们需要把 u 节点表示出来，如果此时 u 节点存在并且 u 节点就是红色的，那么就符合情况一，之后我们先把 p 和 u 节点都染成黑色的，再把 g 节点变为红色的，做完这些操作以后，我们就需要更新一下 c 和 p 节点了更新结束，代表一次变色成功，继续往上进行更新。

if (grandfather->_left == parent)
{
    Node* uncle = grandfather->_right;
    if (uncle && uncle->_col == RED)
    {
        //单纯的变色处理
        grandfather->_col = RED;
        parent->_col = BLACK;
        uncle->_col = BLACK;
        //在往上进行查询
        cur = grandfather;
        parent = cur->_parent;
    }
}

1.完整变色（p 节点在左边）

while (parent && parent->_col == RED)
{
    Node* grandfather = parent->_parent; //先来节点都是左边的情况
    if (grandfather->_left == parent)
    {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
            //单纯的变色处理
            grandfather->_col = RED;
            parent->_col = BLACK;
            uncle->_col = BLACK;
            //在往上进行查询
            cur = grandfather;
            parent = cur->_parent;
        }
    }
}

2.完整变色（p 节点在右边）

if(grandparent->_right == parent)
{
    Node* uncle = grandfather->_left;
    if (uncle&& uncle->_col == RED)
    {
        grandfather->_col = RED;
        parent->_col = BLACK;
        uncle->_col = BLACK;
        //在往上进行查询节点是否正确
        cur = grandfather;
        parent = cur->_parent;
    }
}

3.3.情况二：单旋 + 变色

1.讲解

又看到了我们的老朋友：单旋了，上次我们和它见面还是 AVL 树，没想到到了红黑树，它又来追杀我们了，不过红黑树的单旋其实和 AVL 树是类似的，这意味着我们可以直接使用 AVL 树的单旋代码，下面我通过一个特殊的例子来给各位讲解情况二。

如果 c 是红色，p 是红色，g 为黑，u 不存在或者 u 是黑色的时候，这个时候我们就不能单单依靠表变色进行红黑树的修正了，因为这样会违反规则四；如果 u 不存在，那么 c 一定就是新的节点；如果 u 是黑的，那么 c 一定不是新的节点，而是因为之前 c 本来就是黑色的节点，但是由于进行了变色处理，导致 c 变成了红色节点。

如果 p 是 g 的左子树，如上图所示，c 是 p 的左子树，那么我们就以 g 为旋转点，先进行一次右单旋，如下图所示。

此时我们需要让 g 变为红色，p 变为黑色即可。此时 p 变成了这棵子树新的根了，这样子树黑色节点的数量不变，没有连续的红色节点，并且还不需要往上进行更新了，因为 p 的父亲无论是啥都没会违反这些规则了。

如果 p 是 g 的右子树，c 是 p 的右，如上图所示，那么我们还是以 g 为旋转点，但是是左单旋，如下图所示。

此时我们需要让 p 变为黑色，g 变为红色即可，p 变为了新子树的根，这样子树的黑色节点的数量并没有改变，没有连续的红色节点，并且还不需要往上进行更新了。

当然，我们学完了特殊情况，还需要知晓一些抽象情况，下面我就放上一张图片，希望各位读者自行阅读。

2.代码

首先我们需要先知晓，此时的情况二也是在循环之中的，此时我们还是以右单旋为例进行讲解，当 c 为 p 的左孩子时，意味着此时我们需要单旋进行处理（前提是 u 节点为黑色或者是空），那么此时我们需要进行单旋处理，单旋的话我们直接把 AVL 树的单旋 copy 过来即可（忘了的看我上一篇文章），之后在进行相应的变色处理即可。下面我把两个完整代码展示出来。

1.右单旋 + 变色

if(uncle -> col == black || uncle == nullptr)
{
    if(parent -> left == cur)
    {
        //右单旋
        RotateR(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
        break; //无须在往上走了
    }
}

2.左单旋 + 变色

if(uncle -> col == black || uncle == nullptr)
{
    if(parent -> right == cur)
    {
        //进行左单旋处理
        RotateL(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    }
}

3.情况三：双旋 + 变色

既然都有单旋这种情况了，那么双旋也是必不可少的，当然，双旋的代码还是和 AVL 树是一样的，减少了很大部分的工作量。

1.讲解

情况三的颜色情况其实和情况二是类似的，它们均是 c 和 p 都是红色，g 为黑色，u 是不存在或者为黑色，所以下面我们进入双旋情况的讲解。

如果 p 是 g 的左，c 是 p 的右，此时我们仅仅依靠单旋是不可以进行红黑树的纠正的，所以此时我们就需要通过双旋进行调整，我们先以 p 为旋转点进行一次左旋，在以 g 进行一次右旋，如下图所示。

此时我们仅需让 c 变为黑色，g 变为红色即可，c 变成了这棵树新的根，这样做黑色节点的数目没有改变，没有连续的红色节点了，因为 g 是黑色，此时无论他的父节点是什么，都不会影响结果了。

如果此时 p 是 g 的有孩子，c 是 p 的左孩子，这个时候我们也是需要双旋进行处理的，先以 p 为旋转点进行右旋，再以 g 为旋转点进行左旋，之后把 c 变为黑色，g 为红色即可。

以上是红黑树情况二的特殊情况，下面我们来看看一般情况，即抽象表达，看一看下图的图，我相信你会懂的。

2.代码

我个人认为情况三的代码比较容易，各位读者通过我上面的讲解应该就知晓代码如何书写了，所以我下面直接放代码。

如果 p 是 g 的左孩子

//左右双旋转
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
general_father->_col = RED;

如果 p 是 g 的右孩子

RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
general_father->_col = RED;

红黑树的验证

1.如何验证

此时我们已经讲述完了红黑树相关知识点的讲解，可能有很多读者想知道自己写的红黑树是否是正确的，下面我将给各位讲述一下如何验证自己写的红黑树。此时我们需要检验四条规则，如果满足这四条规则，那么说明这棵树就是一颗非常棒的红黑树。

1. 规则一枚举颜色类型，天然的实现保证了节点非红即黑。
2. 规则二直接检查根部即可
3. 规则三进行前序遍历检查，遇到红色节点检查孩子不太方便，因为孩子是有两个的，并且不一定就是存在的，反过来检查颜色就方便多了。
4. 规则四进行前序遍历，遍历过程中用形参记录根到当前节点的黑色节点的数量，前序遍历遇到黑色节点就++blackNum，走到空就计算一条路径黑色节点的数量。以任意一条路径的黑色节点数量作为基准，依次比较即可。

2.相关代码

bool Check(Node* root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        // 前序遍历走到空时，意味着一条路径走完了
        if (refNum != blackNum)
        {
            cout << "存在黑色结点的数量不相等的路径" << endl;
            return false;
        }
        return true;
    }
    // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;
    }
    if (root->_col == BLACK)
    {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

完整代码

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<ctime>
namespace wang
{
    using namespace std;
    enum Colour { RED, BLACK };
    template<class K, class V> struct RBTreeNode
    {
        pair<K, V> _kv;
        RBTreeNode<K, V>* _left;
        RBTreeNode<K, V>* _right;
        RBTreeNode<K, V>* _parent;
        Colour _col;
        RBTreeNode(const pair<K, V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED) {}
    };
    template<class K, class V> class RBTree
    {
        typedef RBTreeNode<K, V> Node;
    private:
        void RotateR(Node* parent)
        {
            Node* subl = parent->_left;
            Node* sublR = subl->_right;
            parent->_left = sublR;
            if (sublR)
            {
                sublR->_parent = parent;
            }
            Node* ppnode = parent->_parent;
            subl->_right = parent;
            parent->_parent = subl;
            if (ppnode == nullptr)
            {
                _root = subl;
                subl->_parent = ppnode;
            }
            else
            {
                if (subl->_kv.first > ppnode->_kv.first)
                {
                    ppnode->_right = subl;
                }
                else
                {
                    ppnode->_left = subl;
                }
                subl->_parent = ppnode;
            }
        }
        void RotateL(Node* parent)
        {
            Node* subL = parent->_right;
            Node* subLL = subL->_left;
            Node* ppnode = parent->_parent;
            parent->_right = subLL;
            if (subLL)
            {
                subLL->_parent = parent;
            }
            subL->_left = parent;
            parent->_parent = subL;
            if (ppnode == nullptr)
            {
                _root = subL;
                subL->_parent = nullptr;
            }
            else
            {
                if (subL->_kv.first > ppnode->_kv.first)
                {
                    ppnode->_right = subL;
                }
                else
                {
                    ppnode->_left = subL;
                }
                subL->_parent = ppnode;
            }
        }
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_kv.first << ":" << root->_kv.second << endl;
            _InOrder(root->_right);
        }
    public:
        bool Insert(const pair<K, V>& kv)
        {
            if (_root == nullptr)
            {
                _root = new Node(kv);
                _root->_col = BLACK;
            }
            Node* parent = nullptr;
            Node* cur = _root;
            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;
                }
            }
            cur = new Node(kv);
            cur->_col = RED;
            if (parent->_kv.first < kv.first)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }
            cur->_parent = parent;
            while (parent && parent->_col == RED)
            {
                Node* grandfather = parent->_parent;
                if (grandfather->_left == parent)
                {
                    Node* uncle = grandfather->_right;
                    if (uncle && uncle->_col == RED)
                    {
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        uncle->_col = BLACK;
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (parent->_left == cur)
                        {
                            RotateR(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            RotateL(parent);
                            RotateR(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
                else
                {
                    Node* uncle = grandfather->_left;
                    if (uncle&& uncle->_col == RED)
                    {
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        uncle->_col = BLACK;
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (parent->_right == cur)
                        {
                            RotateL(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            RotateR(parent);
                            RotateL(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
            }
            _root->_col = BLACK;
            return true;
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_kv.first > key)
                {
                    cur = cur->_left;
                }
                else if (cur->_kv.first < key)
                {
                    cur = cur->_right;
                }
                else
                {
                    return cur;
                }
            }
            return NULL;
        }
        void InOrder()
        {
            _InOrder(_root);
        }
        bool Check(Node* root, int blackNum, const int refNum)
        {
            if (root == nullptr)
            {
                if (refNum != blackNum)
                {
                    cout << "存在黑色结点的数量不相等的路径" << endl;
                    return false;
                }
                return true;
            }
            if (root->_col == RED && root->_parent->_col == RED)
            {
                cout << root->_kv.first << "存在连续的红色结点" << endl;
                return false;
            }
            if (root->_col == BLACK)
            {
                blackNum++;
            }
            return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
        }
        bool IsBalance()
        {
            if (_root == nullptr) return true;
            if (_root->_col == RED) return false;
            int refNum = 0;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_col == BLACK)
                {
                    ++refNum;
                }
                cur = cur->_left;
            }
            return Check(_root, 0, refNum);
        }
        int Height()
        {
            return _Height(_root);
        }
        int Size()
        {
            return _Size(_root);
        }
    protected:
        int _Size(Node* root)
        {
            if (root == nullptr) return 0;
            return _Size(root->_left) + _Size(root->_right) + 1;
        }
        int _Height(Node* root)
        {
            if (root == nullptr) return 0;
            int leftHeight = _Height(root->_left);
            int rightHeight = _Height(root->_right);
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
    private:
        Node* _root = nullptr;
    };
}