红黑树证明

Question

我在我最后的评论表上有一个问题说。证明n> 1，红黑树必须至少有1个红色节点。这对我很有意义，因为如果n是偶数，则根中的2个子树的节点数不同，因此必须至少有一个红色才能保持所有路径具有相同的黑色高度。那么还有另外一个问题，就是说黑色高度为k的树的最小内部节点是2^k-1。证明这一点的是，如果每个节点都是黑色的，那么完整的二叉树（假设虚拟外部叶子被计数）将具有高度k，并且将其插入公式2^h-1给出我们的答案。

我的问题是第一次证明如何与第二次证明一致。具有多于1个节点的树如何能够具有至少1个红色节点，但是最小的内部节点树只具有黑色节点。任何人都可以启发我吗？

Answer 1

第一个证明基于它的插入算法，这就是为什么总是有一个红色节点的原因。但是在第二个证明中，你实际上可以建立一个仅由黑色构成的红黑树。使用常用的插入算法，插入时总是会显示红色。

我插入此作为一个答案，以防某人有相同的问题或知道更准确的单词用作aswer。

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