Algorithmus: Einfügen in Skip-Liste

Question

Wie sieht der Algorithmus zum Einfügen in Skip-Liste aus?

Normalerweise würde so etwas wie this bei der Suche auf Google erscheinen, aber merkwürdigerweise finde ich nichts hilfreiches in meinem Buch oder im Internet.

Das einzige, was ich finden kann, sind Erklärungen, wie Skip-Listen arbeiten.

Answer 1

Zuerst müssen wir eine Position für das neue Element finden (ich werde es einen Schlüssel nennen).

Wir tun es auf diese Weise:

1. Lassen Sie sich von der höchsten Ebene starten und sehen, wohin der Link führt uns. Wenn es zum Ende der Liste oder zu der Zahl führt, die größer als der Schlüssel ist, müssen wir eine Ebene tiefer gehen. Ansonsten folgen wir diesem Link und wiederholen den Vorgang für den Knoten, zu dem dieser Link führt.

2. Der Pegel wird jedes Mal verringert, wenn wir keinen Sprung machen können, und die Position in der Liste wird jedes Mal größer. Nach einer endlichen Anzahl von Schritten erreichen wir dann die Ebene Null und eine Verknüpfung, die von einer Zahl führt ist kleiner als ein Schlüssel zu der Zahl, die größer als der Schlüssel ist. Es ist genau dort, wo der Schlüssel eingefügt werden sollte.

Jetzt ist es Zeit, es einzufügen.

1. Lassen Sie uns zufällig die "Höhe" des neuen Knotens erzeugen.

2. Wenn wir die Liste während der Suche durchlaufen, können wir ein Array behalten, das den Link ganz rechts für jede gegebene Höhe speichert.

3. Für jede Ebene von 0 bis "height" erstellen wir eine Verknüpfung von diesem Knoten zu dem Knoten, auf den der Link ganz rechts zeigt und den Link ganz rechts zu einem neu erstellten Knoten umleitet.

Ich habe nicht erwähnt, was mit gleichen Elementen zu tun ist. Wir können den Schlüssel trotzdem einfügen (wenn wir Duplikate speichern wollen) oder einfach ignorieren. Hier

ist ein Pseudo-Code der Insert-Funktion:

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