红黑树澄清问题

Question

我一直在读关于红黑树的文章，有两个问题一直困扰着我。我仍然在了解他们，非常抱歉，如果这些是明显的，对一个更有经验的编码器。

1. 如果在红黑树中插入一个节点，平衡该树，然后删除该节点，它会导致同一棵树吗？总是这样吗？在我看来是这样，但我不完全确定。
2. 如果删除没有子节点的红色节点，则平衡树，然后重新插入相同的节点总是导致相同的树？总是，有时候，还是从来没有？

再次，抱歉，如果有琐碎，我仍然在学习，并没有找到一个好的答案，这些问题。提前感谢！

Answer 1

你的第一个问题的答案是no it does not lead to the same tree，下面我给出了一个例子：

         5(B)                        5(B)                   5(B)
     /          \        Del(3)    /      \     Ins(3)    /      \
   3(B)          9(B)    =====>   4(B)    9(B)  =====>  4(B)     9(B)
      \                                                 /
       4(R)                                          3(R)

正如你所看到的，树已经变了。

第二个问题的答案是yes it always result in the same tree，因为当您删除一个red node that has no children时，不会因为没有违反规则而发生再平衡，因为red node的父节点总是black node，当我们再次添加红色节点时，它占据了相同的位置。

下面是一个可视化工具的链接，它可以帮助您清除更多的疑问：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html