赤い黒い木の最大不均衡

私はこの概念を理解するのに苦労しているのですが、黒いノードがバランスされているとすれば、ツリー全体を考えるとRBツリーが持つことができる最大の不均衡は何ですか？ウィキペディアからの引用赤い黒い木の最大不均衡

2017-09-23 Bhargav

：the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.最大不均衡は葉への最短経路の長さの2倍であることを意味し

。

articleは理由を説明しています。

出典

2017-09-23 23:58:02

いいえ、しかし、これはブラックノードがバランスされているという事実を考慮していません。 – Bhargav

です。任意のパスの黒ノードの数がBの場合、最大深度には赤と黒のノードが交互に含まれるため、深さは2 * B（2 * B-1は黒ノードで開始して終了します。最小の深さには黒いノードしか含まれないので、Bになります。 –

赤い黒い木の最大不均衡

答えて

関連する問題