17370845950

应直接使用std::map或std::set，其底层为经充分测试的红黑树；手写仅适用于实现STL、算法题或学习编译器底层；需严格满足五条性质以维持O(log n)性能，修复插入仅需变色与旋转。

红黑树在 C++ 标准库中早已封装好了，别自己手写

除非你在实现 STL 容器、做算法题或学习编译器底层（比如 libstdc++ 的 std::map 实现），否则直接用 std::map 或 std::set。它们底层就是红黑树（GCC/libstdc++ 和 MSVC 都是），接口稳定、经过充分测试，且支持迭代器、异常安全和 allocator 自定义。

红黑树的五条基本性质必须同时满足

这些不是“建议”，而是维持 O(log n) 查找/插入/删除的前提。任意节点违反都会导致树退化：

• 每个节点是红色或黑色
• 根节点是黑色
• 所有叶子节点（NIL 节点，即空指针）是黑色
• 如果一个节点是红色，则它的两个子节点都是黑色（不能连续红）
• 从任一节点到其每个叶子的所有路径上，包含相同数目的黑色节点（黑高一致）

注意：标准实现中 NIL 不是 nullptr，而是一个共享的静态黑色哨兵节点（如 libstdc++ 的 _M_header），否则判断叶子和空指针逻辑容易出错。

插入后只可能破坏性质 2、4、5，修复靠变色 + 旋转

新节点默认染成红色，这样不会影响黑高（性质 5），但可能违反性质 4（父节点也是红色）。修复过程只依赖祖父节点（grandparent）、父节点（parent）、叔节点（uncle）三者颜色组合，分四种情况：

• 叔节点为红色 → 父与叔变黑，祖父变红，然后以祖父为当前节点继续向上修

  

  复
• 叔节点为黑色，且新节点是父节点的右孩子，父节点是祖父的左孩子 → 先对父节点左旋，转为下一种情形
• 叔节点为黑色，且新节点是父节点的左孩子，父节点是祖父的左孩子 → 父变黑，祖父变红，对祖父右旋
• 镜像情况（父为祖父右孩子）→ 对称左旋 + 变色

所有旋转都只改变指针指向和颜色，不改动键值；变色操作无副作用，因此修复时间复杂度是 O(1) 均摊（因为最多上溯 log n 层，但每层最多一次旋转）。

手写红黑树时最容易崩在指针管理和哨兵节点上

常见崩溃点不是逻辑错，而是野指针或误判空节点：

• 把 nullptr 当作叶子节点处理，结果访问 nullptr->color 段错误
• 旋转后忘记更新父指针（尤其根节点变化时没重设 root）
• 插入后忘记把根强制染黑（性质 2），导致后续查找异常
• 拷贝构造/赋值未深拷贝节点，析构时 double-free

真正可靠的实现会定义一个全局 static const node_type* const _s_nil 作为黑色哨兵，并让所有叶节点的孩子都指向它；所有指针比较（如 node->left == _s_nil）都基于此，而非 nullptr。

struct rb_node {
    int key;
    bool color; // true for red, false for black
    rb_node* left;
    rb_node* right;
    rb_node* parent;
};
// 正确的叶子判断（不是 nullptr！）
bool is_leaf(const rb_node* x) {
return x == _s_nil;
}

实际工程里，连 std::map 的迭代器失效规则、自定义比较函数的严格弱序要求，都比红黑树内部逻辑更容易出问题。先确保用对标准容器，再考虑是否真需要替换底层。