红黑树在 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）三者颜色组合，分四种情况：
立即学习“C++免费学习笔记（深入）”；
- 叔节点为红色 → 父与叔变黑，祖父变红，然后以祖父为当前节点继续向上修复
- 叔节点为黑色，且新节点是父节点的右孩子，父节点是祖父的左孩子 → 先对父节点左旋，转为下一种情形
- 叔节点为黑色，且新节点是父节点的左孩子，父节点是祖父的左孩子 → 父变黑，祖父变红，对祖父右旋
- 镜像情况（父为祖父右孩子）→ 对称左旋 + 变色
所有旋转都只改变指针指向和颜色，不改动键值；变色操作无副作用，因此修复时间复杂度是 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 的迭代器失效规则、自定义比较函数的严格弱序要求，都比红黑树内部逻辑更容易出问题。先确保用对标准容器，再考虑是否真需要替换底层。
