CS の多くのデータ構造はバイナリ (BST、ヒープなど) です。それらを非バイナリ形式で実装する正当な理由は何ですか? すなわち。ノードごとに 3 つの子を持つヒープを持つなど。
3 に答える
2
ノードごとに 3 つ以上の子を持つツリーは、ノードごとのリンクが増える代わりに深さが浅くなるため、トレードオフになります。データベースやファイルシステムで一般的に使用される B ツリーは、ノードごとに複数のリンクを持つツリー構造の典型的な例です。B ツリー ノードのサイズは、ファイル システム ブロックまたはクラスターのサイズと厳密に一致するように調整できるため、この構造はファイル システムに適しています。
于 2012-07-15T22:38:20.327 に答える
1
操作がバイナリの場合、バイナリデータ構造を使用します。操作が3値の場合、3値のデータ構造を使用します。バイナリデータ構造が一般的である理由の1つは、ほとんどの操作がバイナリであるためです。たとえば、4つの要素を比較する場合は、一度に2つの要素を比較します。と同じ+,-,*,/です。たとえば、赤黒木であるJavaのTreeSetまたはTreeMapを取り上げます。コンパレータを提供し、以下を実装します。
compare(T o1, T o2)
これは、2つの引数を比較する二項演算です。
于 2012-07-16T05:54:21.753 に答える
1
二分木には、比較的大きなスペースのオーバーヘッドがあります。たとえば、集合を実装する二分探索木のノードにはkey、leftとの 4 つのフィールドが含まれますright。key本当に関心があるのは だけであり、ポインタleftとrightポインタはデータ構造の簿記にすぎないため、2/3 のオーバーヘッドになります。
対照的に、三分探索木ノードには 5 つのフィールドがありkey1ます。これはわずか 3/5 のオーバーヘッドであり、ノードが大きくなると、オーバーヘッドの相対的な量はさらに減少します。もちろん、ある時点で構造が大きくなりすぎて管理できなくなるため、より大きなノードから絞り出せるパフォーマンスの量には制限があります。その制限はアプリケーションによって異なります。key2leftmiddleright
(ノードが大きくなるにつれて低下するメモリ割り当てによって引き起こされるオーバーヘッドについても考慮していません。ノードが大きくなる理由は他にもあります。たとえば、2 ～ 3 ツリーは、二分探索ツリーよりも漸近的な複雑さが優れています。)
于 2012-07-15T22:44:40.013 に答える