红黑树（RBTree）认识总结

一、认识红黑树

1.1 什么是红黑树？

红黑树是一种二叉搜索树，与普通搜索树不同的是，在每个节点上增加一个“颜色”变量 —— RED / BLACK 。

通过对各个节点颜色的限制，确保从 根 到 NIL ，没有一条路径会比其他路径长出两倍。

（NIL ：表示叶子节点的空指针，统一设置为 BLACK ）

1.2 红黑树的性质

• 根节点一定是黑色
• 不能出现两个连续的红色节点
• 对于同一高度而言，从根到该高度任一节点的简单路径上的黑色节点的数量相同

1.3 红黑树节点定义

二、红黑树

2.1 红黑树定义

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
    
private:
    Node* _root;
};

2.2 插入

红黑树的插入是我们学习红黑树过程最重要的知识之一，它主要分为两部分：平衡二叉树的插入 和 旋转 —— 调整树形结构。

插入部分与普通搜索树没有本质区别，这里不做过多介绍。

声明一下：代码中的 grandfather 和 图中的 grandparent 为同一东西，笔者在基本结束本篇时发现这里差异。

• 插入部分

bool Insert(const pair<K, V> kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK; // 根一定为黑色节点
        return true;
    }
    
    Node* cur = _root;
    Node* parent = nullptr;
    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);
    if (cur == parent->_left)
    {
        parent->_left = cur;
    }
    else 
    {
        parent->_right = cur;
    }
    cur->_parent = parent;
    
    _root->_col = BLACK; // 强制设定根一定为黑色！
    return true;
}

• 旋转

2.2.1 什么时候要旋转？

我们新插入的节点默认是红色，当它的 parent 存在且为红色时，就出现了这种情况 —— 树存在两个连续的红色节点，此时我们需要对该部分子树进行旋转 —— 调整树的结构。(下图只展示了部分的子树)

判断条件：parent 存在且为红色

	while (parent && parent->_col == RED)
    { }

2.2.2 几种旋转情况

情形一：uncle 存在，且为红色节点

	Node* grandfather = parent->_parent;
	if (parent == grandfather->_left)
    {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED) // 叔叔存在且为红色
        {
            grandfather->_col = RED;
            parent->_col = BLACK;
            uncle->_col = BLACK;

            cur = grandfather; //  向上调整
            parent = cur->_parent;
        }
    }
	
	if (parent == grandfather->_right)
    {
        Node* uncle = grandfather->_left;
        // ... // 与上面代码一致
    }

情形二：uncle 不存在 或 存在且为黑色

• parent 在 grandfather 左侧的两种情况

	if (parent == grandfather->_left) // parent 在 grandfather 左侧的两种情况
    {
        if (!uncle || uncle->_col == BLACK)
        {
            if (cur == parent->_left) // cur 在 parent 左侧
            {
                RotateR(grandfather);
                
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else // cur 在 parent 右侧
            {
                RotateL(parent);
                RotateR(grandfather);
                
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            break; // 旋转结束后，一定要 break 
            
        }
    }

旋转结束后，树的结构已经满足了红黑树的标准，如果不跳出循环、继续调整，会出现各种奇怪的问题。

• parent 在 grandfather 右侧

	if (parent == grandfather->_right) // parent 在 grandfather 右侧
    {
        if (!uncle || uncle->_col == BLACK) // uncle 不存在 或 uncle存在且为黑色节点
        {
            if (cur == parent->_right) // cur 在 parent 右侧
            {
                RotateL(grandfather);
                
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else // cur 在 parent 左侧
            {
                RotateR(parent);
                RotateL(grandfather);
                
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            break;
        }
    }

2.3 红黑树的验证

红黑树的验证，顾名思义，就是验证 你的“红黑树” 是否能满足红黑树的三条性质。

• 根节点一定是黑色
• 不能出现两个连续的红色节点
• 对于同一高度而言，从根到该高度任一节点的简单路径上的黑色节点的数量相同

	bool IsBalance()
    {
        if (_root && _root->_col == RED) // 验证第一条性质
        {
            cout << "根节点为红色" << endl;
            return false;
        }
        
        // 要判断是否每一条路径上的黑色节点数相同，首先要找一个标杆 —— 这里旋转树最左路径的黑色节点个数
        Node* cur = _root;
        int RefBlackNum = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++RefBlackNum;
            
            cur = cur->_left;
        }
        
        return Check(_root, 0, RefBlackNum);
    }

	bool Check(Node* cur, int BlackNum, int RefBlackNum)
    {
        if (cur == nullptr) //  走到 NIL 时，判断该路径黑色节点个数是否与标杆相同
        {
            if (BlackNum != RefBlackNum)
            {
                cout << "路径黑色节点的个数不相同" << endl; // 验证第三条性质
                return false;
            }
            return true;
        }
        
        if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED)
        {
            cout << "存在两个连续的红色节点" << endl; // 验证第二条性质
            return false;
        }
        
        if (cur->_col == BLACK)
            ++BlackNum;
        
        return Check(cur->_left, BlackNum, RefBlackNum) // 递归判断当前节点的左右子树是否合法
            && Check(cur->_right, BlackNum, RefBlackNum);
    }