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

Question

如何查找红黑树中红色节点的百分比？我熟悉红黑树的特性，但似乎无法将我的头围绕如何处理这个问题。我有一个想法，就是在构建它之后遍历树并计算红色节点，但对于较大的输入来说效率不高。

Answer 1

好吧，如果你存储的每个子树红色和黑色结点的数量，您可以交易时间换空间...

，你只能通过查看根确定这一点。

这是一个红黑树的属性，您存储在节点中的信息只能通过查看节点的子节点（可能是其父节点;我的内存有点模糊）才能更新，不会影响复杂度的树操作。
因此，您的树木建筑将会变慢，但只是一个常数因素。

这个因素是否足够小以至于如果您只需要确定一次这个百分比，那么在实践中保存任何时间都是另一回事。