算法（37）：red-black BSTs-10.2

Page 18物理映射如何用 BST 表示 2-3 树核心物理事实红黑树是 2-3 树在 BST 上的具体编码方式。用 BST 的节点表示 2-3 树中的2-节点一个键两条链接。用两条用红链接Red Link相连的 BST 节点表示 2-3 树中的3-节点两个键三条链接。约定红链接固定为左倾Left-leaning即红色链接只能出现在父节点的左子节点方向。Page 19红黑树的三个基本性质这是红黑树必须满足的三个硬性约束无节点同时连接两条红链接对应 2-3 树中不会出现 4-节点除非临时存在。完美黑平衡Perfect Black Balance从根节点到任意空链接null的路径上经过的黑色链接数量完全相同对应 2-3 树的完美平衡所有叶子在相同深度。红链接必须左倾对应 3-节点在编码时的固定取向。Page 20与 2-3 树的 1-1 对应关系PPT 强调满足上述三个条件的红黑树与 2-3 树之间存在一一对应。你可以把红链接“压平”把相连的两个节点合并成一个 3-节点就能得到一棵 2-3 树。反之任何 2-3 树都可以唯一地编码成这样的红黑树。Page 21搜索实现忽略颜色物理事实红黑树的搜索代码与普通 BST完全一样。搜索过程中不检查节点颜色只检查键的大小。因为颜色只是为了维护平衡的辅助信息不影响查找的逻辑顺序。Page 22颜色存储的位置每个节点只能由父节点的一根链接指向。因此节点的颜色等价于指向它的链接的颜色。在实现中颜色信息作为节点对象的一个布尔字段boolean color存储。根节点没有父链接通常规定根节点为黑色。颜色往上取而不是往下Page 23-24左旋操作修复右倾红链接触发条件当前节点的右子节点是红色左子节点是黑色。物理动作rotateLeft设当前节点为h右子节点为x红色。将x的左子树移交给h作为右子树。将h设为x的左子节点。将x的颜色设为h原来的颜色保持父层颜色的连续性。将h的颜色设为红色。返回x作为新的子树根该节点的颜色与h原本的颜色相同。物理效果把原本右倾的红链接“扶正”为左倾红链接同时维持 BST 的中序顺序。黑平衡在旋转后依然保持。这是right-leaning纠正的情况纠正方法是把E-S变成E-S。可想而知是把“between E and S”拆下来挂载到E的右端点。修改后注意最后把小局部挂载回主干是通过return x完成的谁是x谁就是小局部无颜色状态下的祖先节点。Page 25-26右旋操作修复连续的左倾红链接触发条件当前节点的左子节点是红色并且左子节点的左子节点也是红色两条连续的左倾红链接。这种状态对应 2-3 树中临时出现的 4-节点。物理动作rotateRight设当前节点为h左子节点为x红色。将x的右子树移交给h作为左子树。将h设为x的右子节点。将x的颜色设为h原来的颜色。将h的颜色设为红色。返回x作为新的子树根。Page 27-28颜色翻转拆分临时 4-节点触发条件当前节点的两个子节点都是红色。这表示当前节点与两个子节点一起在 2-3 树中构成了一个临时的 4-节点3 个键、4 条链接。物理动作flipColors将当前节点的颜色设为红色如果它不是根节点意味着它现在要与它的父节点合并向上传递。将两个子节点的颜色设为黑色拆分成两个独立的 2-节点。物理效果将 4-节点分裂成两个 2-节点并将中间键当前节点向上“推”到父层级参与合并。这保持了黑平衡。Page 29插入的概述插入流程与普通 BST 插入相同但插入的新链接总是红色相当于在 2-3 树中将新键放入一个已有节点或与父节点合并。然后沿着搜索路径向上通过旋转和颜色翻转来修复红黑树性质。演示right leaning到left leaning其原因是插入后导致一个2node右节点出现了一个element而RBT模仿的2-3tree中所有的插入过程都是2node-3node-4node-分裂2nodes因此这里插入的C要变成与A相连的整体。而由于C插入后是在右边并且插入的同时就改变了颜色所以就出现了temporary right leaning结构。将这种暂时右倾修正就是左旋本质上是把插入到右边的element也挪上来。类似的操作也出现在BST的deletion中。Page 30-31向 2-节点插入情况向一个 2-节点标准 BST 节点插入新键执行标准 BST 插入新链接标记为红色。如果新链接出现在右子节点位置右倾红链接执行左旋使其成为左倾红链接。印证了上面的左旋修正右倾观点Page 32-33向 3-节点插入情况向一个 3-节点当前节点已有红链接连接子节点插入新键执行标准 BST 插入新链接标记为红色。平衡 4-节点如果出现右倾红链接执行rotateLeft。如果出现连续左倾红链接左孩子和左孙子的链接都是红色执行rotateRight。执行颜色翻转flipColors将当前节点变红子节点变黑相当于向上传递键。如果父节点因此出现新的不平衡继续重复上述步骤向上传递。Page 34向上传递红链接插入过程中当颜色翻转发生后中间键当前节点变为红色与它的父节点形成新的红链接。此时可能再次出现红色右倾链接或连续红链接。因此需要从插入点向上一直检查到根节点重复应用左旋、右旋、颜色翻转。Page 35-40插入轨迹与可视化这些页面是插入操作按升序或随机顺序的图形轨迹。它们验证了红黑树在插入过程中的形态变化。无新文本内容。Page 41性能分析物理结论红黑树的最坏情况高度不超过2 lg N因为不允许连续两条红链接且黑链接路径长度相同。在典型应用中树高约为~1.00 lg N。所有操作查找、插入、删除在最坏情况下均为对数级别。Page 42符号表实现总结红黑树在最坏情况和平均情况下的查找、插入、删除成本均为~2 lg N且支持有序迭代。它解决了普通 BST 在最坏情况下退化为链表的问题。Page 43-44历史与教训这页提到了 Guibas-Sedgewick 论文和红黑树在实际系统中的使用。Page 44 讲述了一个真实事故某数据库实现使用红黑树和 Hibbard 删除但因删除操作导致树高超出限制触发错误恢复流程最终导致服务中断。法律论证表明红黑树的高度保证是≤ 2 lg N这提醒你即使在红黑树中删除操作特别是 Hibbard 删除仍可能影响树的平衡性需要正确实现。这一节的物理操作已经全部覆盖红黑树是用 BST 表示 2-3 树通过颜色标记 3-节点用左旋、右旋、颜色翻转来维持黑平衡。一、颜色的存储Q第22页这里我觉得有点奇怪在note类里面既有一个布尔变量color在外面又有两个布尔变量一个是red一个是blackAprivate static final boolean RED true;和private static final boolean BLACK false;是常量定义存储在类元数据区方法区不占用每个对象的堆内存。它们的存在是为了提高代码可读性——你可以写x.color RED而不是x.color true。boolean color;是实例字段存储在堆上的每个Node对象中。它记录指向该节点的链接的颜色红色为true黑色为false。注意注释里写的// color of parent link意思是这个节点的颜色取决于父节点指向它的链接颜色。isRed(Node x)是一个工具方法如果x不是null且其color字段为true即红色返回true。空链接被视为黑色null不占内存也不需要存储颜色。所以不是“两个布尔变量”而是一个实例变量 两个常量标签 一个工具方法。你提到的“外面有两个布尔变量”它们只是用来给color赋值时的语义标签不存储任何节点状态。节点自己的颜色只储存在它的color字段里。二、最坏情况Q红黑树的最坏情况高度不超过 2 lg N因为不允许连续两条红链接且黑链接路径长度相同。这里详细讲讲A1. 两个物理约束的独立含义约束 A完美黑平衡所有路径黑色链接数相同定义从根到任意空链接的路径上黑色链接的数量为B固定常数。这意味着如果忽略所有红色链接只看黑色链接树是一个完美平衡的二叉树所有叶子在同一深度B。对于一棵深度为B的完美平衡二叉树最多能容纳的节点数是2^B - 1。因此N≤2B−1⇒B≤⌈log⁡2(N1)⌉这是红色链接不存在时树高的上限。换句话说黑色链路的数量B被log N锁死。约束 B不允许连续两条红色链接在任意一条从根到叶子的路径上红色链接不能连续出现即不能出现红-红相连。因此在这条路径上红色链接的数量最多等于黑色链接的数量否则必然会出现连续红链。2. 组合推导树高上限设总路径长度树高为H黑色链接数 红色链接数之和。路径上黑色链接数固定为B。因为不能有连续红链路径上的红色链接数≤B。所以总长度H 黑色数 红色数 ≤ B B 2B。代入上面由黑平衡得到的B ≤ log₂N得到H≤2log⁡2N这就是“最坏情况高度不超过2 lg N”的完整推导。3. 为什么这个保证在物理上是可接受的2 log₂N在渐进意义下依然是对数级别只是常数因子是 2。当N 10⁹时理想平衡树高约30。红黑树最坏高度约60。60 次指针跳转在现代 CPU 上仍然是微秒级别的操作且在工业应用中被认为是可以接受的上界。你之前看到 PPT 里的“红色节点最多与黑色节点一样多”就是这个证明的另一种表述方式。因为红链不能连续出现所以红色的数量不能超过黑色的数量。将这个事实与黑平衡的log N约束相乘就直接得到高度上限。