algorithm - リストをスキップしないでください。配列と同じ制限がありますか?

Question

「n」（格納する要素の数）を事前に知っていれば、配列のようなスキップリストは非常に効率的であると言うのは正しいでしょうか？

スキップ リストの最大レベルは です。スキップ リスト(log n + 1)を作成する前に最大レベルを知る必要があるため、格納される要素の数を把握する必要があります。

Answer 1

サイズが正確にmaxlevel. maxlevelはおよそであるためlog N、頭部のサイズ変更はめったに行われず、発生した場合でもほとんど作業は必要ありません。それを本当に避けたい場合は、最初に使用可能なストレージ全体に十分な容量を持つヘッドを作成できますが、スキップリストのほとんどが数百の要素である場合、これはスペースの無駄になります。

スキップリストの検索手順がレベルを上げないため、これはすべて機能します。ダウンのみ。そのため、既存のノードよりも高いレベルの新しいノードを挿入する場合、ヘッドを除いて既存のノードを変更する必要はありません。ヘッドは、新しいノードの最高レベルを指すように変更する必要があります。(そうしないと、新しいレベルが役に立たなくなります。)

興味深い実装の詳細として、ノードのサイズを保存する必要はありません。ノードがレベルで指されているという事実は、ノードがi少なくともレベルを持っていることを示すのに十分であるため、ノードのサイズとi比較する必要はありません。i頭のサイズだけを知る必要があります。

Answer 2

maxlevel は動的に増やすことができます。

maxlevel=2^(n-1)最初の (2^n-1) ノードに使用します。2^n ノードが来ると が割り当てられlevel=2^n、次の 2^n...2^(n+1) ノードは を使用しますmaxlevel=2^n。