BST的红黑树和高度属性

Question

考虑一下，我们只想将 BST 转换为红黑树，仅使用着色而不进行任何其他更改。

为什么高度为2*log n的二叉搜索树并不总是使用上述事实转换为红黑树，而完全平衡的BST总是可以通过着色转换为红黑树？

Answer 1

要求树有一定的高度会限制最大深度，但不会限制最小深度。你可以有一个高度为 2 log n 的树，它有一个浅的左子树和一个深的右子树：

   *
  / \
 /   \
*     *
     / \
    /   \
   /     \
  /       \
 /         \
/___________\

所有节点的黑色高度必须相同，这意味着左子树限制黑色高度最多为2。只有两个才能避免右子树中的红色边缘但是，每条路径上都有黑色节点。