skiplist- мне действительно нужно объяснение, как оно вставляет и удаляет

Question

Я действительно не понимаю вероятностную вещь этого списка. в дополнение к утверждению «мы должны исследовать не более n/2 + 1 узлов (где n - длина списка). Также давая каждому четвертому узлу указатель четыре вперед (рис. 1c), требуется не более n/4 + 2 узла ». это заявление я читаю по следующей ссылке: ftp: //ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

Answer 1

Пропустить списки объясняются довольно хорошо в их Wikipedia article. Если у вас есть конкретный вопрос о структуре данных, не стесняйтесь спрашивать их.

Answer 2

Лекция из MIT о пропустить списки: http://video.google.com/videoplay?docid=-6710586843601387849#

Answer 3

Несколько легче понять объяснение можно найти здесь: http://igoro.com/archive/skip-lists-are-fascinating/

Answer 4

То, что вы не понимая, что каждый узел имеет ссылку на уровне 1 Т. Е. На самом низком уровне структура данных по существу является связанным списком. Поиск узла с использованием этого, конечно, является операцией O (n).

Каждого узел списка пропуска имеет по крайней мере один ссылки: один на уровне 1. В среднем, половина узлов также имеет ссылку на уровне 2. Если это был самый высокий уровень, на котором ссылка существовала, тогда вы могли бы найти произвольный узел в O (n/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. 

Является ли это более понятным сейчас?