0

完全に満たされたバイナリ ツリーの場合、そのツリーの高さは に等しくfloor(log2(N))、特定のキーを見つけるための比較の最大数は単純h+1に 、またはであることを知っていますfloor(log2(N)) + 1。

この質問は、ファイナルのレビューに出てきますが、答えを見つける方法を思い出せません。考えられる答えは次のとおり7, 8, 9, 10です。答えが9またはであると確信していますが、数値( ) または10に基づいて答えを計算する必要があるかどうかわからないため、わかりません。5122^9191

助けてください！

4

3 に答える 3

1

高さが指定されているので、間違いなくそれが最も簡単な作業方法です。

比較の最大数は、ルートからリーフ ノードに到達するまでにトラバースできる非リーフ ノードの最大数です。彼がどのように高さを定義したかに応じて (残念ながら、これは広く合意されているわけではありません)、高さまたは高さよりも 1 つ低くなります。

于 2013-05-10T03:30:15.770 に答える
1

これは非常にバランスの取れていない二分木で、高さが 5 のノードが 6 つあります。

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

6 を見つけたいとします。6 つの比較が必要です。(6 = 5 + 1)

したがって、あなたの場合、10回の比較が必要です（10 = 9 + 1）。ノードの数は答えに影響しません。

于 2013-05-10T03:34:47.360 に答える