一轮
AVL 树：看高度差，失衡就旋转。
红黑树：看颜色冲突，优先变色，必要时旋转。
一、AVL 树调整策略
AVL 树要求：
任意节点的左右子树高度差不能超过 1通常定义平衡因子：
BF = 左子树高度 - 右子树高度所以合法范围是：
BF ∈ {-1, 0, 1}如果某个节点的 BF 变成：
BF = 2 或 BF = -2就说明该节点失衡，需要旋转。
1. AVL 插入后的调整
插入新节点后，从新节点一路向上回溯，找到第一个失衡节点。
设这个失衡节点为 z，它的较高子节点为 y，新插入节点位于 y 的某一侧。
AVL 插入失衡只有四种情况：
情况 1：LL 型
也叫：
左左型含义：
新节点插入到了 z 的左子树的左边结构大概是：
z
/
y
/
x此时：
BF(z) = 2
BF(y) >= 0调整方法：
对 z 右旋旋转前：
z
/
y
/
x右旋后：
y
/ \
x z情况 2：RR 型
也叫：
右右型含义：
新节点插入到了 z 的右子树的右边结构大概是：
z
\
y
\
x此时：
BF(z) = -2
BF(y) <= 0调整方法：
对 z 左旋旋转前：
z
\
y
\
x左旋后：
y
/ \
z x情况 3：LR 型
也叫：
左右型含义：
新节点插入到了 z 的左子树的右边结构大概是：
z
/
y
\
x此时：
BF(z) = 2
BF(y) = -1调整方法是两步：
先对 y 左旋
再对 z 右旋旋转过程：
z
/
y
\
x先对 y 左旋：
z
/
x
/
y再对 z 右旋：
x
/ \
y z情况 4：RL 型
也叫：
右左型含义：
新节点插入到了 z 的右子树的左边结构大概是：
z
\
y
/
x此时：
BF(z) = -2
BF(y) = 1调整方法是两步：
先对 y 右旋
再对 z 左旋旋转过程：
z
\
y
/
x先对 y 右旋：
z
\
x
\
y再对 z 左旋：
x
/ \
z y2. AVL 插入调整速查表
| 失衡类型 | 判断方式 | 结构方向 | 调整方法 |
|---|---|---|---|
| LL | BF(z)=2 且新节点在左孩子的左边 | 左左 | 对 z 右旋 |
| RR | BF(z)=-2 且新节点在右孩子的右边 | 右右 | 对 z 左旋 |
| LR | BF(z)=2 且新节点在左孩子的右边 | 左右 | 先左旋左孩子，再右旋 z |
| RL | BF(z)=-2 且新节点在右孩子的左边 | 右左 | 先右旋右孩子，再左旋 z |
3. AVL 删除后的调整
AVL 删除比插入稍微麻烦，因为删除一个节点后，可能导致多个祖先节点高度变化。
删除后仍然从被删除位置向上回溯，检查每个祖先节点的平衡因子。
核心判断仍然是四类：
删除后左边太高
也就是：
BF(z) = 2说明 z 的左子树比右子树高太多。
设 y = z.left。
如果
BF(y) >= 0
这是 LL 型。
调整：
对 z 右旋如果
BF(y) < 0
这是 LR 型。
调整：
先对 y 左旋
再对 z 右旋删除后右边太高
也就是：
BF(z) = -2说明 z 的右子树比左子树高太多。
设 y = z.right。
如果
BF(y) <= 0
这是 RR 型。
调整：
对 z 左旋如果
BF(y) > 0
这是 RL 型。
调整：
先对 y 右旋
再对 z 左旋4. AVL 删除调整速查表
失衡节点 z | 子节点 y 的 BF | 类型 | 调整方法 |
|---|---|---|---|
BF(z)=2 | BF(y)>=0 | LL | 对 z 右旋 |
BF(z)=2 | BF(y)<0 | LR | 先对 y 左旋，再对 z 右旋 |
BF(z)=-2 | BF(y)<=0 | RR | 对 z 左旋 |
BF(z)=-2 | BF(y)>0 | RL | 先对 y 右旋，再对 z 左旋 |
插入和删除的旋转类型是一样的。区别是：
插入：通常调整第一个失衡节点后就结束
删除：调整后可能还要继续向上检查二、红黑树调整策略
红黑树的核心规则是：
- 每个节点要么红，要么黑；
- 根节点必须是黑色；
- 所有 NIL 空叶子视为黑色；
- 红节点不能有红孩子；
- 从任意节点到其所有后代 NIL 叶子的路径上，黑节点数量相同。
红黑树不像 AVL 那样严格控制高度差，而是通过颜色和旋转保证大致平衡。
1. 红黑树插入后的调整
红黑树插入规则：
新插入的节点默认染成红色原因是：插入红节点不会立刻改变黑高，比较容易修复。
插入后主要可能破坏这一条规则：
红节点不能有红孩子也就是出现：
父节点是红色，新节点也是红色设：
N = 当前节点，也就是新插入节点
P = 父节点
G = 祖父节点
U = 叔叔节点情况 0：父节点是黑色
如果：
P 是黑色那就没有违反红黑树性质。
不需要调整。
情况 1：父节点红，叔叔节点红
结构大概是：
G(B)
/ \
P(R) U(R)
/
N(R)或者对称情况。
问题：
P 和 N 连续红色修复方法：
P 染黑
U 染黑
G 染红然后把 G 当作新的当前节点，继续向上检查。
示意：
G(B)
/ \
P(R) U(R)
/
N(R)变成：
G(R)
/ \
P(B) U(B)
/
N(R)如果 G 是根节点，最后还要把根染黑。
记忆：
父叔都红：只变色，往上递归情况 2：父节点红，叔叔节点黑，LL 型
结构：
G(B)
/
P(R)
/
N(R)也就是：
当前节点在祖父节点的左子树的左边修复方法：
对 G 右旋
P 染黑
G 染红旋转前：
G(B)
/
P(R)
/
N(R)旋转后：
P(B)
/ \
N(R) G(R)记忆：
左左：右旋祖父情况 3：父节点红，叔叔节点黑，RR 型
结构：
G(B)
\
P(R)
\
N(R)也就是：
当前节点在祖父节点的右子树的右边修复方法：
对 G 左旋
P 染黑
G 染红旋转前：
G(B)
\
P(R)
\
N(R)旋转后：
P(B)
/ \
G(R) N(R)记忆：
右右：左旋祖父情况 4：父节点红，叔叔节点黑，LR 型
结构：
G(B)
/
P(R)
\
N(R)也就是：
当前节点在祖父节点的左子树的右边修复方法分两步：
先对 P 左旋
再按 LL 型处理过程：
G(B)
/
P(R)
\
N(R)先对 P 左旋：
G(B)
/
N(R)
/
P(R)这就变成了 LL 型。
然后对 G 右旋，并调整颜色：
N(B)
/ \
P(R) G(R)记忆：
左右：先左旋父，再右旋祖父情况 5：父节点红，叔叔节点黑，RL 型
结构：
G(B)
\
P(R)
/
N(R)也就是：
当前节点在祖父节点的右子树的左边修复方法分两步：
先对 P 右旋
再按 RR 型处理过程：
G(B)
\
P(R)
/
N(R)先对 P 右旋：
G(B)
\
N(R)
\
P(R)这就变成了 RR 型。
然后对 G 左旋，并调整颜色：
N(B)
/ \
G(R) P(R)记忆：
右左：先右旋父，再左旋祖父2. 红黑树插入调整速查表
| 父节点 | 叔叔节点 | 类型 | 调整策略 |
|---|---|---|---|
| 黑色 | 任意 | 无冲突 | 不调整 |
| 红色 | 红色 | 变色型 | 父、叔染黑，祖父染红，然后继续向上检查 |
| 红色 | 黑色 | LL | 祖父右旋，父染黑，祖父染红 |
| 红色 | 黑色 | RR | 祖父左旋，父染黑，祖父染红 |
| 红色 | 黑色 | LR | 先父左旋，转成 LL，再祖父右旋 |
| 红色 | 黑色 | RL | 先父右旋，转成 RR，再祖父左旋 |
插入修复最后一定要做：
根节点染黑3. 红黑树删除后的调整
红黑树删除比插入复杂，关键是看被删除节点的颜色。
删除时一般先按二叉搜索树删除：
- 如果删除节点有两个孩子，通常用它的中序后继或前驱替代；
- 最终真正被删除的节点，通常会变成一个最多只有一个孩子的节点。
重点看：
真正被删除的节点是什么颜色？情况 1：删除的是红色节点
如果真正删除的是红节点，通常不需要调整。
原因：
删除红节点不会改变任何路径上的黑节点数量直接删除即可。
情况 2：删除的是黑色节点，替代节点是红色
如果删除的是黑节点，但它的替代节点是红色：
删除黑节点后，路径少了一个黑色修复方法：
把替代节点染黑这样黑高恢复。
情况 3：删除的是黑色节点，替代节点也是黑色或 NIL
这是最麻烦的情况。
可以理解为出现了一个：
双重黑色 double black意思是：某条路径上少了一个黑节点，需要向上修复。
设：
X = 当前双重黑节点
P = X 的父节点
S = X 的兄弟节点还要看兄弟节点的两个孩子。
为了方便描述，先假设 X 是父节点 P 的左孩子：
P
/ \
X S
/ \
SL SR其中：
S = sibling，兄弟节点
SL = 兄弟的左孩子，近侄子
SR = 兄弟的右孩子，远侄子如果 X 是右孩子，所有左右情况对称。
删除修复情况 3.1：兄弟节点是红色
结构：
P(B)
/ \
X S(R)
/ \
SL(B) SR(B)当兄弟是红色时，说明父节点一定是黑色，兄弟的孩子也一定是黑色。
修复方法：
S 染黑
P 染红
对 P 左旋旋转后，原来的红兄弟变成新的父节点。
这个操作的目的不是直接结束，而是把情况转换成：
兄弟节点是黑色方便继续处理。
记忆：
兄弟红：先旋转换兄弟删除修复情况 3.2：兄弟黑，兄弟的两个孩子都黑
结构：
P
/ \
X S(B)
/ \
SL(B) SR(B)修复方法：
S 染红含义是：把兄弟这边也减少一个黑色，使两边黑高重新一致。
但是这样会让父节点 P 所在路径少一个黑色，所以：
- 如果
P是红色，把P染黑，修复结束； - 如果
P是黑色，把P当成新的双重黑节点，继续向上修复。
记忆：
兄黑侄黑：兄弟染红，问题上移删除修复情况 3.3：兄弟黑，近侄子红，远侄子黑
对于 X 是左孩子的情况：
P
/ \
X S(B)
/ \
SL(R) SR(B)这里 SL 是近侄子，SR 是远侄子。
修复方法：
SL 染黑
S 染红
对 S 右旋这样会转换成情况 3.4：远侄子红。
记忆：
近红远黑：先旋兄弟，转成远红删除修复情况 3.4：兄弟黑，远侄子红
对于 X 是左孩子的情况：
P
/ \
X S(B)
/ \
SL SR(R)修复方法：
S 染成 P 的颜色
P 染黑
SR 染黑
对 P 左旋修复结束。
记忆：
远侄子红：旋父节点，修复结束4. 红黑树删除调整速查表
假设 X 是左孩子，S 是右兄弟：
兄弟 S | 兄弟孩子情况 | 调整策略 |
|---|---|---|
| 红色 | 必有黑孩子 | S 染黑，P 染红，对 P 左旋 |
| 黑色 | 两个孩子都黑 | S 染红，问题上移到 P |
| 黑色 | 近侄子红，远侄子黑 | 近侄子染黑，S 染红，对 S 右旋 |
| 黑色 | 远侄子红 | S 染成 P 的颜色，P 染黑，远侄子染黑，对 P 左旋 |
如果 X 是右孩子，就把表里的左右全部反过来：
兄弟 S | 兄弟孩子情况 | 调整策略 |
|---|---|---|
| 红色 | 必有黑孩子 | S 染黑，P 染红，对 P 右旋 |
| 黑色 | 两个孩子都黑 | S 染红，问题上移到 P |
| 黑色 | 近侄子红，远侄子黑 | 近侄子染黑，S 染红，对 S 左旋 |
| 黑色 | 远侄子红 | S 染成 P 的颜色，P 染黑，远侄子染黑，对 P 右旋 |
三、AVL 和红黑树调整策略对比
| 对比点 | AVL 树 | 红黑树 |
|---|---|---|
| 维护目标 | 严格高度平衡 | 近似平衡 |
| 判断依据 | 平衡因子 BF | 节点颜色、黑高 |
| 插入后主要问题 | 某个节点高度差超过 1 | 出现红红冲突 |
| 删除后主要问题 | 高度减少导致祖先失衡 | 黑高减少导致双重黑 |
| 常见调整 | 旋转为主 | 变色为主，旋转辅助 |
| 插入旋转次数 | 最多一次单旋或双旋 | 最多两次旋转 |
| 删除调整 | 可能一路向上调整 | 可能一路向上调整 |
| 查询效率 | 更稳定，树更矮 | 略松，但调整成本低 |
| 常见应用 | 读多写少、对查询性能敏感 | 写入删除较多、工程实现常见 |
四、最实用的记忆方法
AVL 树记忆
AVL 只看方向：
LL：右旋
RR：左旋
LR：先左旋，再右旋
RL：先右旋，再左旋可以记成：
外侧插入：单旋
内侧插入：双旋所谓外侧：
LL、RR所谓内侧：
LR、RL红黑树插入记忆
红黑树插入时，先看父节点：
父黑：结束
父红：看叔叔然后：
叔叔红：变色，上移
叔叔黑：旋转 + 变色方向判断和 AVL 类似：
LL：右旋祖父
RR：左旋祖父
LR：先左旋父，再右旋祖父
RL：先右旋父，再左旋祖父红黑树删除记忆
红黑树删除时，先看真正删除的节点颜色：
删红：直接删
删黑 + 替代红：替代节点染黑
删黑 + 替代黑：处理双重黑双重黑时看兄弟：
兄弟红：旋转变成兄弟黑
兄弟黑且侄子全黑：兄弟染红，问题上移
兄弟黑且近侄红：先旋兄弟
兄弟黑且远侄红：旋父节点，修复结束五、一张总表
| 树 | 操作 | 触发问题 | 判断关键 | 调整方式 |
|---|---|---|---|---|
| AVL | 插入 | 高度差超过 1 | LL/RR/LR/RL | 单旋或双旋 |
| AVL | 删除 | 高度差超过 1 | BF 和子节点 BF | 单旋或双旋，可能继续向上 |
| 红黑树 | 插入 | 红红冲突 | 父节点、叔叔节点颜色 | 叔红变色，叔黑旋转 |
| 红黑树 | 删除 | 黑高减少 | 兄弟和侄子颜色 | 变色、旋转、双重黑上移 |
最核心的区别可以压缩成一句话：
AVL 树通过“高度差”判断是否旋转；
红黑树通过“颜色关系”判断是变色还是旋转。