Алгоритм: Вставка в список пропусков

Question

Как выглядит алгоритм вставки в список пропусков?

Обычно что-то вроде this появляется при поиске в google, но, как ни странно, я не могу найти ничего полезного в своей книге или в Интернете.

Единственное, что я могу найти, это объяснения того, как работают списки пропуска.

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