欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

【 C++ 红黑树】插入，旋转，情况分析

2026-11-02 分类：服务器技术 阅读(11) 评论(0)

C++ 红黑树 ： 插入，旋转，情况分析

上一篇我们用 AVL 树把平衡卡得很死：左右高度差不能超过 1。AVL 查得快，但插入删除时为了维持严格平衡，经常牵一发动全身、一连串旋转。这篇讲另一种同样常用、但没那么"较真"的平衡树——红黑树。它用颜色约束路径，允许最长路径是最短路径的 2 倍，换来旋转次数大幅减少。我们之前用的 map、set，底层就是红黑树。

目录

  • 一、红黑树是什么
  • 二、为什么有了 AVL 还要红黑树
  • 三、红黑树的五条规则
  • 四、为什么最长路径不超过最短的两倍
  • 五、节点结构
  • 六、旋转
  • 七、插入：关键看叔叔
  • 八、查找
  • 九、红黑树检查逻辑
  • 十、总结

一、红黑树是什么

红黑树是一种通过颜色来控制尽量平衡的二叉搜索树。它在每个节点里加一个存储位表示颜色，只有红、黑两种。再对"任意一条从根走到叶子的路径上节点的颜色"施加约束，就能保证：没有任何一条路径会比其他路径长出 2 倍，因此整棵树是接近平衡的——它不像 AVL 那样卡高度差，而是用颜色近似地把高度压住。

二、为什么有了 AVL 还要红黑树

可能有人会问：严格平衡的 AVL 深度更浅，查询按理更快，为什么实际工程里 map/set 都用红黑树？原因有两点。

第一，两者的查询复杂度在工程上几乎拉不开差距。红黑树只要求最长路径不超过最短路径的 2 倍。AVL 和红黑树的高度都是对数级：假设 AVL 跑到 30 层（2³⁰ 是十亿级数据），红黑树最长也就 60 层，最多多走 30 次比较。对现在的机器来说，多这 30 次的消耗微乎其微。

第二，红黑树插入、删除时的旋转次数远少于 AVL。AVL 删除时经常引发连锁旋转，一层一层往上转；红黑树变色为主、旋转为辅，大多数情况只动一两次。维护成本低，换来的综合收益反而更大。所以现在应用更广的是红黑树。

三、红黑树的五条规则

红黑树的"平衡"完全靠下面几条颜色规则约束：

  • 每个节点不是红色就是黑色；
  • 根节点是黑色；
  • 如果一个节点是红色的，它的两个孩子必须是黑色——也就是任意一条路径上不会出现连续两个红节点；
  • 对任意一个节点，从它出发到下面所有空（NULL）节点的每条路径上，包含的黑节点数量相同；
  • 《算法导论》等教材还补充：每个叶子节点（这里指的是空节点 NIL，不是真正存数据的叶子）都是黑色。

    • 注意第 5 条说的"叶子"不是我们平时说的最底下那个存数据的节点，而是遍历尽头的空指针 NIL，有的书叫它外部节点。引入 NIL 是为了把所有路径都数清楚、好统一计数；实际写代码时通常把 NIL 省略掉，知道有这个概念即可。

    四、为什么最长路径不超过最短的两倍

    把规则 3、4 放在一起推一遍，就能明白"最长路径 = 2 × 最短路径"是怎么来的。

    先定义黑高 bh（black height）：从某个节点出发走到 NIL，路上经过的黑节点个数（不含该节点本身，不同教材记法略有出入）。

    • 最短路径：一条路上全是黑节点、一个红节点都没有，长度就是 bh；
    • 最长路径：受规则 3 限制，红黑必须交替；受规则 4 限制，黑节点数量要和最短路径一样多。于是每两个黑节点之间都可以塞一个红节点，最后一个黑节点下面还能再挂一个红节点。

    这样一来，黑节点有 bh 个，红节点最多也能有 bh 个，最长路径长度就是 2·bh。所以任意路径长度满足：

    bh ≤ h ≤ 2·bh

    也就是说，红黑树任意一条路径不会比另一条长出超过一倍。

    五、节点结构

    和 AVL 一样，为了沿父链向上调整，红黑树节点也带 _parent；区别是把"平衡因子"换成了"颜色"。默认按 key/value 结构实现：

    // 枚举值表示颜色
    enum Colour
    {
    RED,
    BLACK
    };

    // 这里我们默认按key/value结构实现
    template<class K, class V>
    struct RBTreeNode
    {
    // 这里更新控制平衡也要加入parent指针
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv)
    :_kv(kv)
    , _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _col(RED)
    {}
    };

    六、旋转

    红黑树调整颜色不够时也用旋转，而且单旋的写法和 AVL 完全一样：右单旋是"左边太重向右压"，左单旋是"右边太重向左压"。直接把之前那两个单旋搬过来即可。

    //右单旋的实现
    void RotateR(Node* parent)
    {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    //这个时候要考虑subLR是不是空节点
    //按照逻辑来说，subLR的父节点要更新成parent。但是subLR如果是空节点就没这一说
    if (subLR)
    subLR->_parent = parent;

    //考虑parent还有父亲
    Node* parentParent = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (parentParent == nullptr)
    {
    _root = subL;
    subL->_parent = nullptr;
    }

    else
    {
    if (parent == parentParent->_left)
    {
    parentParent->_left = subL;
    }
    else
    {
    parentParent->_right = subL;
    }

    subL->_parent = parentParent;
    }
    }

    //左旋
    void RotateL(Node* parent)
    {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL)
    subRL->_parent = parent;

    Node* parentParent = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

    if (parentParent == nullptr)
    {
    _root = subR;
    subR->_parent = nullptr;
    }
    else
    {
    if (parent == parentParent->_left)
    {
    parentParent->_left = subR;
    }
    else
    {
    parentParent->_right = subR;
    }
    subR->_parent = parentParent;
    }
    }

    //红黑树虽然有双旋，但是我们可以调两个单旋实现，不需要再造双旋的轮子了
    //void RotateLR(Node* parent)
    //{
    // Node* subL = parent->_left;
    // Node* subLR = subL->_right;

    // RotateL(parent->_left);
    // RotateR(parent);
    //}

    //void RotateRL(Node* parent)
    //{
    // Node* subR = parent->_right;
    // Node* subRL = subR->_left;

    // RotateR(parent->_right);
    // RotateL(parent);
    //}

    红黑树真正调整时只用到左右单旋；下面插入部分也只调用 RotateR 和 RotateL。

    七、插入：关键看叔叔

    插入第一步和二叉搜索树一模一样：按 key 大小走到空位挂新节点。新节点默认染成红色——因为染黑一定会让某条路径多一个黑节点，违反规则 4；染红才有可能不破坏黑高平衡。

    挂完之后看父亲：

    • 父亲是黑色：不破坏任何规则，直接结束；
    • 父亲是红色：出现了连续红节点（违反规则 3），这时关键看叔叔节点（和父亲同层、祖父的另一个孩子）。注意：无论哪种情况，处理完都会把父亲变黑。

    设祖父为 grandfather、父亲为 parent、新节点为 cur、叔叔为 uncle。代码按"父亲在祖父左边还是右边"分两大支，每支再按叔叔颜色细分：

    bool insert(const pair<K, V>& kv)
    {

    if (_root == nullptr)
    {
    _root = new Node(kv);
    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->_right = cur;
    }
    else
    {
    parent->_left = cur;
    }

    cur->_parent = parent;

    //parent如果存在且为黑，直接在parent后面插入新增红色节点cur即可，不需其他操作
    //没有parent说明是根，上面给了解决方案
    //所以这里parent存在且为红的情况作为条件
    while (parent && parent->_col == RED)
    {
    Node* grandfather = parent->_parent;

    if (grandfather->_left == parent)
    {
    // g
    // p u
    Node* uncle = grandfather->_right;

    //uncle存在且为红，只变色然后继续向上处理
    if (uncle && uncle->_col == RED)
    {
    parent->_col = BLACK;
    uncle->_col = BLACK;
    grandfather->_col = RED;

    cur = grandfather;
    parent = cur->_parent;
    }
    else //叔叔不存在或者存在且为黑
    {
    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
    {
    // g
    // u p
    Node* uncle = grandfather->_left;
    // 叔叔存在且为红，-> 变色即可
    if (uncle && uncle->_col == RED)
    {
    parent->_col = uncle->_col = BLACK;
    grandfather->_col = RED;

    // 继续往上处理
    cur = grandfather;
    parent = cur->_parent;
    }
    else // 叔叔不存在，或者存在且为黑
    {
    // 旋转+变色
    // g
    // u p
    // c
    if (cur == parent->_right)
    {
    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：叔叔存在且为红。 父亲红、叔叔红，问题出在祖父这一层——祖父一定是黑的，它下面两个红孩子没事，但我们又加了一个红孙节点，和父亲连续红了。这时不用旋转：把父亲和叔叔都染黑、祖父染红，黑高在这一层是守恒的（原来祖父黑贡献 1，现在父叔各黑贡献 2 但祖父变红贡献 0，整体没变）。然后把 cur 上移到祖父、继续检查祖父的父亲，因为祖父变红后可能和它的父亲连续红。

    c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红

    情况分析

    情况 2：叔叔黑（或不存在），且新节点和父亲在同一条直线上（左左 / 右右）。 父亲红、叔叔黑，只变色救不了，需要旋转。以祖父为旋转点做一次单旋，把父亲提上去当这一层的新根，父亲变黑、祖父变红。这就是代码里 RotateR(grandfather) 或 RotateL(grandfather) 那两个分支。

    c为红，p为红，g为⿊，u不存在或者u存在且为⿊

    情况分析

    情况 3：叔叔黑（或不存在），但新节点和父亲形成折线（左右 / 右左）。 先以父亲为旋转点做一次单旋把折线拉直，再以祖父为旋转点做一次单旋，最后把新节点变黑、祖父变红。这就是代码里先 RotateL(parent) 再 RotateR(grandfather)（或先 RotateR(parent) 再 RotateL(grandfather)）的双旋分支。

    情况三就不画图了，没啥意思，逻辑就是这样

    情况分析

    无论哪一支，处理完都 break：旋转+变色已经让这一层恢复平衡，黑高也回到正常，不需要再往上连锁处理。循环结束后，最后兜底把整棵树根染黑，保证规则 2。

    八、查找

    查找就是普通二叉搜索树查找：比 key 小向右、比 key 大向左，相等返回。代码：

    //查找，这个很简单了，我就不说了
    Node* Find(const K& key)
    {
    Node* cur = _root;
    while (cur)
    {
    if (cur->_kv.first < key)
    {
    cur = cur->_right;
    }
    else if (cur->_kv.first > key)
    {
    cur = cur->_left;
    }
    else
    {
    return cur;
    }
    }
    return nullptr;
    }

    九、红黑树检查逻辑

    写完一棵红黑树，怎么验证它真的满足规则？这里给了 IsBalance 和递归辅助函数 Check，下面把逻辑补全。

    //检查红黑树
    bool Check(Node* root, int blackNum, const int refNum)
    {
    if (root == nullptr)
    {
    // 前序遍历走到空时，意味着一条路径走完了
    //cout << blackNum << endl;
    if (refNum != blackNum)
    {
    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)
    {
    blackNum++;
    }

    return Check(root->_left, blackNum, refNum)
    && Check(root->_right, blackNum, refNum);
    }

    bool IsBalance()
    {
    if (_root == nullptr)
    return true;

    if (_root->_col == RED)
    return false;

    // 参考值
    int refNum = 0;
    Node* cur = _root;
    while (cur)
    {
    if (cur->_col == BLACK)
    {
    ++refNum;
    }
    cur = cur->_left;
    }

    return Check(_root, 0, refNum);
    }

    IsBalance 先做两件事：

  • 空树直接返回 true；
  • 根如果是红色，违反规则 2，直接返回 false。

    • 然后算一个参考黑高 refNum：从根一直往左走到底（最左路径），一路数经过的黑节点个数。这条路径上的黑节点数就是红黑树的标准黑高——根据规则 4，其他任意路径的黑节点数都必须和它相等。

    Check 是前序递归，干三件事：

  • 走到空指针时，一条路径就走完了。把这条路径累计的黑节点数 blackNum 和参考值 refNum 比一下：不相等说明这条路径黑节点数不对，违反规则 4；相等就这条路径没问题。
  • 检查连续红节点。不直接检查"红节点的孩子是不是黑"，因为孩子有两个、还可能为空；反过来检查"当前节点是红、它父亲是不是也是红"，只要当前是红且父亲也是红，就违反规则 3。
  • 累计黑节点数：当前节点是黑色就 blackNum++，再带着这个计数递归检查左、右子树。左右两条路径都通过，这棵树才算红黑树。

    • 十、写个测试跑一下

    下面这段 main 是我们自己加的驱动代码（上面节点、旋转、插入、检查的实现都不动）：往树里插一串 key，中序遍历看是否有序，再调 IsBalance() 验证是否真的是一棵合格的红黑树。

    // 中序遍历，验证搜索顺序
    template<class K, class V>
    void InOrder(typename RBTree<K, V>::Node* root)
    {
    if (root == nullptr)
    return;
    InOrder<K, V>(root->_left);
    cout << root->_kv.first << " ";
    InOrder<K, V>(root->_right);
    }

    int main()
    {
    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    RBTree<int, int> t;
    for (auto e : a)
    {
    t.insert({ e, e });
    }

    // 中序应该是升序：3 7 9 11 14 15 16 18 26
    InOrder<int, int>(t.GetRoot());

    // 通过则打印"是红黑树"，否则会在 Check() 里打印具体哪条路径不对
    if (t.IsBalance())
    cout << endl << "是红黑树" << endl;
    else
    cout << endl << "不是红黑树" << endl;

    return 0;
    }

    用这组数据是为了刻意触发不同的旋转分支：16、3、7 会触发叔叔红变色上推，11、9 会触发左右双旋，14、15 又会触发右左双旋，一次跑遍几种典型情况。IsBalance() 通过，就说明插入过程中颜色和旋转都处理对了。

    因为 _root 是 private，跑上面的 main 前需要在类的 public 区补一个取根接口：

    Node* GetRoot() { return _root; }

    十一、总结

  • 红黑树用颜色近似平衡：允许最长路径是最短路径 2 倍，不像 AVL 卡高度差，查询仍是 O(logN)；
  • 五条规则：非红即黑、根黑、红父必有黑孩、任意路径黑节点数相同、NIL 黑；
  • 黑高 bh：最短路径长 bh、最长路径最多 2bh，所以 bh ≤ h ≤ 2bh；
  • 插入关键看叔叔：新节点染红，父黑直接结束；父红时，叔叔红就变色上推，叔叔黑/不存在就单旋或双旋+变色，最后把根染黑；
  • 检查：先确认根黑、取最左路径黑节点数为参考值，再前序递归——到空比黑节点数、遇到红节点查父亲防连续红。

    • 红黑树删除我也先不讲了，大家可以去看看《算法导论》这本书，我有时间再发文吧，这个计划无限期延长。 注意：本文是对红黑树的模拟实现，实现效果也已经达成，和库内源码的写法不一致，库中给红黑树一个哨兵位节点，类似list的设计，但实在复杂，本文舍弃了源码的实现逻辑。有哨兵位和没哨兵位都各有优劣。

    赞(0)
    未经允许不得转载：171主机测评 » 【 C++ 红黑树】插入，旋转，情况分析
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(64587)#python(21518)#开发语言(17905)#java(16474)#运维(16216)#linux(15689)#大数据(15361)#服务器(13698)#算法(12337)#前端(11705)#ai(10345)#网络(9939)#数据库(9550)#c++(8698)#学习(7191)#课程设计(7036)#机器学习(7024)#区块链(6066)#后端(5565)#OpenClaw(5419)#spring boot(5319)#深度学习(5292)#c语言(4565)#安全(4519)#毕业设计(4402)#数据结构(4345)#架构(4191)#docker(4125)#javascript(3992)#大模型(3940)

    热门文章

    最新文章

    归档

    分类