红黑树中红色节点的百分比

Question

我将如何找到红黑树中红色节点的百分比？我熟悉红黑树的属性，但似乎无法理解如何处理这个问题。我的一个想法是在构建树并计算红色节点后简单地遍历树，但对于更大的输入来说它似乎效率低下。

Answer 1

好吧，你可以用时间换 space...

如果存储每个子树中红色和黑色节点的数量，则只能通过查看根来确定。

它是一个 属性 的红黑树，你存储在节点中的信息只能通过查看节点的子节点（可能还有它的父节点；我的记忆有点模糊）来更新'影响树操作的复杂度。
所以你的树构建会变慢，但只会变慢。

如果您只需要确定一次这个百分比，那么这个因素是否小到可以节省您在实践中的任何时间是另一回事。