data-structures - 红-红-黑树中具有特定黑高的节点数

Question

我在家庭作业中被要求回答一个关于“红-红-黑”树的问题。红红黑树的描述（从互联网某处复制）是：

“红-红-黑树是满足以下条件的二叉搜索树：

1. 每个节点不是红色就是黑色
2. 每片叶子（零）都是黑色的
3. 如果一个节点是红色的，它的父节点是红色的，那么它的两个子节点都是黑色的
4. 从节点到后代叶子的每条简单路径都包含相同数量的黑色节点（树的黑色高度）”

有人问我，给定具有 n 个节点的红-红-黑树，黑色高度为 k 的最大内部节点数是多少？最小的数是多少？

我已经想了两个多小时了，但除了头痛之外，我一无所获。

谢谢！

Answer 1

最大节点数：(2^2k)-1

最小节点数：(2^k)-1

Answer 2

两个红节点永远不能连续出现。当您遍历任何路径时，黑色节点的数量应该相等。