【数据结构】 红黑树

一、红黑树是什么

红黑树 是一棵自平衡的二叉排序树 BST相比 AVL（严格高度平衡），红黑树是弱平衡；不严格限制左右高度差，只通过结点颜色 + 5 条规则维持大致平衡。
核心目的：减少旋转次数，插入删除更快，工业级常用（C++map、Java TreeMap 底层）

二、结点结构

每个结点额外保存 1 种颜色：
红色
黑色
默认：叶子空结点 (NIL) 统一为黑色

三、红黑树五大铁律

每个结点只能是红色 / 黑色
根结点一定是黑色
所有叶子结点（NIL 空叶） 都是黑色
红色结点的两个孩子，必须都是黑色
结论：不能出现连续两个红色结点
从任意结点出发，到其所有叶子的简单路径，包含的黑色结点数量相同
结论：黑色高度统一
关键推论
最长路径 ≤ 最短路径 × 2
整树高度稳定：O(logn)
不会出现极端斜树

四、核心概念

黑高
某结点到叶子路径上黑色结点的总数，整树黑高一致。
弱平衡
AVL：左右高度差≤1
红黑树：允许高度差很大，但靠「红色隔离 + 黑高相等」控上限

五、插入规则

新结点默认先染红色
若染黑色：直接破坏性质 5（黑高改变），全局大量调整
染红色：只可能违反「不能连续红」，修复代价小
插入后违规只可能：父结点也是红色
修复手段二选一：
变色（简单优先）
左旋 / 右旋（结构调整）
六、三大修复场景（背诵版）
设：
z：当前违规红点
p：父结点（红）
g：祖父结点（必黑）
u：叔叔结点
场景 1：叔叔 u 为红色
方案：单纯变色
父 p 变黑
叔叔 u 变黑
祖父 g 变红
把 g 当作新违规点，向上递归检查
场景 2：叔叔 u 为黑色，z 是 p 的右孩子（RR 类）
方案：单次左旋旋转后转为场景 3
场景 3：叔叔 u 为黑色，z 是 p 的左孩子（LL 类）
方案：右旋 + 变色
对 g 右旋
p 变黑、g 变红
直接修复完毕，无需向上回溯
LR / RL 型：先小旋转，再大旋转 + 改色，和 AVL 逻辑相似

七、删除

删除比插入复杂，会引发黑色高度不足修复核心：
借兄弟结点黑色
兄弟变色、旋转补黑
最坏向上逐层修正

八、红黑树 与 AVL 树 深度对比

总结一句话
频繁查询 → 选 AVL
频繁插入、删除、修改 → 选 红黑树

九、考试超级易错点

错误：红黑树没有高度限制
正确：最长路径不超过最短 2 倍，有严格上界
错误：可以连续红
正确：严禁连续红色结点
忽略：NIL 叶子是黑色
正确：所有空叶子统一黑色，是性质 5 的基础
根结点颜色随便
正确：根必须黑色
新结点为什么染红？
→ 避免破坏黑高，减少全局调整

十、极简背诵口诀

根黑叶黑，红子必黑；
任一路径，黑数相等；
新插染红，遇红修复；
叔红变色，叔黑旋转；
AVL 高平衡旋转多，红黑弱平衡改色多。