algorithm - スキップ リストのマージ

Question

Skip lists指定された 2つ (それぞれ n 個のキーを持つ) を時間の複雑さ (最悪の場合) で 1 つSkip ListにO(n)マージするにはどうすればよいですか?

アルゴリズムを探しているだけです - 特定の実装/言語はありません。

Answer 1

store the two skip lists in two arrays: A,B
merge the arrays.
repeat until getting into root ('top' is a linked list containing only one element): 
   for each second entry in the skip list 'top' add a 'tag' (link 'upstairs' of the previous level)

store と merge は O(n) であるため、実際には O(n) であり、ループでは反復処理が必要です。

n+n/2+n/4+n/8+... = sigma(n/2^k) where k in (0,infinity) = 2n