У java есть реализация списка пропуска. Списки с пропусками: вероятностная альтернатива сбалансированным деревьям С какого уровня начинать искать? Определение L(n)

Списки с пропусками - это структура данных, которая может применяться вместо сбалансированных деревьев. Благодаря тому, что алгоритм балансировки вероятностный, а не строгий, вставка и удаление элемента в списках с пропусками реализуется намного проще и значительно быстрее, чем в сбалансированных деревьях.

Списки с пропусками - это вероятностная альтернатива сбалансированным деревьям. Они балансируются с использованием генератора случайных чисел. Несмотря на то, что у списков с пропусками плохая производительность в худшем случае, не существует такой последовательности операций, при которой бы это происходило постоянно (примерно как в алгоритме быстрой сортировки со случайным выбором опорного элемента). Очень маловероятно, что эта структура данных значительно разбалансируется (например, для словаря размером более 250 элементов вероятность того, что поиск займёт в три раза больше ожидаемого времени, меньше одной миллионной).

Балансировать структуру данных вероятностно проще, чем явно обеспечивать баланс. Для многих задач списки пропуска это более естественное представление данных по сравнению с деревьями. Алгоритмы получаются более простыми для реализации и, на практике, более быстрыми по сравнению со сбалансированными деревьями. Кроме того, списки с пропусками очень эффективно используют память. Они могут быть реализованы так, чтобы на один элемент приходился в среднем примерно 1.33 указатель (или даже меньше) и не требуют хранения для каждого элемента дополнительной информации о балансе или приоритете.

Для поиска элемента в связном списке мы должны просмотреть каждый его узел:

Если список хранится отсортированным и каждый второй его узел дополнительно содержит указатель на два узла вперед, нам нужно просмотреть не более, чем ⌈n /2⌉ + 1 узлов(где n - длина списка):

Аналогично, если теперь каждый четвёртый узел содержит указатель на четыре узла вперёд, то потребуется просмотреть не более чем ⌈n /4⌉ + 2 узла:

Если каждый 2 i i узлов вперёд, то количество узлов, которые необходимо просмотреть, сократится до ⌈log 2 n ⌉, а общее количество указателей в структуре лишь удвоится:

Такая структура данных может использоваться для быстрого поиска, но вставка и удаление узлов будут медленными.

Назовём узел, содержащий k указателей на впередистоящие элементы, узлом уровня k . Если каждый 2 i -ый узел содержит указатель на 2 i узлов вперёд, то уровни распределены так: 50% узлов - уровня 1, 25% - уровня 2, 12.5% - уровня 3 и т.д. Но что произойдёт, если уровни узлов будут выбираться случайно, в тех же самых пропорциях? Например, так:

Указатель номер i каждого узла будет ссылаться на следующий узел уровня i или больше, а не на ровно 2 i -1 узлов вперёд, как было до этого. Вставки и удаления потребуют только локальных изменений; уровень узла, выбранный случайно при его вставке, никогда не будет меняться. При неудачном назначении уровней производительность может оказаться низкой, но мы покажем, что такие ситуации редки. Из-за того, что эти структуры данных представляют из себя связные списки с дополнительными указателями для пропуска промежуточных узлов, я называю их списками с пропусками .

Операции

Опишем алгоритмы для поиска, вставки и удаления элементов в словаре, реализованном на списках с пропусками. Операция поиска возвращает значение для заданного ключа или сигнализирует о том, что ключ не найден. Операция вставки связывает ключ с новым значением (и создаёт ключ, если его не было до этого). Операция удаления удаляет ключ. Также в эту структуру данных можно легко добавить дополнительные операции, такие как «поиск минимального ключа» или «нахождение следующего ключа».

Каждый элемент списка представляет из себя узел, уровень которого был выбран случайно при его создании, причём независимо от числа элементов, которые уже находились там. Узел уровня i содержит i указателей на различные элементы впереди, проиндексированные от 1 до i . Мы можем не хранить уровень узла в самом узле. Количество уровней ограничено заранее выбранной константой MaxLevel . Назовём уровнем списка максимальный уровень узла в этом списке (если список пуст, то уровень равен 1). Заголовок списка (на картинках он слева) содержит указатели на уровни с 1 по MaxLevel . Если элементов такого уровня ещё нет, то значение указателя - специальный элемент NIL.

Инициализация

Создадим элемент NIL, ключ которого больше любого ключа, который может когда-либо появиться в списке. Элемент NIL будет завершать все списки с пропусками. Уровень списка равен 1, а все указатели из заголовка ссылаются на NIL.

Поиск элемента

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

Search (list, searchKey)
x:= list→header
# инвариант цикла: x→key < searchKey
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
# x→key < searchKey ≤ x→forward→key
x:= x→forward
if x→key = searchKey then return x→value
else return failure

Вставка и удаление элемента

Для вставки или удаления узла применяем алгоритм поиска для нахождения всех элементов перед вставляемым (или удаляемым), затем обновляем соответствующие указатели:


В данном примере мы вставили элемент уровня 2.

Insert (list, searchKey, newValue)
local update
x:= list→header
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
# x→key < searchKey ≤ x→forward[i]→key
update[i] := x
x:= x→forward
if x→key = searchKey then x→value:= newValue
else
lvl:= randomLevel()
if lvl > list→level then
for i:= list→level + 1 to lvl do
update[i] := list→header
list→level:= lvl
x:= makeNode(lvl, searchKey, value)
for i:= 1 to level do
x→forward[i] := update[i]→forward[i]
update[i]→forward[i] := x

Delete (list, searchKey)
local update
x:= list→header
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
update[i] := x
x:= x→forward
if x→key = searchKey then
for i:= 1 to list→level do
if update[i]→forward[i] ≠ x then break
update[i]→forward[i] := x→forward[i]
free(x)
while list→level > 1 and list→header→forward = NIL do
list→level:= list→level – 1

Для запоминания элементов перед вставляемым(или удаляемым) используется массив update . Элемент update[i] - это указатель на самый правый узел, уровня i или выше, из числа находящихся слева от места обновления.

Если случайно выбранный уровень вставляемого узла оказался больше, чем уровень всего списка (т.е. если узлов с таким уровнем ещё не было), увеличиваем уровень списка и инициализируем соответствующие элементы массива update указателями на заголовок. После каждого удаления проверяем, удалили ли мы узел с максимальным уровнем и, если это так, уменьшаем уровень списка.

Генерация номера уровня

Ранее мы приводили распределение уровней узлов в случае, когда половина узлов, содержащих указатель уровня i , также содержали указатель на узел уровня i +1. Чтобы избавиться от магической константы 1/2, обозначим за p долю узлов уровня i , содержащих указатель на узлы уровня i +i. Номер уровня для новой вершины генерируется случайно по следующему алгоритму:

randomLevel ()
lvl:= 1
# random() возвращает случайное число в полуинтервале }