算法：插入在跳躍列表

Question

怎樣的算法插入跳躍列表是什麼樣子？

通常像this在谷歌搜索時，但奇怪的是我似乎無法找到任何東西在我的書或在互聯網上有用將彈出。

我能找到的唯一的事情是如何跳錶的工作解釋。

Answer 1

首先，我們需要找到新元素的位置（我稱之爲一個鍵）。

我們這樣來做：

1. 讓我們從最高層開始看到鏈接指向我們。如果它導致列表的末尾或大於該鍵的數字，我們需要降低一級。否則，我們按照這個鏈接並重復該鏈接引導到的節點的過程。

2. 每當我們不能跳躍時，水平就會降低，並且每次我們都可以增加列表中的位置，所以在有限的步數之後，我們將達到零等級和一個從數字小於鍵數大於鍵的鍵。這正是應該插入密鑰的地方。

現在是它的時間來插入它。

1. 讓我們隨機生成新節點的「高度」。

2. 當我們在搜索過程中遍歷列表，我們可以保持存儲最右邊的鏈接，每一個給定的高度數組。

3. 對於從0到「height」的每個級別，我們創建一個從該節點到最右邊鏈接指向的節點的鏈接，並將最右邊的鏈接重定向到新創建的節點。

我沒有提及如何處理相同的元素。無論如何我們可以插入密鑰（如果我們想存儲重複的），或者只是忽略它。

這裏是插入功能的僞代碼：

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