红黑树插入一个节点后如何调整（变色与旋转）？

简化版

新插入的节点总是染成红色（这样最不容易破坏「黑高相同」的性质 5）。如果它的父节点是黑色，什么都不用做；如果父节点也是红色（违反「红不相邻」），就看叔叔节点的颜色分情况修复：叔叔是红——父、叔变黑，祖父变红，再把祖父当作新插入点向上递归；叔叔是黑——通过旋转 + 变色把这一处的双红消除。最后保证根是黑色。

详细版

新节点 N 染红后，只有「父节点 P 也是红色」时才需要调整（否则合法）。设祖父为 G、叔叔为 U，分三类：

情况	条件	处理
情况 1	N 是根	直接把 N 染黑，结束
情况 2	父 P 是黑	无需调整（没破坏任何性质）
情况 3	父红、叔红	P 和 U 变黑、G 变红，然后把 G 当作新的 N 向上递归处理
情况 4	父红、叔黑，且 N、P 同侧（LL/RR）	旋转 G（LL 右旋 / RR 左旋）+ 变色（P 变黑、G 变红）
情况 5	父红、叔黑，且 N、P 异侧（LR/RL）	先旋转 P 转成情况 4，再按情况 4 处理

核心：叔叔红就「变色 + 上移」，叔叔黑就「旋转 + 变色」定点解决。

完整版教学

一、为什么新节点染红

插入必然要维持红黑性质。如果新节点染黑，它所在的那条路径就凭空多了一个黑节点，立刻破坏「性质 5：黑高相同」，而黑高的修复很麻烦。如果染红，则不影响任何路径的黑节点数（性质 5 天然保持），唯一可能违反的是「性质 4：红不相邻」——仅当父节点恰好也是红色时。所以染红把可能的破坏限制在最小、最好修复的范围，这是设计上的巧思。

二、情况 3（叔叔红）：变色上移

当父 P 和叔 U 都是红色时，祖父 G 一定是黑色（否则原树就违规了）。修复方法：把 P、U 都染黑，把 G 染红。

这样 N 的父亲 P 变黑了，双红消除。
G 变红后，经过 G 的每条路径黑节点数不变（G 从黑变红 −1，但它的两个孩子 P、U 从红变黑 +1，抵消），性质 5 保持。
但 G 变红后，可能和 G 的父亲又构成双红。所以把 G 当作新的「插入节点」，向上递归同样的流程。这就是为什么叔叔红时问题会「向上传播」，最坏一路传到根（根再染黑收尾）。

三、情况 4、5（叔叔黑）：旋转定点解决

当叔叔 U 是黑色（或是 NIL 空节点）时，不能靠变色上移，得靠旋转把双红这一处「压平」。

情况 5（LR/RL 拐弯）：N 和 P 一个偏左一个偏右（比如 P 是 G 的左孩子、N 是 P 的右孩子）。先对 P 旋转，把它转成 N 和 P 同侧的「直线」形状——变成情况 4。
情况 4（LL/RR 直线）：N、P、G 在一条斜线上。对 G 旋转（LL 型右旋 G、RR 型左旋 G），并把 P 染黑、G 染红。旋转后 P 上位当这棵子树的根且为黑色，双红消除，且这棵子树黑高不变，不再向上传播——所以叔叔黑的情况一次旋转搞定。

记忆：叔叔红 → 变色 + 递归上移；叔叔黑 → 旋转 + 变色、就地结束。

四、和 AVL 旋转的异同

红黑树用的左旋/右旋和 AVL 完全一样（保持有序性、调整结构）。不同的是红黑树是颜色 + 旋转双管齐下，且插入最多只需 2 次旋转（情况 5 一次把拐弯掰直 + 情况 4 一次），比 AVL 更节省旋转。变色虽然可能一路上移，但变色是 O(1) 操作，比旋转廉价。

五、复杂度

时间 O(log n)：BST 插入下降 O(log n)，向上修复最多 O(log n) 次变色。
旋转次数：最多 2 次（这是红黑树相对 AVL 的优势之一）。
变色可能沿路径上移 O(log n) 次，但都是 O(1) 的染色。

六、常见误区与追问

考点	正确口径
新节点染红	不立即增加黑高
叔叔红	父叔变黑、祖父变红，问题上移
叔叔黑	通过旋转和变色消除红红冲突

insert red node
while parent is red:
  if uncle is red: recolor and move up
  else: rotate to make outer case, then recolor

红黑树插入修复的主线是处理“父红子红”的连续红节点冲突。

误区：新插入节点应该染黑。 染黑会直接增加某条路径黑高，更难修复；染红通常只可能造成红红冲突。
误区：叔叔红时要旋转。 叔叔红时主要靠变色把冲突上移，叔叔黑时才需要旋转定点修复。
误区：旋转后不用重新染色。 旋转只改变结构，还必须通过变色恢复红黑性质。
追问：LR/RL 插入如何处理？ 先对父节点做一次旋转转成 LL/RR 外侧情况，再对祖父旋转。
追问：根节点最后为什么要染黑？ 红黑树性质要求根为黑；修复过程中根可能被染红，最后统一改黑。
追问：插入复杂度是多少？ 查找插入位置 O(log n)，修复最多沿祖先向上，整体 O(log n)。

七、加强记忆

红黑树插入：新节点染红（最不破坏黑高）。父黑则完事；父红看叔叔：叔红 → 父叔变黑、祖父变红、祖父当新节点向上递归（可能传到根，根最后染黑）；叔黑 → 旋转 + 变色就地解决（LR/RL 先旋父掰直成 LL/RR，再旋祖父 + 父黑祖父红）。口诀「叔红变色上移、叔黑旋转定点」。插入最多 2 次旋转，O(log n)。

简化版

详细版