紅黑樹中紅色節點的百分比

Question

如何查找紅黑樹中紅色節點的百分比？我熟悉紅黑樹的特性，但似乎無法將我的頭圍繞如何處理這個問題。我有一個想法，就是在構建它之後遍歷樹並計算紅色節點，但對於較大的輸入來說效率不高。

Answer 1

好吧，如果你存儲的每個子樹紅色和黑色結點的數量，您可以交易時間換空間...

，你只能通過查看根確定這一點。

這是一個紅黑樹的屬性，您存儲在節點中的信息只能通過查看節點的子節點（可能是其父節點;我的內存有點模糊）才能更新，不會影響複雜度的樹操作。
因此，您的樹木建築將會變慢，但只是一個常數因素。

這個因素是否足夠小以至於如果您只需要確定一次這個百分比，那麼在實踐中保存任何時間都是另一回事。