我的作业中的一个问题是找到确切的下限
(#black nodes)/(#red nodes)
在 rb 树中。界限一定不是渐近的。有什么建议么?
您的帮助将不胜感激。
我的作业中的一个问题是找到确切的下限
(#black nodes)/(#red nodes)
在 rb 树中。界限一定不是渐近的。有什么建议么?
您的帮助将不胜感激。
假设这是一个家庭作业:
让我们回顾一下来自Wikipedia的 RedBlack Trees 的一些属性:
要获得#B/#R 的下限,您需要构建一棵具有尽可能多的红色节点的树。(不幸的是,由于 2,3,4 你不能构造一棵全红的树)
一些值得思考的问题: