たとえば、各ノードにサイズ値を追加するだけで、各ノードを簡単にランク付けしたり、k 次の統計情報を取得したりできることがわかっています。C++ STL セットのような言語実装よりも、他にどのような利点がありますか?
3 に答える
1
独自の BST をコーディングすることには多くの利点があります。
回答で述べたように、BST を拡張して、ローテーションで保持される各ノードに追加情報を保存できます。これは、インターバル ツリー、リンク/カット ツリーなどを構築するために使用できます。これは、そうでなければ、ブラック ボックスの標準コンテナーでは実行できませんでした。
さらに、独自のツリーを作成すると、バランスをとる方法を変更できます。たとえば、ルックアップに関連して挿入と削除がほとんどないことがわかっている場合は、赤/黒ツリーの代わりに AVL ツリーを使用できます。これらのツリーは高さが小さいためです。アクセス パターンが一様ではなく、スレッドが 1 つしかないという事実がわかっている場合は、スプレイ ツリーを使用できます。または、全体的なランタイムがすべて重要であることがわかっていて、マルチスレッドのルックアップが必要な場合は、スケープゴート ツリーを作成してみてください。
お役に立てれば！
于 2013-01-13T01:27:19.297 に答える
0
独自のデータ構造を実装する場合は、それをコーディングし、それが正しいことをテストし、実装が効率的であることを確認する必要があります。
これは STL コンポーネントで既に処理されているため、自分で車輪を再発明するよりも、既存の実装を再利用することをお勧めします。
于 2013-01-12T23:29:56.910 に答える