今日、フェンウィック ツリー (バイナリ インデックス ツリー) についての講義を聞きました。先生は、このツリーは区間ツリーとセグメント ツリーの一般化であると言いましたが、この 3 つのデータ構造の実装は異なります。この断言は本当ですか？なぜ？
4457 次
2 に答える
11
次の分類は賢明なようですが、さまざまな人々がこれらの用語を混同することになります。
フェニック木/バイナリインデックスツリー リンク
単一の配列とバイナリ表現の演算を使用してプレフィックスの合計（累積合計とも呼ばれます）を格納するもの。要素はモノイドのメンバーになることができます。
レンジツリー リンク
各ノードが特定の範囲のサブ範囲、たとえば[0、N]を表すツリーのファミリー。区間の結合演算を計算するために使用されます。
区間木 リンク
実際の間隔を保存するツリー。最も一般的には、中点を取り、ノードで交差する間隔を維持し、ポイントの左側と右側の間隔に対してプロセスを繰り返します。
セグメントツリー リンク
葉が離散的ではなく、おそらく連続的な空間の基本区間であり、より高いノードが基本区間の和集合である範囲ツリーに似ています。ポイントの包含をチェックするために使用されます。
于 2012-12-26T08:54:01.987 に答える
6
バイナリ インデックス ツリーが何かの一般化と呼ばれているのを聞いたことがありません。これは確かに、区間ツリーとセグメント ツリーの一般化ではありません。リンクをたどって、これを納得させることをお勧めします。
このツリーよりも、インターバル ツリーとセグメント ツリーの一般化です
もしあなたの先生が「この木」で「二分索引の木」を意味していたとしたら、彼は間違っています。
しかし、この 3 つのデータ構造の私の実装は異なります
もちろん、それらは異なります。教師は、そうすべきではないとは決して言いません。彼は、一方が他方の一般化であると言っただけです（これは真実ではありませんが、それでも）。いずれにせよ、実装は異なるはずです。
同じ実装を持つのは、バイナリ インデックス ツリーとフェンウィック ツリーです。これらは同じものだからです。
于 2010-05-09T06:17:13.847 に答える