質問がここにあるのか、プログラマー (または他の SE サイト) にあるのかはわかりませんが、バランスの取れたバイナリ ツリーとインデックス可能なスキップリストの関連する違いに興味がありました。この問題は、この質問のコンテキストで発生しました。ウィキペディアから：
スキップ リストは確率的なデータ構造であり、多くのアプリケーションで選択される実装方法としてバランス ツリーに取って代わる可能性が高いと思われます。スキップ リスト アルゴリズムは、バランス ツリーと同じ漸近的な期待時間境界を持ち、より単純で高速で、使用するスペースが少なくなります。
スキップリストのスペース要件は、階層の深さに依存しませんか? そして、少なくとも検索に関しては、二分木の方が使いやすいのではないでしょうか? スキップリストのメリット/デメリットは他にもありますか?
(質問の一部 (使いやすさ、シンプルさなど) は少し主観的なものであり、この投稿の最後で回答します。)
スペースの使い方を見てみましょう。まず、n 個のノードを持つ二分探索木があるとします。必要な総スペース使用量は? 各ノードには、いくつかのデータと 2 つのポインターが格納されます。残高情報を維持するために、ある程度の情報が必要になる場合もあります。これは、総スペース使用量が
n * (2 * sizeof(ポインタ) + sizeof(データ) + sizeof(残高情報))
それでは、同等のスキップリストについて考えてみましょう。スキップリストによって使用されるメモリの実際の量はノードの高さに依存するというあなたの意見はまったく正しいですが、スキップリストによって使用される予想されるスペースの量について話すことができます。通常、スキップリストのノードの高さは、1 から始めて、公正なコインを繰り返し投げ、表を裏返す限り高さを増やし、裏を裏返すとすぐに停止することによって選択します。この設定が与えられた場合、スキップリスト内の予想されるポインターの数は?
確率論からの興味深い結果は、確率 p の一連の独立したイベントがある場合、そのイベントが発生する前に (期待に基づいて) 約 1 / p の試行が必要であるということです。コイン投げの例では、表が出るまでコインを投げます。コインは公正なコイン (50% の確率で表が出る) であるため、裏が出るまでに必要な予想試行回数は 2 です。最後のフリップで成長が終了するため、スキップリストでノードが成長する回数は 1 回と予想されます。したがって、平均的なノードには 2 つのポインターしかないと予想されます。1 つの初期ポインターと 1 つの追加ポインターです。これは、予想される合計スペース使用量が
n * (2 * sizeof(ポインタ) + sizeof(データ))
これを平衡二分探索木のノードのサイズと比較してください。バランス情報を格納するためにゼロ以外の量のスペースが必要な場合、skiplist は (予想に基づいて) バランス BST よりも少ないメモリを実際に使用します。バランスの取れた BST の多くのタイプ ( treap など) は多くのバランス情報を必要とすることに注意してください。他のもの ( red/black trees、AVL trees ) はバランス情報を持っていますが、その情報をポインターの下位ビットに隠すことができます。 ( splay trees ) バランス情報はまったくありません。したがって、これは保証された勝利ではありませんが、多くの場合、スペースを使用します。
シンプルさ、使いやすさなどに関する他の質問については、それは本当に状況によって異なります。個人的には、スキップリストで検索を行うコードよりも、BST で要素を検索するコードの方がはるかに簡単だと思います。ただし、バランスの取れた BST のローテーション ロジックは、多くの場合、スキップリストの挿入/削除ロジックよりもかなり複雑です。参考文献を参照せずに赤/黒ツリーで考えられるすべての回転ケースをガタガタ鳴らすことができるかどうかを確認してみてください。そういう意味では、スキップリストに挿入したり、スキップリストから削除したりするためのロジックを覚える方が少し簡単かもしれません。
お役に立てれば！
これまでに言及されていないことは、スキップ リストが同時操作に有利になる可能性があることです。Doug Lea が作成した ConcurrentSkipListMap のソースを読んだら、コメントを掘り下げてください。それは言及しています：
検索ツリーのための既知の効率的なロックフリーの挿入および削除アルゴリズムはありません。インデックス ノードの「ダウン」リンクの不変性 (トゥルー ツリーの変更可能な「レフト」フィールドとは対照的に) は、CAS 操作のみを使用してこれを扱いやすくします。
これが完璧なフォーラムではないことは間違いありません。
あなたが引用したコメントは、元のスキップリストの論文の著者によって書かれたものであり、偏りのない主張ではありません. それから 23 年が経ちましたが、スキップ リストよりも赤黒木がまだ普及しているようです。例外は、データ構造の 1 つのオプションとしてスキップ リストを含むredis キーと値のペア データベースです。
スキップリストはとてもクールです。しかし、一般的なランダム化のケースで私が示すことができた唯一のスペースの利点は、バランス フラグを格納する必要がないことです: 値ごとに 2 ビットです。これは、バイナリ ツリーのパフォーマンスを複製するのに十分なほど階層が密集していることを前提としています。これは、決定論の代償と考えることができます (副ランダム化)。SL の優れた機能は、密度の低い階層を使用して、速度の一定の要素をスペースと交換できることです。
補足: ソートされた順序でトラバースする必要がない場合、キーを暗号化するだけで不均衡なバイナリ ツリーをランダム化できることはあまり議論されません (つまり、RC4 のような非常に単純なものを使用して疑似ランダム暗号テキストにマッピングします)。このようなツリーの実装は非常に簡単です。