赤黒の木の赤いノードの割合

Question

赤い黒のツリーの赤いノードの割合を調べるにはどうすればよいですか？私は赤黒の木の特性に精通していますが、これに近づく方法について私の頭を包んでいるようには見えません。私が持っているアイデアの1つは、ツリーを構築して赤いノードを数えた後に単純にツリーをたどることですが、大きな入力に対しては効率が悪いようです。

Answer 1

さて、あなたは宇宙の時間を交換することができます...

あなたは、各サブツリー内の赤と黒のノード数を保存する場合は、rootだけを見て、これを決定することができます。

これはノードに保存する情報で、ノードの子（および親の可能性もあるが、私のメモリは少し濁っている）を見るだけで更新することができ、複雑さには影響しませんツリー操作の
あなたのツリー構築は遅くなりますが、一定の要因によってのみです。

この係数が実際にはどれくらいの時間を節約できるかどうかは、このパーセンテージを決定する必要がある場合にのみ、1回は別の問題です。