1回答

liuyubobobo

2021-04-17

已采纳

红节点表示的是 2-3 树中，和父亲的黑节点融合在一起的一个 3 节点。

但是，在我们向 2-3 树添加节点的时候，可能出现“临时的” 4-节点。比如这页 ppt：

当需要右旋转的时候，相当于出现了一个临时的 4-节点。他最初是这个样子：

注意，此时12-37-42 这三个节点，实际上在 2-3 树中，是一个临时的 4-节点。

在我们右旋转以后，变成这个样子：

但是变成这个样子以后，12-37-42 依然应该对应 2-3 树中的一个 4 节点，而不是 12-37 是一个 3 节点，42 是一个单独的 2-节点。红黑树对应的 2-3 树不应该有改变。（*）

但是，现在怎么表示 12-37-42 是一个 4-节点？答案是给 42 染红。此时，我们依然使用了 “红节点表示和父亲的黑节点融合在一起”的定义，但暂时打破了“左倾”的定义。（反正是临时的）。这样一来，12-37-42 就表示一个 2-3 树中的临时 4-节点：

之后，通过 flipColors，相当于做到了把这个临时 4-节点拆开，让 37 的子节点都成为了单独的 2-节点（即黑色）：

这个过程是将我们的红黑树映射成 2-3 树相对应的。如果不染红，在我上文标（*）的地方，我们的红黑树和 2-3 树的对应关系变了。

继续加油！：）

0

1

hellocp7

非常感谢！

2021-04-23

共1条回复