红黑树证明

Question

我在最后的复习单上有个问题，上面说。对于n>1，一棵红黑树必须至少有一个红色节点.这对我来说是有意义的，因为如果n是偶数，则来自根的两个子树有不同的节点数，因此必须至少有一个红色才能使所有路径保持相同的黑色高度。还有另一个问题，就是黑高k的树的最小内部节点是2^k-1。这方面的证明是，如果每个节点都是黑色的，则整个二叉树，假设虚拟的外部叶子被计算在内，将会有高度k，并将其插入公式2^h-1中，给出答案。

我的问题是，第一种证据和第二种证据怎么会一致呢？一个节点超过一个节点的树怎么可能至少有一个红色节点，而最小的内部节点树却只有黑色节点。有人能指点我吗？

Answer 1

第一个证明是基于它的插入算法，这就是为什么总是有一个红色节点。但是在第二个证明中，你实际上可以手工构建一个只有黑色的红黑树。使用常用的插入算法，插入时总是会出现红色。

如果有人有同样的问题，或者知道更准确的单词，我会把它作为答案插入。

阅读材料：http://www.geeksforgeeks.org/red-black-tree-set-2-insert/