Skip List: Inserts

Question

Ich versuche zu verstehen, wie eine Skip-Liste zum Einfügen funktioniert, aber wenn ich es herausziehe, funktioniert es nicht.

|-inf<---------------------------->+inf|0 
|-inf<--------->4<---------------->+inf|1 
|-inf<--------->4<--->9<--->11<--->+inf|2 
|-inf<--->1<--->4<--->9<--->11<--->+inf|3 

Also ich möchte 5 auf der oben verlinkten Liste einfügen.

Beginnen Sie in Zeile 0: Beginnen Sie bei -inf, vergleichen Sie 5 mit + inf, gehen Sie zur nächsten Zeile.

Verschieben auf Reihe 1:

Ist 5 < = 4, Nr. Vergleichen Sie mit dem, was rechts ist, + inf. Verschieben Sie von dem Element nach unten 4 2.

verschieben zu Zeile 2 Zeile:

Jetzt sind durchqueren wir zwischen 4 und 9, so dass der Vergleich wäre so etwas wie 5 < = 4? Nein. Ist 5 < = 9? Ja. Einfügen zwischen 4 und 9.

Aber jetzt 5 erscheint nicht in Zeile 3? Was mache ich falsch?

Answer 1

Wenn Sie sehen, dass 5 < = 9, müssen Sie weiter unten gehen, bis Sie den Boden erreichen. Es könnte irgendeine Zahl zwischen 4 und 9 noch in einer der unteren Ebenen sein. Wenn Sie seine Position in der unteren Zeile festlegen, fügen Sie sie dort ein und beginnen dann, sie um eine Zeile höher einzufügen, abhängig vom Ergebnis eines Zufallsgenerators. Die vollständige Sequenz für Ihre Einfügung ist dann etwa so:

1. 5> + inf? Nein: nach unten bewegen.
2. 5> 4? Ja: nach rechts bewegen.
3. 5> + inf? Nein: nach unten bewegen.
4. 5> 9? Nein: nach unten bewegen.
5. 5> 9? Nein: nach unten bewegen.
6. Konnte im vorherigen Schritt nicht nach unten verschieben, also zwischen 4 und 9 auf unterster Ebene einfügen.
7. Fügen Sie probabilistisch 5 zu höheren Zeilen hinzu.