什么是左倾红黑树（LLRB）？它和普通红黑树有什么区别？

简化版

左倾红黑树是红黑树的一种简化变体，要求红链接尽量向左倾斜，用红链接表示 2-3 树中的 3-node。它把插入修复归纳成左旋、右旋、颜色翻转三类操作，代码比传统红黑树更容易统一。

详细版

LLRB（Left-Leaning Red-Black Tree）通常把红色看成「父节点与子节点之间的链接颜色」。核心规则：

红链接只能向左倾斜；
不允许一个节点同时连接两条连续红链接；
完全黑平衡，对应 2-3 树的平衡性。

插入时新节点为红色，然后局部修复：

若右链接为红且左链接不红，左旋；
若左链接为红且左孩子的左链接也红，右旋；
若左右链接都红，颜色翻转。

LLRB 的思想是把普通红黑树的复杂 case 压缩成固定的局部规则，更适合教学和简洁实现。

完整版教学

一、为什么会有 LLRB

传统红黑树插入删除有很多镜像情况：叔叔红、叔叔黑、左左、左右、右右、右左。它性能很好，但实现和记忆成本高。LLRB 的目标是用更少的规则表达同样的平衡思想，尤其让插入代码变得接近递归 BST 插入后的三步修复。

LLRB 的「左倾」不是数学必然，而是一种约定：把表示 3-node 的红链接统一放在左边。统一方向后，右倾红链接就被视为需要旋转修正的临时状态。

记忆钩子：LLRB 是给红链接定了交通规则：能左不右，右倾就旋回来。

二、红链接和 2-3 树的关系

LLRB 常用红链接表示 2-3 树里的 3-node。一个黑节点和它的左红孩子可以合起来理解成一个含 2 个 key 的 3-node。这样二叉树结构就能模拟多路平衡树结构。

2-3树中的 [a|b]
可表示为:
    b(B)
   /
 a(R)

这里红色不是说节点本身危险，而是表示它和父节点逻辑上属于同一个 3-node。要求红链接左倾，就是统一用左红孩子来编码 3-node。

三、插入修复的三条规则

LLRB 插入后通常按固定顺序修复：

if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);

第一条修正右倾红链接。第二条修正连续左红链接，避免 4-node 表示失控。第三条把临时 4-node 向上分裂，相当于 2-3 树节点分裂。三条规则组合起来，让树既保持 BST 中序，又保持黑平衡。

四、用数字例子看插入

插入 1,2,3。插入 1 后根变黑。插入 2 时，2 作为 1 的右红孩子，出现右倾红链接，需要左旋，变成 2 黑、1 红。插入 3 后，2 的左右孩子都红，颜色翻转，2 变红，1 和 3 变黑，最后根再染黑。

步骤	局部问题	修复
右孩子红、左孩子黑	右倾红链接	左旋
左孩子红且左左红	连续红链接	右旋
左右孩子都红	临时 4-node	颜色翻转

这个过程和 2-3 树插入分裂非常接近，只是用二叉树旋转表达。

五、LLRB 和普通红黑树的区别

普通红黑树允许红节点作为左孩子或右孩子，只要不出现红红相连并满足黑高一致即可。LLRB 额外要求红链接左倾，因此它是更受限制的一类红黑树表示。限制更强的好处是实现规则更统一，坏处是某些操作可能需要更多旋转来维护左倾约束。

维度	普通红黑树	LLRB
红链接方向	左右都可	倾向左侧
教学实现	case 较多	规则较少
对应模型	2-3-4 树常见	2-3 树常见
工程使用	TreeMap 等常见	教学和简洁实现常见

面试里如果不是专门问 LLRB，不要把它和工业红黑树实现混为一谈。

六、删除为什么仍然不简单

LLRB 插入非常优雅，但删除仍然有复杂度。删除过程中要确保沿搜索路径不会进入 2-node，否则删除后可能破坏黑平衡。常见实现会在向下递归时提前做 moveRedLeft 或 moveRedRight，把红链接借到需要的方向。

这说明 LLRB 不是让红黑树所有操作都变成傻瓜题，而是把规则体系换成更统一的 2-3 树视角。理解这个视角，比硬背每个删除函数更重要。

七、常见误区与追问

误区：LLRB 是另一种完全不同的数据结构。 它仍是红黑树思想的一种变体和编码方式。
追问：为什么红链接要左倾？ 为了统一表示 2-3 树中的 3-node，减少镜像 case。
误区：LLRB 的节点红色和普通红黑树意义完全一样。 LLRB 更强调链接颜色，用红链接表示节点合并关系。
追问：LLRB 插入三步是什么？ 右红左黑左旋、左左红右旋、左右都红颜色翻转。
误区：LLRB 删除也很简单。 删除仍需处理向下借红链接和黑平衡维护。

八、加强记忆

LLRB 可以记成「红链接代表 3-node，统一向左倒」。它通过左旋修正右红，通过右旋修正连续左红，通过颜色翻转拆分临时 4-node。它和普通红黑树的目标一样，都是保证对数高度；区别在于 LLRB 给红链接加了左倾约束，让插入规则更像 2-3 树的局部分裂。

简化版

详细版