完全に満たされたバイナリ ツリーの場合、そのツリーの高さは に等しくfloor(log2(N))、特定のキーを見つけるための比較の最大数は単純h+1に 、またはであることを知っていますfloor(log2(N)) + 1。
この質問は、ファイナルのレビューに出てきますが、答えを見つける方法を思い出せません。考えられる答えは次のとおり7, 8, 9, 10です。答えが9またはであると確信していますが、数値( ) または10に基づいて答えを計算する必要があるかどうかわからないため、わかりません。5122^9191
助けてください！
高さが指定されているので、間違いなくそれが最も簡単な作業方法です。
比較の最大数は、ルートからリーフ ノードに到達するまでにトラバースできる非リーフ ノードの最大数です。彼がどのように高さを定義したかに応じて (残念ながら、これは広く合意されているわけではありません)、高さまたは高さよりも 1 つ低くなります。
これは非常にバランスの取れていない二分木で、高さが 5 のノードが 6 つあります。
1
\
2
\
3
\
4
\
5
\
6
6 を見つけたいとします。6 つの比較が必要です。(6 = 5 + 1)
したがって、あなたの場合、10回の比較が必要です（10 = 9 + 1）。ノードの数は答えに影響しません。