390
правок
Изменения
Нет описания правки
* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>)
'''node''' insert ('''node''' i, '''K''' key, '''T''' data)
'''while''' i.key <= key <font color=darkgreen>// Ищем подходящее место</font>
'''void''' insert ('''list''' skip_list, '''K''' key, '''T''' data) <font color=darkgreen>// Обёрточка</font>
insert(skip_list.head, key, data)
'''void''' erase ('''node''' i, '''K''' key)
'''if''' i == ''null''
'''void''' erase ('''list''' skip_list, '''K''' key) <font color=darkgreen>// Обёрточка</font>
erase(skip_list.head, key)
==Псевдокод==Наглядный, но не очень эффективный по памяти вариант списка с пропусками. В узлах списка хранятся:* <tex>next</tex> {{---}} следующий узел* <tex>down</tex> {{---}} тот же узел на следующем уровне* <tex>data</tex> {{---}} данные типа T* <tex>key</codetex> {{---}} ключ типа K
==Применение==
* Базы данных
