C++ 精通之路：红黑树

作者：雪芙花

2022-10-24
湖南
本文字数：4828 字
阅读完需：约 16 分钟

红黑树

一：红黑树的概念

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

二：红黑树的性质

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

通过以上的规则，就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍从而达到相对平衡

三：红黑树节点的定义

// 节点的颜色enum Color{RED, BLACK};// 红黑树节点的定义template<class ValueType>struct RBTreeNode{RBTreeNode(const ValueType& data = ValueType()，Color color = RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode<ValueType>* _pLeft; // 节点的左孩子RBTreeNode<ValueType>* _pRight; // 节点的右孩子RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字ValueType _data; // 节点的值域Color _color; // 节点的颜色};

复制代码

注意：

需要将节点的默认颜色给成红色的，因为红色不影响红黑树的整体结构。在后续插入的情况，也是一样

四：红黑树结构

在 stl 源码中的结构：

五：红黑树的插入操作

先用简单的比较，找到插入节点需要插入的位置
因为默认是为红色，所以要向上判断是否违反规则，情况如下：

父亲是黑色，则不用做任何操作即可满足红黑树的结构
父亲是红色，出现了连续的红节点，不满足红黑树的结构，需要处理，具体处理情况如下：

具体处理情况：

因为父亲是红色，所以父亲不可能是根，因为不能出现连续的红节点，所以祖父是黑节点，
祖父和父亲都确定了，只有祖父的另外一个孩子（叔叔）的颜色没有确定
所以我们以叔叔的颜色为特殊情况再以次分析如何处理

注：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点

情况一（只需要变色）：

cur 为红，p 为红，g 为黑，u 存在且为红

因为有连续的红节点，必须要做变色处理了，如何保证在不破坏红黑树的整体结构下来做变色处理呢？

我们选择把 g 变红，p 和 u 变黑来处理。
这样就保证了在 p 和 u 这两条路径下的黑色节点没有发生改变并且没有了连续的红节点
但是 g 的改变也会导致 g 上层结构的变化，所以我们还要做出改变：

假如 g 为根节点的时候，将其变黑
假如 g 不为根节点的时候，则继续以 g 为新增节点向上调整

情况二（单旋加变色）：

cur 为红，p 为红，g 为黑，u 不存在/u 为黑

假如 u 不存在，则 cur 一定是新增节点，因为假如 cur 原来是黑色的话，就违反了规则：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
假如 u 存在，所以 u 为黑色（为红色的情况以讨论）：假设 cur 是新增节点，则在 cur 未插入前，p 左子树的这条路径的长度已经逼 u 上的路径上的黑色节点少了，违反了规则：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点，所以假设不成立，cur 一定是从黑色变为红色的

解决方法：

如果 p 为 g 的左孩子，cur 为 p 的左孩子，则进行右单旋转，p 变黑，g 变红如果 p 为 g 的右孩子，cur 为 p 的右孩子，则进行左单旋转，p 变黑，g 变红

原因/理由：如果 p 为 g 的左孩子，cur 为 p 的左孩子，则失去了平衡，通过变色已经无法满足要求了，所以我们就要借助旋转来帮助我们。所以如果 p 为 g 的左孩子，cur 为 p 的左孩子，则进行右单旋转，p 变黑，g 变红。即平衡了整个树，又保证了路径中的黑色节点不变。

情况三（双旋加变色）：

也是 cur 为红，p 为红，g 为黑，u 不存在/u 为黑，但 cur 的位置发生了变化，如图所示：

解决办法：

如果 p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 做左单旋转，p 旋转后再对 g 进行右单旋，旋转后将 cur 变黑，g 变红
如果 p 为 g 的右孩子，cur 为 p 的左孩子，则针对 p 做右单旋转，p 旋转后再对 g 进行左单旋，旋转后将 cur 变黑，g 变红

具体步骤图：

插入的实现

pair<Node*, bool> Insert(const pair<K, V>& kv){    //空树的情况    if (_root == nullptr)    {        _root = new Node(kv);        _root->_col = BLACK;        return make_pair(_root, true);    }
    //查找位置插入节点    Node* cur = _root, * parent = _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 make_pair(cur, false);        }    }
    //创建链接节点    cur = new Node(kv);    Node* newnode = cur;    if (parent->_kv.first > kv.first)    {        parent->_left = cur;    }    else    {        parent->_right = cur;    }    cur->_parent = parent;        //父节点存在且为红，则需要调整（不能存在连续的红色节点）    while (parent && parent->_col == RED)    {        //此时当前节点一定有祖父节点        Node* granparent = parent->_parent;        //具体调整情况主要看叔叔节点        //分左右讨论        if (parent == granparent->_left)        {            Node* uncle = granparent->_right;            //情况1：叔叔节点存在且为红            if (uncle && uncle->_col == RED)            {                //修改颜色，继续向上检查                granparent->_col = RED;                parent->_col = uncle->_col = BLACK;
                cur = granparent;                parent = cur->_parent;            }            else//情况2和3：叔叔节点不存在 或者存在且为黑            {                //单旋(三代节点为斜线)+变色                if (cur == parent->_left)                {                    RotateR(granparent);
                    granparent->_col = RED;                    parent->_col = BLACK;                }                else//双旋(三代节点为折线)+变色                {                    RotateL(parent);                    RotateR(granparent);
                    cur->_col = BLACK;                    granparent->_col = RED;                }                //旋转后不需再向上调整了                break;            }        }        else//parent=grandparent->right        {            Node* uncle = granparent->_left;            if (uncle && uncle->_col == RED)            {                parent->_col = uncle->_col = BLACK;                granparent->_col = RED;
                cur = granparent;                parent = cur->_parent;            }            else            {                if (cur == parent->_right)                {                    RotateL(granparent);
                    parent->_col = BLACK;                    granparent->_col = RED;                }                else                {                    RotateR(parent);                    RotateL(granparent);
                    cur->_col = BLACK;                    granparent->_col = RED;                }                break;            }        }    }        //确保根节点为黑    _root->_col = BLACK;    return make_pair(newnode, true);}

复制代码

旋转实现

void RotateL(Node* parent){    Node* subR = parent->_right;    Node* subRL = subR->_left;    Node* parentP = parent->_parent;

    parent->_right = subRL;    if (subRL)    {        subRL->_parent = parent;    }
    subR->_left = parent;    parent->_parent = subR;
    if (parent == _root)    {        _root = subR;        subR->_parent = nullptr;    }    else    {        subR->_parent = parentP;        if (parentP->_left == parent)        {            parentP->_left = subR;        }        else        {            parentP->_right = subR;        }    }}
void RotateR(Node* parent){    Node* subL = parent->_left;    Node* subLR = subL->_right;    Node* parentP = parent->_parent;

    parent->_left = subLR;    if (subLR)    {        subLR->_parent = parent;    }
    subL->_right = parent;    parent->_parent = subL;
    if (parent == _root)    {        _root = subL;        subL->_parent = nullptr;    }    else    {        subL->_parent = parentP;        if (parentP->_left == parent)        {            parentP->_left = subL;        }        else        {            parentP->_right = subL;        }    }}

复制代码

六:红黑树的验证

红黑树的检测分为两步：

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

实现代码：

bool IsRBTree(){    //空树    if (_root == nullptr)    {        return true;    }    //根节点为黑色    if (_root->_col == RED)    {        cout << "根节点为红色" << endl;        return false;    }    //黑色结点数量各路径上相同    //先走一条得到基准值    int Blacknum = 0;    Node* cur = _root;    while (cur)    {        if (cur->_col == BLACK)            Blacknum++;        cur = cur->_left;    }    //检查子树    int i = 0;    return _IsRBTree(_root, Blacknum, i);}
bool _IsRBTree(Node* root, int blacknum, int count){    //递归到空节点    if (root == nullptr)    {        if (blacknum == count)            return true;        cout << "各路径上黑色节点个数不同" << endl;        return false;    }  //子节点为红则检查父节点是否为红（通过父节点检查子节点会遇到空节点）    if (root->_col == RED && root->_parent->_col == RED)    {        cout << "存在连续红色节点" << endl;        return false;    }  //计数黑结点    if (root->_col == BLACK)        count++;  //递归左右子树    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);}

复制代码

七、红黑树的删除

红黑树的删除不做讲解，有兴趣可参考：《算法导论》或者《STL 源码剖析》http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.htmlhttp://blog.csdn.net/chenhuajie123/article/details/11951777

八：红黑树与 AVL 树的比较

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(logN )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多.

九：红黑树的应用

C++ STL 库 -- map/set、mutil_map/mutil_set
Java 库
linux 内核
其他一些库

下一章我们将会将 map/set 如何通过红黑树来实现的，敬请期待吧！！

总结

红黑树是一个极其优秀的数据结构，也是面试中比较爱考的。在 liunx，c++，java 中也有很多的使用。对于我们这些将来的互联网从业者来说，是一个必须要掌握的数据结构（可以不知道具体的代码实现，但要懂红黑树是如何实现的，以及后来如何封装出 map/set 的）。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/a8af996210948d1e964337eef】。未经作者许可，禁止转载。

雪芙花

关注

还未添加个人签名 2022-04-28 加入

还未添加个人简介

发布

暂无评论

创作场景

C++ 精通之路：红黑树

红黑树

一：红黑树的概念

二：红黑树的性质

三：红黑树节点的定义

四：红黑树结构

五：红黑树的插入操作

情况一（只需要变色）：

情况二（单旋加变色）：

情况三（双旋加变色）：

插入的实现

旋转实现

六:红黑树的验证

实现代码：

七、红黑树的删除

八：红黑树与 AVL 树的比较

九：红黑树的应用

总结

雪芙花

评论