Was Sie nicht zu verstehen ist, dass jeder Knoten einen Link auf der Ebene hat 1 Das heißt, auf der untersten Ebene ist die Datenstruktur im Wesentlichen eine verkettete Liste. Das Suchen nach einem Knoten unter Verwendung dieses ist natürlich eine O (n) -Operation.
Jeder Knoten der Sprungliste hat mindestens ein Link: den einen auf Stufe 1. Im Durchschnitt die Hälfte der Knoten auch einen Link auf der Ebene haben 2. Wenn dies der höchste Wert war, bei dem ein Link existiert, dann könnten Sie einen beliebigen Knoten in O (n/2) finden. Grundsätzlich folgen Sie den Knoten der 2. Ebene, bis Sie entweder das gesuchte Objekt gefunden haben oder bis Sie zu einem Knoten gelangen, dessen Wert größer ist als der gesuchte. An diesem Punkt gehen Sie zu den Knoten der Ebene 1 und suchen vom vorherigen Knoten (d. H. Der, der kleiner ist als der gesuchte).
Wiederum durchschnittlich, 1/4 der Knoten haben eine Verbindung auf Ebene 3. Mit diesen können Sie einen beliebigen Knoten in O (n/4) finden. Sie durchsuchen zuerst die Knoten der Ebene 3, bis Sie entweder den Knoten finden oder darüber hinausgehen und dann von diesem Punkt auf die Knoten der Ebene 2 und zu den Knoten der Ebene 1 gelangen, wenn der Knoten nicht auf Ebene 2 gefunden wird.
Wenn Sie den Berechnungen folgen, können Sie sehen, dass Ihr maximales Level m ist. Solange Sie weniger als 2^m Knoten in der Überspringungsliste haben, beträgt Ihre amortisierte durchschnittliche Suchzeit O (log2 (n)), wobei n ist die Anzahl der Elemente in der Liste.
So ist die Struktur einer Sprungliste Knoten ist wie folgt:
SkiplistNode
{
int level;
SomeType data; // the data held in the node
SkiplistNode* forwards[]; // an array of 'level' forward references
}
Wenn ein Knoten einen level Wert von 1 hat, dann wird es nur ein Element in dem forwards Array sein. Wenn es auf der Ebene 4 ist, dann gibt es vier Einträge werden: eine für jede der Stufen 4, 3, 2 und 1.
Wie sich herausstellt, die durchschnittliche Größe des Arrays ist forwards 2. die folgt die Progression 1 + 1/2 + 1/4 + 1/8 + 1/16, + 1/32, ... das heißt:
Every node has a link at level 1
1/2 of the nodes have a link at level 2
1/4 of the nodes have a link at level 3
1/8 of the nodes have a link at level 4
etc.
ist das jetzt mehr klar?
Ich vermute, das ist Hausaufgabensache. Kannst du deine Frage klarer stellen? –
eigentlich ist es keine Hausaufgaben, ich habe gerade die lec und vergeblich versuchend, die Vorteile der Skip-Liste zu verstehen, vor allem, wie es einfügen und löschen –
ich lese diese Aussage in einem Papier der Skip-Liste. –