私はコンピューター サイエンス大学の新入生です。わかりやすい理由を教えてください。
635 のノードを持つ高さによって平衡化されたバイナリ ツリーがあります。最悪のシナリオで発生する比較の数とその理由は?
11506 次
3 に答える
5
これを考える一つの方法があります。二分探索木で比較を行うたびに、次のいずれかが発生します。
- あなたは木から離れました。この場合、これで完了です。
- 探している値は、現在調査しているノードと一致します。この場合、これで完了です。
- 探している値が、調査しているノードと一致しません。その場合、あなたは左に降りるか、右に降りるかのどちらかです。
ここでの重要な観察は、各ステップの後、終了する (やった!) か、ツリーを下に降りるかのいずれかであるということです。各ポイントで、1 つの比較を行います。永遠に下降することはできないため、実行できる比較の数は限られています。具体的には、ツリーの高さが h の場合、レベルごとに 1 つの比較を行うと、実行できる比較の最大数は h + 1 になります。 .
あなたの質問では、635 個のノードのバランスのとれた二分探索木があることがわかります。木のバランスが取れているかどうかを判断するにはさまざまな方法があり、それらすべてが異なる木の高さにつながるため、このコンテキストで「バランスが取れている」が何を意味するのかは 100% 明確ではありません。最後のレベルを除くすべてのレベルが満たされている完全な二分探索ツリーが与えられていると仮定します。
これが重要な理由は、高さ h の完全な二分探索木がある場合、最大で 2 h + 1 - 1 ノードを持つことができるからです。木の高さをノード数で解こうとすると、次のようになります。
n = 2時間+1 - 1
n + 1 = 2時間 +1
lg (n + 1) = h + 1
lg (n + 1) - 1 = h
したがって、ノード数が n の場合、n 個のノードを保持する完全な二分探索木の最小の高さを決定できます。あなたの場合、n = 635 なので、
lg (635 + 1) - 1 = h
lg (636) - 1 = h
9.312882955 - 1 = 時間
8.312882955 = h
したがって、ツリーの高さは 8.312882955 です。もちろん、木は分数の高さを持つことはできないので、天井を取ると木の高さが 9 になることがわかります。行われる比較の最大数は h + 1 であるため、実行するときに最大 10 回の比較が行われます。ルックアップ。
お役に立てれば！
于 2013-06-13T18:59:34.427 に答える
0
一般性を失うことなく、最大のノーと言えます。比較の高さはBSTの高さになります...比較ごとにノードに近づくため、ノード内のすべてのノードにアクセスする必要はありません...
于 2013-06-13T19:32:18.780 に答える