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

Question

<分区>

Answer 1

快速浏览 properties of a red-black tree表明没有任何节点必须是红色的要求。红色节点出现的唯一方式是通过属性 5:

Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

此属性也满足任何 perfect binary tree ，所以每棵只有黑色节点的完美二叉搜索树也是一棵红黑树。 (不过，我不确定教科书上的红黑树算法是否曾经产生过这些。)

Also, given a BST, if we can convert it into an RBT, is there a unique way to turn this tree into a red-black tree?

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