-1

我的作业中的一个问题是找到确切的下限

(#black nodes)/(#red nodes)

在 rb 树中。界限一定不是渐近的。有什么建议么?

您的帮助将不胜感激。

4

1 回答 1

3

假设这是一个家庭作业:

让我们回顾一下来自Wikipedia的 RedBlack Trees 的一些属性:

  1. ...
  2. 根是黑色的。
  3. 所有的叶子都是黑色的。
  4. 每个红色节点的两个孩子都是黑色的。
  5. ...

要获得#B/#R 的下限,您需要构建一棵具有尽可能多的红色节点的树。(不幸的是,由于 2,3,4 你不能构造一棵全红的树)

一些值得思考的问题:

  • 你能在平衡或不太平衡的树中放置更多的红色节点吗?
  • 偶数或奇数最大高度会有所不同吗?
  • 假设一棵树包含 3, 7, ..., (2^n)-1 个后向节点,您可以放入多少个红色节点?
于 2011-04-12T06:51:05.483 回答