0

私が苦労してきた質問... 2 ～ 3 ツリーの実装で、ノードの次数が 1 にならないのはなぜですか?

O(log(n)) (B ツリー ファミリーのメンバーとして) 保持したい O(log(n)) に関連している可能性があると思いました。次数 1 が許可されている場合、次のようなツリーを取得できます。

1
 \
  2
   \
    3
     \
      4
       \
        5

たとえば、一部の操作では O(log(n)) の代わりに O(n) が使用されますが、この回答のどこで 2-3 ツリーを参照したか、および次数 1 を許可できない理由がわかりません。 . :-/

ありがとう！;-)

4

1 に答える 1

0

あなたはすでに正しい答えを持っていますが、次のように言いたいかもしれません:

B ツリー バリアントは、すべてのリーフを同じ深さ (ツリーの高さ) に維持し、操作には通常、その高さに比例して時間がかかります。

内部ノードには少なくとも 2 つの子が必要であるため、各レベルには親レベルの少なくとも 2 倍のノードが含まれ、ツリーの高さは O(log N) です。

内部ノードに 2 つ未満の子を含めることが許可されている場合、高さが O(log N) を超える可能性があり、操作に対数時間よりも時間がかかります。

于 2016-01-03T16:55:44.583 に答える