我的作业中的一个问题是找到确切的下限
(#black nodes)/(#red nodes)
在 rb 树中。界限一定不是渐近的。有什么建议么？
您的帮助将不胜感激。
问问题
549 次
1 回答
3
假设这是一个家庭作业：
让我们回顾一下来自Wikipedia的 RedBlack Trees 的一些属性：
- ...
- 根是黑色的。
- 所有的叶子都是黑色的。
- 每个红色节点的两个孩子都是黑色的。
- ...
要获得#B/#R 的下限，您需要构建一棵具有尽可能多的红色节点的树。（不幸的是，由于 2,3,4 你不能构造一棵全红的树）
一些值得思考的问题：
- 你能在平衡或不太平衡的树中放置更多的红色节点吗？
- 偶数或奇数最大高度会有所不同吗？
- 假设一棵树包含 3, 7, ..., (2^n)-1 个后向节点，您可以放入多少个红色节点？
于 2011-04-12T06:51:05.483 回答