【C++】红黑树，“红“与“黑”的较量

各位大佬好，我是落羽！一个坚持不断学习进步的大学生。
如果您觉得我的文章有所帮助，欢迎多多互三分享交流，一起学习进步！
也欢迎关注我的blog主页: 落羽的落羽

一、红黑树的概念与规则

红黑树有以下四条规则：

1. 每个结点不是红色就是黑色
2. 根结点是黑色的
3. 如果一个结点是红色的，则它的两个孩子必须都是黑色的，也就是说任意一条路径上不会出现连续的红色结点（黑色结点的孩子颜色不做要求）
4. 对于任意一个结点，从结点到这棵树所有空结点的简单路径上，均包含相同数量的黑色结点

依靠它的几条规则，从同一结点出发红黑树没有一条路径会比其他路径长出2倍，因而也是接近平衡的。这是因为，由于从根到空结点的每条路径都有相同数量的黑色结点，所以极限场景下，理论最短路径就是全是黑色结点的路径（设长度为bh），理论最长路径是一黑一红间隔组成，长度就是2bh了。也就是说，红黑树中任意一条从根到空结点的路径x，都有bh <= x <= 2bh，确保了红黑树最长路径不超过最短路径的2倍了。

假设N是红黑树中结点数量，h是最短路径长度，那么2^h -1 <= N <= 2^2h -1 ，推出h约等于logN，红黑树增删查改最坏情况也就是走最长路径2*logN，时间复杂度还是O(logN)。

这些规则保证了红黑树的平衡性，使得树的高度保持在logN级别。相比于AVL树，红黑树的平衡结构可以说更加“松散”，AVL树严格要求了左右子树高度差不超过1，但红黑树只要路径长不超过2倍就行，但它们的效率还是相同的水平。

二、红黑树的实现

红黑树的结构

enum Color
{
	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;
	Color _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;
public:

private:
	Node* _root;
};

红黑树的插入

• 首先按照二叉搜索树的规则找到应插入的位置，插入后我们需要判断是否符合红黑树的规则。
• 如果是空树插入，新增结点必须是黑色的，插入完成；如果是非空树插入，新增结点必须是红色的，因为如果非空树插入了黑色结点就会破坏规则4，这条规则是很难维护的。
• 非空树插入红色结点后，如果父亲是黑色的，则不会破坏任何规则，插入完成。
• 非空树插入红色结点后，如果父亲是红色的，就破坏了规则“红色结点的孩子必须是黑色”，此时需要下面进一步分析。

接下来，我们具体分析最后一条情况，又有几种场景。下面称新增结点为c，c的父亲为p，p的父亲为g，p的兄弟为u。c是红色的，p也是红色的，那么g一定是黑色的，这三者的颜色是确定的，所以关键是看u的状态（下图中只表示出cpgu结点，省略其他子树）：

场景1：

u存在且为红色。这种场景下，c保持红色不变，使p和u都变成黑色，g变为红色。这样处理后，就能使包含p或u的路径的黑色结点数量保持一致。

场景2：

u存在且为黑色 或 u不存在。u不存在，则c一定是新增结点；u存在且为黑，则c一定不是新增结点，而是新增结点插入在了c的子树中通过场景1调整后使c变成了红色。

这两种情况下处理方式是一样的，需要旋转+变色处理，但是旋转变色的方式，和AVL树一样仍需分情况讨论：

• p是g的左，c是p的左。以g为旋转点右单旋。然后把p变黑，g变红。如图
• p是g的右，c是p的右。以g为旋转点左单旋。然后把p变黑，g变红。如图
• p是g的左，c是p的右。**先以p为旋转点左单旋，再以g为旋转点右单旋（左右双旋）。然后把c变黑，g变红。**如图
• p是g的右，c是p的左。**先以p为旋转点右单旋，再以g为旋转点左单旋（右左双旋）。然后把c变黑，g变红。**如图

红黑树的插入代码实现：

bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
    cur = new Node(kv);
    cur->_col = RED;
    cur->_parent = parent;
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }

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

            //p是g的左的情况
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                //u存在且为红色
                //变色
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                    //u不存在或存在为黑色
                else //旋转+变色
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }

                //p是g的右的情况
            else
            {
                Node* uncle = grandfather->_left;
                //u存在且为红色
                //变色
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                    //u不存在或存在为黑色
                else //旋转+变色
                {
                    if (cur == parent->_right)
                    {
                        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;
}

红黑树的验证

• 规则1不用检查，因为我们一开始就用了枚举类型赋值
• 规则2检查根结点颜色即可
• 规则3进行前序遍历，遇到红色结点就检查它的父结点是不是红色的
• 规则4，首先用一个refNum记录最左路径的黑色结点数量，进行前序遍历，遍历过程中用一个变量blackNum记录到当前结点的黑色结点数量，遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。此时若blackNum与refNum不同，则规则4不满足。

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 << "存在连续的红色结点！" << 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;
    }
    //参考值refNum记录最左路径的黑色结点数量
    int refNum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
        {
            refNum++;
        }
        cur = cur->_left;
    }
    return Check(_root, 0, refNum);
}

本篇完，感谢阅读~