对于相同的输入，红黑树的每个实现都具有相同数量的红色节点吗？

Question

详细说明，对于相同的输入，是否可以有实现不同的红黑树的实现？

Answer 1

从理论上讲，有很多方法可以维护所需的RB-tree不变式，因此，可以肯定的是，不同的实现可以产生完全不同的树。

但是，在实际的实际实现中，没有太多选择。如果“输入”由一系列插入组成，则不同的实现可能仍会产生不同的树，但是每个级别中的黑色节点数将相同。这是由于红黑树和2-3-4 B树之间的关系。

但是，关于如何实现删除还有更多选择，因此，如果您所说的“输入”包括删除，那么黑色节点结构也可以不同。