algorithm - 我们可以有一个没有任何红色节点的红黑树吗？

Question

我想知道一棵红黑树是否应该至少有一个红色节点。另外，给定 BST，如果我们可以将其转换为 RBT，是否有一种独特的方法可以将这棵树变成红黑树？

Answer 1

快速浏览一下红黑树的属性会发现，不需要任何节点都是红色的。出现红色节点的唯一方法是通过属性 5：

从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

任何完美二叉树也满足这个性质，因此每棵只有黑色节点的完美二叉搜索树也是红黑树。（不过，我不确定教科书的红黑树算法是否会产生这些。）

另外，给定 BST，如果我们可以将其转换为 RBT，是否有一种独特的方法可以将这棵树变成红黑树？

任意 BST 没有单一的唯一 RBT；总是有多个等效的 RBT，除了非常浅的树。