Что вы не понимаете, так это то, что каждый узел имеет ссылку на уровне 1. То есть на самом низком уровне структура данных по сути представляет собой связанный список.Поиск узла, использующего это, является, конечно, операцией O (n).
Каждый узел списка пропусков имеет , по крайней мере, одну ссылку: одну на уровне 1. Вкл.в среднем , половина узлов также имеет ссылку на уровне 2. Если это был самый высокий уровень, на котором существовала ссылка, то можно найти произвольный узел в O (n / 2).По сути, вы следуете за узлами 2-го уровня, пока либо не найдете нужный элемент, либо пока не доберетесь до узла, значение которого больше, чем искомый.В этот момент вы переходите на узлы уровня 1 и ищете вперед от предыдущего узла (то есть того, который меньше, чем тот, который вы ищете).
Опять в среднем, 1/4 отузлы имеют ссылку на уровне 3. Используя их, вы можете найти произвольный узел в O (n / 4).Сначала вы ищите узлы уровня 3, пока не найдете узел или не пройдете мимо него, а затем не спуститесь на узлы уровня 2 с этой точки и на узлы уровня 1, если не найдете узел уровня 2.
Если вы будете следовать математике, вы увидите, что если ваш максимальный уровень равен m, то, если в списке пропусков меньше 2^m узлов, среднее время поиска при амортизации будет равно O (log2 (n)), где n - количество элементов в списке.
Таким образом, структура узла списка пропуска выглядит следующим образом:
SkiplistNode
{
int level;
SomeType data; // the data held in the node
SkiplistNode* forwards[]; // an array of 'level' forward references
}
Если узел имеет level значение 1, тогда в массиве forwards будет только один элемент.Если он находится на уровне 4, тогда будет четыре записи: по одной для каждого из уровней 4, 3, 2 и 1.
Как выясняется, средний размер forwards массив равен 2. Это следует за последовательностью 1 + 1/2 + 1/4 + 1/8 + 1/16, + 1/32, ... То есть:
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.
Это более ясно сейчас?