数据结构--红黑树（RBTree）_红黑树 数据结构

一、红黑树概念

1.1 什么是红黑树

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

2.1 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个结点是红色的，则他的两个孩子是黑色的，及不存在两个连续的红色结点
4. 对于每个叶子结点，从该结点到其所有后代叶结点的简单路径，均包含相同数目的黑色节点
5. 每个叶子结点都是黑色的（此处的叶子节点指的是空节点）

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？

【解释】：由于红黑树要保证每条路径的黑色结点个数相同，且不能存在连续的两个红色结点，所以最短路径就是全黑，最长路径是一黑一红交替，这样红黑树的最长路径的极限也只能为最短路径的两倍

二、红黑树的实现

2.1 红黑树结点的定义

enum Color
{
	RED,
	BLACK
};
template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)
	{}
	struct RBTreeNode* _left;
	struct RBTreeNode* _right;
	struct RBTreeNode* _parent;
	pair<K, V> _kv;
	Color _col;
};

思考：在结点的定义中，为什么要将结点的默认颜色给成红色的？

【解释】：若将结点的颜色默认为黑色，由于要求每条路径的黑色结点个数相同，如果新插入一个结点，就会破坏这个性质，影响比较大，如果将结点的颜色默认为红色，那么最多也就会出现两个连续的红色结点，只会影响一条路径，只需要进行调整即可，影响比较小

2.2 红黑树的插入

1. 按照二叉搜索树的规则将结点插入到红黑树中

2. 检测插入结点后，红黑树的性质是否遭到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点（因为cur与p一定为红色，g一定为黑色，我们只需要对u进行讨论）

• 情况一：cur为红，p为红，g为黑，u存在且为红（假设uncle在g的右边）

注意：此时看到的树可能是一颗完整的树，也可能是一颗子树

解决方法：

        由于出现了连续的两个红色结点，我们只能将p变为黑色，因为如果cur为新增结点，将其变为黑色会破坏性质4，而将p变为黑色，会导致g的左右子树黑色节点不同，所以需要将u也变为黑色，而g有可能只是一颗子树，为了保证与其他路径的黑色节点个数相同，还需要将g变为红色，如果g为根节点的话，再将其变为黑色即可。

• 情况二：cur为红色，p为红色，g为黑色，u不存在或者u存在且为黑色（假设u在g的右边）

说明：u的情况存在两种

1.uncle不存在，那么cur一定是新增的那个结点，因为如果不是新增结点，那么cur和p至少有一个应该为黑色，不然就违反性质3了

2.uncle存在且为黑色，那么cur原来的颜色一定为黑色，现在看到cur的颜色为红色是因为cur子树在调整过程中将cur变为了红色

【解决办法】：

• 如果cur为p的左孩子

将p变黑，g变红，以g作为父亲结点右单旋

• 如果cur为p的右孩子

将cur变黑，g变红，先以p为父亲节点左单旋，在以g为父亲节右单旋

ps：uncle为g左边原理同上，对于旋转不清楚的可以参考数据结构--AVL树

2.3 代码实现

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);
    if (parent->_kv.first>kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;
 
    while (parent && parent->_col == RED)
    {
        Node* grandfather = parent->_parent;
        if (parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                //继续向上调整
                cur = grandfather;
                parent = cur->_parent;
            }
            else //uncle不存在或者uncle存在且为黑
            {
                if (cur == parent->_left)
                {
                    //      g
                    //    p   u
                    //  c
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    //      g
                    //    p   u
                    //      c
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
        else
        {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                //继续向上调整
                cur = grandfather;
                parent = cur->_parent;
            }
            else //uncle不存在或者uncle存在且为黑
            {
                if (cur == parent->_right)
                {
                    //      g
                    //    u   p
                    //          c
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    //      g
                    //    u   p
                    //      c
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

三、红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

bool IsBalance()
{
    if (_root->_col == RED)
        return false;
    Node* cur = _root;
    int RefNum = 0; //作为路径黑色结点个数的参考
    while (cur)
    {
        if (cur->_col == BLACK)
            RefNum++;
        cur = cur->_left;
    }
    return _IsBalance(_root,RefNum,0);
}
 
bool _IsBalance(Node* root,int RefNum,int num)
{
    if (root == nullptr)
    {
        //验证每条路径的黑色节点个数是否相同
        if (num != RefNum)
        {
            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)
        num++;
    return _IsBalance(root->_left, RefNum, num) && _IsBalance(root->_right, RefNum, num);
}