红黑树证明
Red-Black Tree Proof
我对我的最终评论有疑问 sheet 说。证明对于n>1，一棵红黑树必须至少有1个红色节点。这对我来说很有意义，因为如果 n 是偶数，则根部的 2 个子树具有不同数量的节点，因此必须至少有一个红色才能使所有路径保持相同的黑色高度。然后还有另一个问题说黑色高度为 k 的树的最小内部节点是 2^k -1。对此的证明是，如果每个节点都是黑色的，则完整的二叉树（假设计算了虚拟外部叶子）的高度将为 k，并将其代入公式 2^h -1 即可得到答案。
我的问题是第一个证明如何与第二个证明重合。一棵多于 1 个节点的树怎么可能至少有 1 个红色节点，而最小内部节点树只有黑色节点。谁能赐教一下？
第一个证明是基于它的插入算法，这就是为什么总是有一个红色节点的原因。但是在第二个证明中，你实际上可以手动构建一个只包含黑色的红黑树。使用常用的插入算法，插入时总是红色。
我插入这个作为答案，以防有人有同样的问题或知道更准确的词作为答案。
正在阅读 material：http://www.geeksforgeeks.org/red-black-tree-set-2-insert/
我对我的最终评论有疑问 sheet 说。证明对于n>1，一棵红黑树必须至少有1个红色节点。这对我来说很有意义，因为如果 n 是偶数，则根部的 2 个子树具有不同数量的节点，因此必须至少有一个红色才能使所有路径保持相同的黑色高度。然后还有另一个问题说黑色高度为 k 的树的最小内部节点是 2^k -1。对此的证明是，如果每个节点都是黑色的，则完整的二叉树（假设计算了虚拟外部叶子）的高度将为 k，并将其代入公式 2^h -1 即可得到答案。
我的问题是第一个证明如何与第二个证明重合。一棵多于 1 个节点的树怎么可能至少有 1 个红色节点，而最小内部节点树只有黑色节点。谁能赐教一下？
第一个证明是基于它的插入算法，这就是为什么总是有一个红色节点的原因。但是在第二个证明中，你实际上可以手动构建一个只包含黑色的红黑树。使用常用的插入算法，插入时总是红色。
我插入这个作为答案，以防有人有同样的问题或知道更准确的词作为答案。
正在阅读 material：http://www.geeksforgeeks.org/red-black-tree-set-2-insert/