红黑树：插入节点与平衡维护

# 红黑树：插入节点与平衡维护 ## 1. 红黑树规则冲突与初步处理 在红黑树中，当父节点和子节点均为红色时，就违反了规则 3。例如，有一棵红黑树，父节点和子节点都是红色，为了解决这个问题，我们尝试将子节点 6 变为黑色。操作步骤如下： 1. 将红色箭头定位到节点 6 上。 2. 按下 R/B 按钮，此时节点 6 变为黑色。 虽然解决了父节点和子节点均为红色的问题，但新的问题出现了，提示“Error: Black heights differ”。从根节点到节点 6 的路径上有三个黑色节点，而从根节点到节点 75 的路径上只有两个黑色节点，这违反了规则 4。这个问题可以通过旋转和颜色更改来解决。 ## 2. 更多实验与红黑规则的作用 ### 2.1 实验操作 我们可以使用 RBTree Workshop 小程序进行更多实验： - 插入更多节点，观察插入节点后树的变化，尝试通过旋转和颜色更改来实现树的平衡，看看保持红黑树的正确性是否能保证树（几乎）平衡。 - 先插入升序键（50, 60, 70, 80, 90），然后点击 Start 按钮重新开始，再插入降序键（50, 40, 30, 20, 10），先忽略出现的提示信息，这些情况通常会让普通二叉搜索树陷入困境，观察是否还能平衡这棵树。 ### 2.2 红黑规则保证平衡 尝试创建一棵高度差为两层或更多但红黑规则正确的树，结果会发现这是不可能的。这就是红黑规则能够保持树平衡的原因。如果一条路径比另一条路径长一个节点以上，那么它要么有更多的黑色节点，违反规则 4；要么有两个相邻的红色节点，违反规则 3。可以通过小程序实验来验证这一点。 ### 2.3 空孩子与黑高 规则 4 规定，从根节点到任何叶子节点或空孩子的所有路径必须有相同数量的黑色节点。空孩子是指非叶子节点可能有但实际没有的孩子。例如，在某个树结构中，从 50 到 25 再到 25 的右孩子（其空孩子）的路径上只有一个黑色节点，这与到 6 和 75 的路径上有两个黑色节点不同，这种情况违反了规则 4，尽管到叶子节点的两条路径有相同数量的黑色节点。黑高用于描述从根节点到给定节点的黑色节点数量。 ## 3. 旋转操作 ### 3.1 旋转的目的和要求 为了平衡树，需要对节点进行物理重新排列，这可以通过旋转操作来实现。旋转操作需要同时满足两个条件： - 提升一些节点，降低另一些节点，以帮助平衡树。 - 确保不违反二叉搜索树的特性，即任何节点的左子节点的键值小于该节点，右子节点的键值大于或等于该节点。 颜色规则和节点颜色更改仅用于帮助决定何时执行旋转操作，真正起关键作用的是旋转操作。 ### 3.2 简单旋转 简单旋转通常涉及三个节点，以右旋转为例： - 选择一个节点作为旋转的“顶部”节点，该节点在右旋转时会向下并向右移动到其右子节点的位置。 - 其左子节点会向上移动到其位置。 需要注意的是，旋转的不是节点本身，而是它们之间的关系。并且在进行右旋转时，顶部节点必须有左子节点；进行左旋转时，顶部节点必须有右子节点。 ### 3.3 复杂旋转：交叉节点 旋转操作可能会比简单的三节点示例更复杂。例如，先将 50 作为根节点，然后按顺序插入 25、75、12、37。插入 12 时，会提示“Can’t insert: needs color flip”，点击 Flip 按钮，父节点和子节点会改变颜色，再次按下 Ins 完成 12 的插入，最后插入 37。此时，将箭头放在根节点上并按下 RoR 按钮，会发现 37 从 25 的右子节点分离出来，成为 50 的左子节点，这种旋转导致了规则 4 的违反。在原始位置中，37 被称为顶部节点 50 的内部孙节点，内部孙节点如果是上升节点的子节点，在旋转时会与父节点断开连接，并重新连接到其前祖父节点。 ### 3.4 子树的移动 旋转操作不仅会使单个节点改变位置，整个子树也会移动。例如，先将 50 作为根节点，然后按顺序插入 25、75、12、37、62、87、6、18、31、43，遇到“Can’t insert: needs color flip”提示时点击 Flip 按钮。将箭头放在根节点 50 上，按下 RoR 按钮后，会出现以下情况： - 顶部节点（50）移动到其右子节点。 - 顶部节点的左子节点（25）移动到顶部。 - 以 12 为根的整个子树向上移动。 - 以 37 为根的整个子树移动到成为 50 的左子节点。 - 以 75 为根的整个子树向下移动。 可以通过交替按下 RoR 和 RoL 按钮，观察子树的移动情况。每个子树内节点的关系不受旋转影响，整个子树作为一个单元移动。 ### 3.5 人与计算机处理旋转的差异 在实际操作中，我们可以通过将箭头放在顶部节点上，然后按下 RoR 或 RoL 按钮来触发旋转。但在真正的红黑树插入算法中，旋转是在程序控制下自动进行的，无需人工干预。作为人类，我们可以通过观察树的结构并执行适当的旋转来平衡树，但计算机更擅长遵循简单规则，红黑方案通过颜色编码和四个颜色规则为计算机提供了这样的规则。 以下是