算法：在跳跃列表中插入

Question

在跳跃列表中插入的算法是怎样的？

通常在 google 上搜索时会弹出类似 this 的内容，但奇怪的是，我似乎无法在我的书或互联网上找到任何有用的东西。

我唯一能找到的是关于跳过列表如何工作的解释。

Answer 1

首先，我们需要为新元素找到一个位置（我称之为键）。

我们这样做：

让我们从最高层开始，看看link将我们引向何方。如果它导致列表的末尾或大于键的数字，我们需要向下一级。否则，我们将遵循此 link 并针对此 link 引导我们到达的节点重复该过程。
每当我们无法跳跃时，级别就会降低，而每次我们可以跳跃时，列表中的位置就会增加，所以在有限的步数之后，我们将达到零级和 link 从小于键的数字引出大于键的数字。这正是应该插入钥匙的地方。

现在是时候插入它了。

让我们随机生成新节点的"height"。
当我们在搜索过程中遍历列表时，我们可以保留一个数组，该数组存储每个给定高度的最右边link。
对于从0到"height"的每一层，我们创建一个从这个节点到最右边的link指向的节点的link，并重定向最右边的link到新创建的节点。

我没有提到如何处理相等的元素。我们可以插入密钥（如果我们想存储重复项），或者忽略它。

下面是插入函数的伪代码：

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  
    }
}

算法：在跳跃列表中插入

Algorithm: Insertion in skip list

algorithm

computation-theory

skip-lists