红黑树【C/C++实现】

最新推荐文章于 2025-04-03 18:04:57 发布

沉默.@

最新推荐文章于 2025-04-03 18:04:57 发布

阅读量591

点赞数 1

文章标签： c++ c语言算法

本文链接：https://blog.csdn.net/smf12138/article/details/127293621

版权

红黑树

🏞️1. 红黑树的概念及性质

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

红黑树的性质：

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

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

分析如下：

🌁2. 红黑树节点定义

enum Color
{
    BLACK,
    RED
};

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode(pair<K, V> kv = pair<K, V>(), Color color = RED)
        : _kv(kv)
            , _color(color)
            , _left(nullptr), _right(nullptr), _parent(nullptr)
        {}

    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;

    pair<K, V> _kv;   //节点存储的数据
    Color _color;  //节点的颜色
};

🌠3. 红黑树插入

红黑树的插入与二叉搜索树的插入类似，只不过新增加了对于平衡的调整，可分为三种情况：

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

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

上图情况二中c，d，e可能为这四种结果中的任意一种：
情况二：cur为红，p为红，u不存在/u存在且为黑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色–p变黑，g变红

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

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；

相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转则转换成了情况2

具体情况分析：

情况二和情况三旋转+变色处理后，这棵子树不违反红黑树的规则，而且黑色节点数量相比插入前没有变化，所以不会再影响上层，调整结束.

红黑树插入代码：

bool insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_color = BLACK;

        return true;
    }

    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->_color = RED;
    if (kv.first > parent->_kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }

    cur->_parent = parent;

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

        //情况一：
        if (parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;

            if (uncle && uncle->_color == RED)
            {
                parent->_color = BLACK;
                uncle->_color = BLACK;
                grandfather->_color = RED;

                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_left)
                {
                    RotateR(parent);
                    parent->_color = BLACK;
                    grandfather->_color = RED;
                }
                else
                {
                    RotateL(parent);
                    RotateR(grandfather);

                    parent->_color = BLACK;
                    grandfather->_color = RED;
                }

                break;
            }
        }
        else
        {
            //p在g的右边
            Node* uncle = grandfather->_left;

            if (uncle && uncle->_color == RED)
            {
                grandfather->_color = RED;
                uncle->_color = BLACK;
                parent->_color = BLACK;

                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_right)
                {
                    RotateL(grandfather);

                    parent->_color = BLACK;
                    grandfather->_color = RED;
                }
                else
                {
                    RotateR(parent);
                    RotateL(grandfather);

                    grandfather->_color = RED;
                    cur->_color = BLACK;
                }

                break;
            }
        }


    }

    _root->_color = BLACK;

    return true;
}

🌌4. 红黑树的验证

红黑树的验证分为两步：

检测其是否满足二叉搜索树（中序遍历是否为有序序列）
检测其是否满足红黑树的性质

//提供给用户的接口
bool isVaildRBTree()
{
    Node* root = _root;

    //空树也是红黑树
    if (nullptr == _root)
        return true;

    //检测根结点是否满足性质
    if (BLACK != _root->_color)
    {
        cout << "违反了红黑树的性质二：根结点必须为黑色" << endl;
        return false;
    }

    size_t blackCount = 0;
    Node* cur = _root;

    while (cur)
    {
        if (BLACK == cur->_color)
        {
            ++blackCount;
        }
        cur = cur->_left;
    }

    size_t k = 0;
    return _isVaildRBTree(_root, k, blackCount);
}

//内部递归函数
bool _isVaildRBTree(Node* root, size_t k, const size_t blackCount)
{
    //走到nullptr时，判断k与blackCount是否相等
    if (root == nullptr)
    {
        if (k != blackCount)
        {
            cout << "违反性质4：每条路径黑色节点个数必须相同" << endl;
            return false;
        }

        return true;
    }

    //统计路径上黑色节点的个数
    if (BLACK == root->_color)
        ++k;

    //检测当前节点及其双亲是否都为红色
    Node* parent = root->_parent;
    if (parent && parent->_color == RED && root->_color == RED)
    {
        cout << "违反性质三：没有连续的红色节点" << endl;
        return false;
    }

    return _isVaildRBTree(root->_left, k, blackCount)
        && _isVaildRBTree(root->_right, k, blackCount);
}