data-structures - RBツリー、BツリーまたはAVLツリーをいつ選択しますか？

Question

プログラマーとして、RBツリー、Bツリー、またはAVLツリーの使用をいつ検討する必要がありますか？選択を決定する前に考慮する必要がある重要なポイントは何ですか？

重要なポイントを参照して、なぜそれが他のものよりも選ばれるのか、各ツリー構造のシナリオで誰かが説明できますか？

Answer 1

塩のピンチでこれを取ります：

数千を超えるアイテムを管理していて、ディスクまたは低速のストレージメディアからそれらをページングしている場合のBツリー。

ツリーでかなり頻繁に挿入、削除、および取得を行う場合のRBツリー。

挿入と削除が検索に比べてまれである場合のAVLツリー。

Answer 2

B +ツリーは、メインメモリ内であっても、優れた汎用の順序付きコンテナデータ構造であると思います。仮想メモリが問題ではない場合でも、キャッシュの使いやすさが問題になることがよくあります。B+ツリーは、シーケンシャルアクセスに特に適しています。リンクリストと同じ漸近的なパフォーマンスですが、キャッシュの使いやすさは単純な配列に近いです。これらすべてとO（log n）は、検索、挿入、および削除を行います。

ただし、B +ツリーには問題があります。たとえば、挿入/削除を行うときにノード内でアイテムが移動したり、それらのアイテムへのポインタが無効になったりします。「カーソルのメンテナンス」を行うコンテナライブラリがあります。カーソルは、リンクリストで現在参照しているリーフノードにアタッチされるため、自動的に修正または無効化できます。カーソルが1つか2つを超えることはめったにないので、うまく機能しますが、それでも同じように余分な作業が必要になります。

もう1つのことは、B+ツリーは本質的にそれだけであるということです。必要かどうかに応じて、非リーフノードを削除または再作成できると思いますが、バイナリツリーノードを使用すると、柔軟性が大幅に向上します。バイナリツリーは、ノードをコピーせずにリンクリストに変換したり、元に戻したりできます。ポインタを変更するだけで、別のデータ構造として扱っていることを思い出してください。特に、これは、ツリーのO（n）マージが非常に簡単になることを意味します。両方のツリーをリストに変換し、それらをマージしてから、ツリーに変換し直します。

さらにもう1つは、メモリの割り当てと解放です。バイナリツリーでは、これをアルゴリズムから分離できます。ユーザーはノードを作成してから挿入アルゴリズムを呼び出すことができ、削除するとノードを抽出できます（ツリーからノードを切り離しますが、メモリを解放しないでください）。BツリーまたはB+ツリーでは、これは明らかに機能しません。データは複数アイテムのノードに存在します。必要な新しいノードの数がわかり、ノードを割り当てることができるようになるまで、ノードを変更せずに操作を「計画」する挿入メソッドを作成するのは困難です。

赤黒対AVL？それが大きな違いを生むかどうかはわかりません。私自身のライブラリには、ノードを操作するためのポリシーベースの「ツール」クラスがあり、二重リンクリスト、単純なバイナリツリー、スプレーツリー、赤黒木、およびさまざまな変換を含むtreapのメソッドがあります。それらのメソッドのいくつかは、私がいつか退屈したためにのみ実装されました。treapメソッドをテストしたかどうかさえわかりません。私がAVLではなく赤黒木を選んだ理由は、私が個人的にアルゴリズムをよりよく理解しているためです。つまり、アルゴリズムが単純であるという意味ではなく、私がそれらに精通しているのは単なる歴史のまぐれです。

最後にもう1つ、私はもともと実験としてB+ツリーコンテナを開発しただけです。それは本当に終わらない実験の1つですが、他の人に繰り返すように勧めるものではありません。必要なのが順序付けられたコンテナだけである場合、最良の答えは、既存のライブラリが提供するものを使用することです。たとえば、C++のstd::mapなどです。私のライブラリは何年​​にもわたって進化し、安定するまでにかなりの時間がかかりました。そして、比較的最近、技術的に移植性がないことを発見しました（WRT offsetofの未定義の動作に依存します）。

Answer 3

メモリ内のB-Treeには、アイテムの数が32000を超える場合に利点があります... stx-btreeのspeedtest.pdfを参照してください。

Answer 4

データ構造を選択するときは、次のような要素をトレードオフします。

• 検索の速度v更新の速度
• 構造が最悪の場合の操作、たとえばソートされた順序で到着するレコードの挿入にどれだけうまく対処できるか
• 無駄なスペース

まず、RobertHarveyが参照しているウィキペディアの記事を読みます。

実用的には、Javaなどの言語で作業する場合、平均的なプログラマーは提供されているコレクションクラスを使用する傾向があります。パフォーマンス調整アクティビティで、収集パフォーマンスに問題があることがわかった場合は、別の実装を探すことができます。これは、ビジネス主導の開発が最初に考慮しなければならないことはめったにありません。このようなデータ構造を手動で実装する必要があることは非常にまれです。通常、使用できるライブラリがあります。