1

N 個のノードを持ち、すべての内部ノードが p 個の子を持つ一定の (一度構築されると変更されない) バランス ツリーがあるとします。明らかに、ノードにアクセスするための最悪のシナリオは logp(N) です。しかし、r 個のノードにアクセスするための償却コストはどうでしょうか? それらに昇順でアクセスするとどうなるでしょうか (検索ツリーを使用)。それはただの (logp(N))/r ですか?

4

1 に答える 1

0

バランスの取れた検索ツリー内のすべての要素にアクセスするための償却コストを確実に計算できます。ただし、「ほぼすべて」のノードがツリーの一番下にあることがわかります。(より正確には、完全なp-ary ツリー1/pの場合、ノードは葉ではありません)。したがって、すべてのアクセスの平均コストは、(おおよそ) リーフ アクセスのコスト ( ) になり、最悪の場合のコストと同じになります。logpn

于 2013-03-12T00:22:52.833 に答える