algorithm - アルゴリズム: スキップ リストへの挿入

Question

スキップ リストに挿入するためのアルゴリズムはどのように見えますか?

通常、Google で検索するとこのようなものがポップアップ表示されますが、奇妙なことに、本やインターネットで役立つ情報を見つけることができないようです。

私が見つけることができる唯一のものは、スキップリストがどのように機能するかの説明です.

Answer 1

まず、新しい要素の位置を見つける必要があります (キーと呼びます)。

次のようにします。

1. 最上位レベルから始めて、リンクがどこにつながるか見てみましょう。リストの最後またはキーよりも大きい番号につながる場合は、1 レベル下に移動する必要があります。それ以外の場合は、このリンクをたどって、このリンクが導くノードの手順を繰り返します。

2. ジャンプできなくなるたびにレベルが下がり、できるたびにリスト内の位置が増えるので、有限数のステップの後、レベル 0 に到達し、キーより小さい数字からつながるリンクに到達します。キーより大きい数値にします。まさにキーを挿入する場所です。

今度はそれを挿入します。

1. 新しいノードの「高さ」をランダムに生成してみましょう。

2. 検索中にリストをトラバースすると、特定の高さごとに右端のリンクを格納する配列を保持できます。

3. 0 から「高さ」までの各レベルについて、このノードから右端のリンクが指すノードへのリンクを作成し、右端のリンクを新しく作成されたノードにリダイレクトします。

等しい要素をどうするかについては言及しませんでした。とにかく（重複を保存したい場合）キーを挿入するか、単に無視することができます。

挿入関数の疑似コードは次のとおりです。

class Node {
    // an array of links for levels from 0 to the height of this node
    Node[] next; 
    int key; 

    Node(int height, int key) {
        key = key;
        next = new Node[height + 1];
    }
}

// I assume that the list always has two nodes: head and tail, which do not
// hold any values

void insert(int newKey) {
    // The rightmost node for each level such that the node itself has a key 
    // less than newKey but the node which the link points to has a larger key. 
    rightMostForLevel = new Node[maxLevel + 1]
    fill(leftMostForLevel, head)
    curLevel = maxLevel
    curNode = head
    // We need to find a node with the largest key such that its key is less
    // than or equal to the newKey, but the next node in the list is either 
    // equal to the tail or a has a greater key. 
    // We are done when the level is equal to zero and the next node has 
    // a key greater than newKey.
    while (curLevel != 0 
            or (curNode.next[curLevel] != tail and curNode.next[curLevel] <= key)) {
        if (curNode.next[curLevel] == tail or curNode.next[curLevel].key > key) {
            // We cannot make the jump (its too "long")
            // So we go one level lower
            curLevel--
        } else {
            // Otherwise, we make the jump
            curNode = curNode.next[curLevel]
            // And update the rightmost node for the current level
            rightMostForLevel[curLevel] = curNode
        }
    }  
    // Now we know where the new node should be inserted 
    newHeight = random height
    newNode = new Node(newHeight, newKey)
    // All we need to do is to update the links
    for (level = 0; level <= newHeight; level++) {
        // We "cut" the links that go through the new node
        newNode.next[level] = rightMostForLevel[level].next[level] 
        rightMostForLevel[level].next[level] = newNode  
    }
}