algorithm - 插入红黑树

Question

我正在上一门算法类(class)，在我的类(class)幻灯片中，有一个插入红黑树的示例:

我的问题是，为什么我们不让“2”在这里成为叶节点呢？看起来如果我们让它成为叶节点，那么就不会违反红黑树的条件。我在这里缺少什么？

Answer 1

问题不在于图像的第二棵树 2 的位置，而在于不同节点的颜色。解释如下:

insertion 的第一条规则在红黑树中是:新插入的节点必须始终是红色的。您陷入了案例 3​​ 插入，其中节点 2 的父亲和叔叔都是红色。因此需要将它们重新着色为黑色，祖父将变为红色，但由于祖父是根，因此它会再次变为黑色。

所以新树(插入2后)应该是这样的(r和b表示颜色，.b是Nil节点):

       5b
     /    \     
    1b     7b
  /   \    / \
 .b    2r .b  .b
       / \
      .b  .b

为什么我们总是需要在彩铃中插入红色节点，你可能会问？答案是，第一我们知道在 RBT 中每个 NIL 节点总是黑色的，第二我们有规则 5。如果我们在末尾插入一个黑色节点，树将违反此规则，只需将 2b 放在上面的树中而不是 2r 并保持 1 和 7 的颜色为红色，然后从根节点到任何 Nil 节点计数黑色节点，您将看到一些路径有 2 个后节点，一些路径有 3 个黑色节点。