红黑树节点必须包含颜色字段和父指针；旋转需更新四元组父子关系；插入修复分四类case处理；删除复杂，建议优先使用std::map/set。
红黑树节点定义必须包含颜色字段和三叉指针
标准二叉搜索树节点不满足红黑树约束，RBNode 必须显式存储颜色（通常用 bool is_red 或枚举），且需保留父指针——这是实现自底向上修复旋转的前提。子节点指针命名建议统一为 left、right，避免用 lchild 等非主流写法导致后续逻辑混乱。
常见错误：漏掉 parent 指针，导致插入后无法回溯调整；或把颜色存在 int color 里却未定义 RED=0/BLACK=1，引发条件判断歧义。
struct RBNode {
int key;
bool is_red; // true 表示红色，false 表示黑色
RBNode* left;
RBNode* right;
RBNode* parent;
RBNode(int k) : key(k), is_red(true), left(nullptr), right(nullptr), parent(nullptr) {}};
左旋与右旋函数必须更新父子关系四元组
旋转不是单纯交换指针，而是重连 old_root、new_root、subtree 和 parent 四者之间的 left/right/parent 字段。漏掉任一链接（尤其是 new_root->parent 或 old_root->parent）都会导致树断裂或内存泄漏。
立即学习“C++免费学习笔记（深入）”；
-
left_rotate(x)：以x为轴，将x->right提升为新根，x成为其左子 -
right_rotate(y)：以y为轴，将y->left提升为新根，y成为其右子 - 若
x是根节点，旋转后需同步更新树的root指针
void left_rotate(RBNode*& root, RBNode* x) {
RBNode* y = x->right;
x->right = y->left;
if (y->left != nullptr) y->left->parent = x;
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;}
插入后修复需分四类 case 处理，核心是变色+旋转组合
插入新节点默认设为红色，仅可能违反「红节点不能有红子」和「根必须为黑」两条规则。修复函数 insert_fixup 从新节点开始向上迭代，关键在于识别当前节点 z、父节点 z->parent、叔节点 uncle 的颜色组合：
- Case 1：叔节点为红 → 父与叔变黑，祖父变红，
z = z->parent->parent继续向上检查 - Case 2：叔为黑且
z是右子 → 先left_rotate(z->parent)，转为 Case 3 - Case 3：叔为黑且
z是左子 →right_rotate(z->parent->parent)，再将父变黑、祖父变红 - 注意：所有旋转后必须立即修正颜色，且 Case 1 中若祖父为根，则最后一步需强制置黑
容易被忽略的点：uncle 判空必须用 uncle == nullptr 而非 !uncle（避免未初始化野指针误判）；修复循环终止条件是 z->parent == nullptr || !z->parent->is_red。
删除操作比插入复杂得多，建议优先复用 std::map/set
红黑树删除涉及「找后继→替换→修复双黑」三阶段，修复逻辑包含至少 6 种 case，其中「双黑传播」需同时处理兄弟颜色、兄弟子节点颜色、兄弟是否为根等交叉条件。手动实现极易在边界场景（如删根、删唯一子树、连续黑节点）出错。
除非教学目的或嵌入式环境严格限制 STL，否则直接使用 std::map 或 std::set 更可靠——它们底层就是红黑树，接口稳定，且经过数十年编译器厂商验证。自己造轮子时，务必用大量随机序列 + valgrind 检查内存泄漏和非法访问。
