为什么每次插入左倾红黑树后都需要将根着色为黑色？
Why is it necessary to color the root black after every insertion into a Left-Leaning Red-Black Tree?
在 Sedgewick 的左倾红黑树中（在他的 paper or his Algorithms book 中提出），对标准 BST 的一个修改是在每次插入后将根节点着色为黑色，参见 root.color = BLACK insert(Key, Value).
我理解这在语义上是必要的，因为根节点永远不应该是 3 节点/4 节点的左子节点。但是，我不明白为什么这在实践中是必要的，因为似乎从未检查过根节点的颜色。谁能指出我在这里遗漏了什么？
我想是因为你需要重建树，做树就是AVL。当您插入一个新节点时，根节点可能会更改为另一个节点并且需要为根重新着色。
检查代码后，我得出了与您相同的结论，即从未实际使用根颜色。
因此，我进行了一些测试以尝试确认这一点，在此过程中我发现该论文中提供的代码实际上存在一些小错误：对从未定义的方法的调用、对从未声明的变量、不必要的重复昂贵的方法调用、未使用的对象引用（=指针）等等。
当然，其中 none 个是一个非常严重的问题，其中 none 个问题需要付出很多努力才能解决；但我认为只有当代码 完美 或接近完美时，你的问题才真正有意义，而事实并非如此。鉴于代码有几十个编译错误和几个明显的非最佳位不涉及红黑语义，我认为争论是否是有意义的确实需要以语义预期的方式设置根节点颜色。
但就其价值而言，我的测试表明根颜色确实无关紧要；我写了一个验证方法来验证适当的不变量（没有红色 非根 节点有红色子节点，并且所有叶节点都有相同的黑色深度），我发现这些无论我是否注释掉将根颜色设置为黑色的行，都将被保留。 （当然，这仅针对我测试的案例进行了演示，但仍然足以让我对结论更有信心。具体来说，我的案例涉及按顺序、倒序或随机添加密钥 1 到 1000 -打乱顺序，然后按顺序、倒序或随机打乱顺序删除它们。我在每次插入或删除后验证了不变量。）
对于标准的红黑树来说，这似乎没有什么不同：约定是根应该是黑色的。这只不过是一个约定，因为理论上根节点可以是（左）红色而不违反任何（其他）红黑树属性。这种颜色变化也不会影响左倾红黑树的附加属性。
请参阅 Red-black tree - Wikipedia 中的 属性 #2：
- The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
简而言之：将根节点着色为黑色不是必需的，而是按照惯例完成的。
黑色根的着色作用是简化需要执行的检查。如果将根节点着色为黑色并将 运行 着色为红色违规，则您知道（无需进一步测试）当前节点的父节点不是根节点，因此当前节点也有祖父节点。在我研究过的树中，执行颜色检查比检查当前节点是否是根要便宜得多。
在 Sedgewick 的左倾红黑树中（在他的 paper or his Algorithms book 中提出），对标准 BST 的一个修改是在每次插入后将根节点着色为黑色，参见 root.color = BLACK insert(Key, Value).
我理解这在语义上是必要的，因为根节点永远不应该是 3 节点/4 节点的左子节点。但是，我不明白为什么这在实践中是必要的，因为似乎从未检查过根节点的颜色。谁能指出我在这里遗漏了什么？
我想是因为你需要重建树，做树就是AVL。当您插入一个新节点时，根节点可能会更改为另一个节点并且需要为根重新着色。
检查代码后，我得出了与您相同的结论，即从未实际使用根颜色。
因此，我进行了一些测试以尝试确认这一点，在此过程中我发现该论文中提供的代码实际上存在一些小错误：对从未定义的方法的调用、对从未声明的变量、不必要的重复昂贵的方法调用、未使用的对象引用（=指针）等等。
当然，其中 none 个是一个非常严重的问题，其中 none 个问题需要付出很多努力才能解决；但我认为只有当代码 完美 或接近完美时，你的问题才真正有意义，而事实并非如此。鉴于代码有几十个编译错误和几个明显的非最佳位不涉及红黑语义，我认为争论是否是有意义的确实需要以语义预期的方式设置根节点颜色。
但就其价值而言，我的测试表明根颜色确实无关紧要；我写了一个验证方法来验证适当的不变量（没有红色 非根 节点有红色子节点，并且所有叶节点都有相同的黑色深度），我发现这些无论我是否注释掉将根颜色设置为黑色的行，都将被保留。 （当然，这仅针对我测试的案例进行了演示，但仍然足以让我对结论更有信心。具体来说，我的案例涉及按顺序、倒序或随机添加密钥 1 到 1000 -打乱顺序，然后按顺序、倒序或随机打乱顺序删除它们。我在每次插入或删除后验证了不变量。）
对于标准的红黑树来说，这似乎没有什么不同：约定是根应该是黑色的。这只不过是一个约定，因为理论上根节点可以是（左）红色而不违反任何（其他）红黑树属性。这种颜色变化也不会影响左倾红黑树的附加属性。
请参阅 Red-black tree - Wikipedia 中的 属性 #2：
- The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
简而言之：将根节点着色为黑色不是必需的，而是按照惯例完成的。
黑色根的着色作用是简化需要执行的检查。如果将根节点着色为黑色并将 运行 着色为红色违规，则您知道（无需进一步测试）当前节点的父节点不是根节点，因此当前节点也有祖父节点。在我研究过的树中，执行颜色检查比检查当前节点是否是根要便宜得多。