【数据结构】红黑树-蒲公英云

【数据结构】红黑树

矫情吗；* 2024-03-17 17:04 110阅读 0赞

文章目录

红黑树
- 1. 红黑树的概念
- 1. 红黑树的性质
- 1. 红黑树节点的定义
- 1. 红黑树的结构
- 1. 红黑树的插入操作

红黑树

1. 红黑树的概念

红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或者是Black。通过任何一条根到叶子的路径各个节点着色方式的限制。红黑树确保任何一条路径不会比其他路径长度多出两倍，所以是平衡的

2. 红黑树的性质

每个节点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，它的两个孩子节点是黑色的
对于每个节点，从该节点到其所有后代叶节点的简单路径上，包含相同数目的黑色节点
每个叶子节点都是黑色的（此处的叶子节点表示空节点）

3. 红黑树节点的定义

enum Color {
    RED,
    BLACK
};
template<class ValueType>
class RBTreeNode {
public:
    explicit RBTreeNode(const ValueType& data = ValueType(), Color color = RED):_left(nullptr),
    _right(nullptr),
    _parent(nullptr), _data(data), _color(color)
    {
    }
    RBTreeNode<ValueType>* _left;
    RBTreeNode<ValueType>* _right;
    RBTreeNode<ValueType>* _parent;
    ValueType _data;
    Color _color;
};

在节点的定义当中，为什么将节点的默认颜色给为红色？

通过把新插入的节点默认为红色，可以较快地满足红黑树的性质，并且减少了插入操作时需要进行的旋转操作次数，提高了插入操作的效率。同时，红色节点相对于黑色节点来说，占用的存储空间更小，节省了内存空间。因此，在红黑树中，默认将节点的颜色给为红色。

4. 红黑树的结构

红黑树当中增加了一个头结点，如下图所示

5. 红黑树的插入操作

红黑树是在二叉搜索树的基础上加平衡限制条件，因此红黑树插入可以分为两步：

按照二叉搜索树的规则插入新节点
检测新节点插入之后红黑树的性质是否改变

约定：cur表示当前节点、p父节点、g为祖父节点，u为叔叔节点

情况一：cur为红色，p为红，g为红, u存在且为红

注意：上图的数可以是一棵完整的树，也可能是一棵子树

黑色是可以连着出现，但是红色节点不行。

如果g是根节点，调整完成之后，需要将g改为黑色。如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整

cur 和 p均为红，违反了性质三。将p和u改为黑，然后把g当做cur继续向上调整

情况二：cur为红，p为红，g为黑色。u不存在/u存在且为黑

u的情况有两种

如果u不存在，则cur一定是新插入的节点。如果cur不是新插入的节点，则cur和p则一定有一个节点颜色是黑色，就不满足性质四
如果u存在，一定是黑色，那么cur原来的颜色一定是黑色，现在看到红色的原因是在调整的过程中将cur节点的颜色改为红色

p为g的左孩子，cur为p的左孩子，进行右旋

p为g的右孩子，cur为p的右孩子，进行左旋

p、g变色–p变黑，g变红

情况三：cur为红，p为红，g为黑u不存在/u存在且为黑

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

Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
    Node* uncle = grandfather->_right;
    // 情况1：u存在且为红，变色处理，并继续往上处理
    if (uncle && uncle->_col == RED)
    {
        parent->_col = BLACK;
        uncle->_col = BLACK;
        grandfather->_col = RED;
        // 继续往上调整
        cur = grandfather;
        parent = cur->_parent;
    }
    else // 情况2+3：u不存在/u存在且为黑，旋转+变色
    {
        //     g
        //   p   u
        // c 
        if (cur == parent->_left)
        {
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
        }
        else
        {
            //     g
            //   p   u
            //     c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            //parent->_col = RED;
            grandfather->_col = RED;
        }
        break;
    }
}
else // (grandfather->_right == parent)
{
    //    g
    //  u   p
    //        c
    Node* uncle = grandfather->_left;
    // 情况1：u存在且为红，变色处理，并继续往上处理
    if (uncle && uncle->_col == RED)
    {
        parent->_col = BLACK;
        uncle->_col = BLACK;
        grandfather->_col = RED;
        // 继续往上调整
        cur = grandfather;
        parent = cur->_parent;
    }
    else // 情况2+3：u不存在/u存在且为黑，旋转+变色
    {
        //    g
        //  u   p
        //        c
        if (cur == parent->_right)
        {
            RotateL(grandfather);
            grandfather->_col = RED;
            parent->_col = BLACK;
        }
        else
        {
            //    g
            //  u   p
            //    c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
        }
        break;
    }
}