写红黑树关键在于严格维护五条性质，每次插入/删除后必须显式恢复；漏一条会导致erase死循环或树高异常，核心是旋转更新parent指针、修复前判空、颜色操作精准、异常安全保证。
红黑树不是靠“教程结构”写出来的，是靠五个不变量硬扛出来的
写一个能用的红黑树，关键不在画结构图或背插入流程，而在每次插入/删除后，**必须显式恢复那五条红黑性质**。漏一条，find可能不崩，但erase大概率死循环，或者insert后树高突然跳变——这不是bug，是性质坍塌。
实操建议：
- 先写好
Node结构：至少含color（bool或枚举）、left、right、parent；空节点用nullptr，别搞哨兵节点——初学者加哨兵反而掩盖指针错误 - 把五条性质写成注释贴在代码顶部：
root is black、red node's children are black、all paths from node to leaves have same black count等，每次改完立刻对照检查 - 旋转函数（
rotate_left、rotate_right）必须返回新子树根，且要同步更新parent指针；常见错误是只改了left/right，忘了new_root->parent = old_parent
插入后修复：90%的崩溃来自“忘掉祖父节点的颜色判断”
标准插入后修复分三种情况（LL/LR/RR/RL归为两类），但真正卡住人的，是进入修复前没确认grandparent是否存在，以及它是不是红色——如果grandparent == nullptr或它是黑色，直接return，不该进任何case。
常见错误现象：
立即学习“C++免费学习笔记（深入）”；
-
Segmentation fault在if (grandparent->color == RED)这行——因为grandparent是nullptr - 插入后树看起来平衡，但再插一个就
double free——本质是某次旋转中parent指针没重置，导致两个节点同时指向同一子树
实操建议：
- 修复函数开头强制检查：
if (!grandparent || grandparent->color == BLACK) return; - 所有涉及
uncle的分支，先判uncle != nullptr，再取uncle->color；别信“uncle一定存在” - 颜色翻转（recolor）时，只动
parent、uncle、grandparent三者；别顺手把current也改了——它此时是红色，改完就违反“红节点孩子必黑”
删除后修复：比插入多一层抽象，核心是“黑高补偿”
删除难点不在找后继，而在被删节点deleted的替代节点replacement若为黑色，会导致以它为根的子树“黑高-1”。修复目标不是把颜色填回去，而是通过旋转+ recolor，让整棵树各路径黑节点数重新一致。
使用场景：
- 调用
erase(key)后程序卡住或返回错误迭代器——大概率fix_double_black没处理replacement == nullptr的情况（即删的是叶子） - 删完再查，有些key搜不到——说明某次旋转后
parent没更新，导致子树脱离主干
实操建议：
- 删除函数末尾统一调用
fix_double_black(replacement)，哪怕replacement是nullptr；该函数第一行就得处理if (!node) { node = parent; }，否则空指针解引用 - 修复中的四种case（
node是双重黑，sibling颜色+子节点颜色组合）必须覆盖全；漏掉sibling为黑但两个孩子都黑的情况，就会无限循环 - 旋转后务必重置
node的父指针，例如rotate_left(parent)后，node->parent仍是原parent，但parent已不是它的父了——得手动设node->parent = new_parent
C++实现里最容易被忽略的：移动语义和异常安全
标准库std::map能安全抛异常，是因为它所有操作都满足强异常保证；你自己写的红黑树如果支持T含非noexcept构造/赋值，insert中途抛异常，就可能留下半残树——比如新节点已链入，但颜色没设，或旋转一半就停了。
性能与兼容性影响：
- 用
std::move传value进insert，但别在节点构造里直接std::move——万一T移动构造抛异常，节点内存已分配却未初始化 - 所有修改指针的操作（旋转、重连）必须放在
try块外；真正可能抛异常的只有new Node(std::move(value))这一句，其余都是纯指针操作，不会抛 - 别为了省事把
Node做成std::unique_ptr——它会干扰parent指针维护，且增加间接访问开销；裸指针+手动delete更可控
复杂点从来不在旋转逻辑本身，而在于你是否记得：每改一个->left，就得同步改对应子节点的->parent；每动一次颜色，就得确认没破坏任意一条性质；每次抛异常，树必须回到插入前状态。
