红-红-黑树中具有特定黑色高度的节点数
我在作业中被要求回答一个有关“红-红-黑”树的问题。红红黑树的描述（从互联网上的某个地方复制）是：
“红红黑树是满足以下条件的二叉搜索树：
- 每个节点不是红色就是黑色
- 每片叶子（nil） ）是黑色
- 如果一个节点是红色并且它的父节点是红色，那么它的两个子节点都是黑色
- 从节点到后代叶子的每个简单路径都包含相同数量的黑色节点（树的黑色高度）”
我被问到，给定一个有n个节点的红红黑树，黑高k的内部节点的最大数量是多少？最小的数字是多少？
我已经尝试思考这个问题两个多小时了，但除了头痛之外，我什么也想不到。
谢谢！
I was asked in a homework assignment to answer a question regarding "Red-Red-Black" trees. The description of a red-red-black tree (copied from somewhere in the internet) is:
"A red-red-black tree is a binary search tree that satisfies the following conditions:
- Every node is either red or black
- Every leaf (nil) is black
- If a node is red and it's parent is red, then both its children are black
- Every simple path from a node to a descendant leaf contains the same number of black nodes (the black-height of the tree)"
I was asked, given a red-red-black tree with n nodes, what is the largest number of internal nodes with black-height k? What's the smallest number?
I've been trying to think about it for more then two hours now, but apart from headache I couldn't get anywhere.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
最大节点数：(2^2k)-1
最小节点数：(2^k)-1
maximum number of nodes : (2^2k)-1
minimum number of nodes : (2^k)-1
两个红色节点永远不可能连续出现。
当你遍历任何路径时，黑色节点的数量应该相等。
Two Red Node can never appear continuously.
Number of Black node should be equal in when you traverse through any path.