ヒープ構造を実装する場合、位置 i にあるノードの子が位置 2i および 2i+1 にあるように、データを配列に格納できます。
私の質問は、配列を使用して二分探索木を表現し、代わりにポインターなどを処理しないのはなぜですか?
ありがとう
7975 次
7 に答える
8
個人的に
ポインタを使用すると、データ構造のサイズを動的に拡大するのが簡単になるためです。
ヒープよりもビンツリーを維持する方が簡単だと思います
ツリー内の要素のバランスを取り、削除し、挿入するアルゴリズムは、ポインターのみを変更し、ベクトルのように物理的に移動することはありません。
等々...
于 2010-01-08T13:40:02.470 に答える
7
すべての子の位置がそのように静的に事前計算されている場合、配列は基本的に完全に完全で完全にバランスの取れた二分木を表します。
「実生活」のすべての二分木が完全に完全でバランスが取れているわけではありません。特に長いブランチがいくつかある場合は、最下位レベルのすべてのノードに対応するために、配列全体を大幅に大きくする必要があります。
配列にバインドされたバイナリツリーがほとんど空の場合、配列スペースのほとんどが無駄になります。
木の枝の一部だけが配列の「下部」に到達するのに十分な深さである場合、多くのスペースが無駄になります。
ツリー（または1つのブランチ）が配列のサイズよりも「深く」成長する必要がある場合は、配列を「成長」させる必要があります。これは通常、より大きな配列へのコピーとして実装されます。これは時間のかかる操作です。
つまり、ポインタを使用すると、構造を動的かつ柔軟に拡張できます。配列でツリーを表現することは、優れた学術的演習であり、小さくて単純なケースではうまく機能しますが、多くの場合、「実際の」コンピューティングの要求を満たしません。
于 2010-01-08T13:39:21.467 に答える
7
主な理由は、再帰ツリーにより非常に単純なコードが可能になるためです。ツリーを配列にフラット化すると、再帰アルゴリズムが行う多くの簿記を行う必要があるため、コードは非常に複雑になります。
また、高さ N のツリーは、N と2^(N+1)-1ノード (。実際のノードのみがメモリを必要とします。配列を使用する場合は、スパース配列を使用しない限り、常にすべてのノード (空のノードも含む) にスペースを割り当てる必要があります。 (コードがさらに複雑になります) したがって、高さ 100 のまばらなツリーをメモリに保持するのは簡単ですが、20282409603651670423947251286008 バイトの RAM を割り当てることができるコンピューターを見つけるのは困難です。
于 2010-01-08T13:43:33.290 に答える
2
要素をヒープに挿入するには、要素を任意の場所に配置し、ヒープ制約が再び有効になるまで親と入れ替えます。Swap-with-parent は、ヒープのバイナリ ツリー構造をそのまま維持する操作です。これは、サイズ N のヒープが N セル配列として表され、対数時間で新しい要素を追加できることを意味します。
二分探索木は、ヒープ (子 2n および 2n+1) と同じ表現構造を使用してサイズ N の配列として表すことができますが、この方法で要素を挿入するのは非常に困難です。なぜなら、ヒープ制約とは異なり、二分探索はツリー制約では、バランスの取れたツリーを取得するために回転を実行する必要があります。したがって、対数よりも高いコストで N ノード ツリーを N セル配列に保持するか、ツリーをより大きな配列に保持することでスペースを浪費します (私の記憶が役立つ場合、レッドバック ツリーはアレイの 50% を無駄にします)。
したがって、配列内の二分探索木は、内部のデータが定数である場合にのみ興味深いものになります。そうであれば、ヒープ構造 (子 2n および 2n+1) は必要ありません。配列を並べ替えて、バイナリ検索を使用するだけです。
于 2010-01-08T13:44:48.833 に答える
0
私の知る限り、配列を使用して二分探索木を表すことができます。ただし、ポインタを使用する方が柔軟性があります。
于 2010-01-08T13:38:37.090 に答える
0
配列ベースの実装は、グラフ アルゴリズムで優先キューとして使用されるヒープが必要な場合に便利です。その場合、ヒープ内の要素は一定で、一番上の要素をポップして新しい要素を挿入します。最上位要素 (または最小要素) を削除するには、再びヒープになるように再調整する必要があります。これは、配列が適度にバランスされるように行うことができます。
これに関するリファレンスは、有向グラフで最適なネットワーク フローを効率的に計算することに関する Goldberg と Tarjan によるアルゴリズム、iirc です。
于 2010-01-08T13:52:35.563 に答える