Главная » Java, Структуры данных и алгоритмы » Операции обновления

0

Еще одной особенностью структуры данных списка, помимо элегантного поискового алгоритма, являются простые алгоритмы обновления словаря.

Ввод

Алгоритм ввода для skip-списка использует механизм генерации случайных чисел для определения количества ссылок на вводимый объект (к,е), добавляемых в список. Ввод нового объекта (к,е) в срисок начинается с выполнения операции SkipSearch(A;). В результате получаем позицию р нижнего левого объекта с наибольшим ключом, меньшим или равным к (р в этом случае может оказаться позицией специального объекта с ключом «-оо»). Затем (к,е) вводится в список нижнего уровня за позицией р. После ввода объекта «подбрасываем монетку», то есть вызываем метод random(), возвращающий случайное число в диапазоне между 0 и 1. Если это число меньше 1/2, переходим на один уровень вверх, вводим (к,е) в соответствующую позицию этого уровня и снова «подбрасываем монетку». Продолжаем до тех- пор, пока возвращаемое число не оказывается большим 1/2, после чего процесс прекращается. Затем все ссылки на новый объект (к,е), созданные в процессе ввода, связываются воедино, и для (к,е) создается башня.

Псевдокод алгоритма ввода для skip-списка 5цриэодится во фрагменте кода 8.5, а процесс его выполнения показан на рис. 8.11. Приведенный

Рис. 8.11. Ввод элемента с ключом 42 в список рис. 8.9 с применением трех ссылок на новый объект, полученных в результате «подбрасывания монетки». Проанализированные в процессе ввода позиции показаны мелким штрихом. Позиции, введенные для хранения нового объекта, отмечены крупным штрихом. Предшествующие им позиции отмечены флажками

алгоритм использует метод insertAfterAbove(/?,#,(/:,?)), который вводит позицию с объектом (к,е) после позиции р (на том же уровне, что и р) и над позицией q, возвращая позицию г нового объекта (и устанавливая внутренние ссылки так, что методы after, before, above и below для р, q и г работают правильно).

Алгоритм Skiplnsert(/:,e):

Input: объект (k,e); Output: отсутствует.

р SkipSearch(Zc)

q <- insertAfterAbove (p, null, (к, e)) {переход на нижний уровень} while random () < 1/2 do while above(p) = null do

p before(p) {сканирование} jd <r- above(p) {переход на уровень вверх} q insertAfterAbove (p, q, (к, ё)) {вставка нового объекта}

Фрагмент кода 8.5. Ввод в skip-список, при котором метод random() возвращает произвольное число от 0 до 1 и отсутствует выход за верхний уровень

Предполагаемое время выполнения алгоритма ввода составляет 0(log п), как это будет показано в п. 8.6.3.

Удаление

Как и алгоритмы поиска и ввода, алгоритм удаления из skip-списка S достаточно прост. Так, для выполнения операции removeElement(A;) вначале отыскивается запрацшваемый ключ к. Если позиция р с ключом к не найдена, возвращается элемент NO_SUCH_KEY. При наличии этой позиции (на нижнем уровне) удаляются все позиции над р, доступ к которым осуществляется с помощью операции above для прохождения вверх по ‘ башне объекта. Алгоритм удаления приведен на рис. 8.12, а его детальное описание оставлено для упражнения. Как будет показано в следующем разделе, время выполнения удаления в skip-списке должно составлять 0(log л).

Puc. 8.12. Удаление объекта с ключом 25 из skip-списка (рис. 8 Л1). Позиции, анализируемые после поиска позиции списка So, содержащей искомый объект, отмечены мелким пунктиром. Удаленные позиции показаны крупным пунктиром

Прежде чем перейти к анализу, отметим несколько усовершенствований в структуре данных skip-списка. Во-первых, нет нужды хранить ссылки к объектам на уровнях списка выше 0, так как они используются на этих уровнях как ссылки на ключи. Во-вторых, метод above можно не применять. Да и метод before также не особенно нужен. Ввод и удаление объекта можно выполнять сверху вниз при направленном вперед сканировании, экономя таким образом место для ссылок «вверх» и «вперед». Подробное описание такой оптимизации исследуется в упражнении. Ни одно из этих изменений не улучшает асимптотического выполнения skip-списка более чем на некоторый постоянный коэффициент, но с практической точки зрения в этом имеется определенный смысл. В принципе экспериментально можно доказать, что оптимизированный skip-список эффективнее AVL-деревьев или других сбалансированных поисковых деревьев, обсуждаемых в главе 9.

Предполагаемое время выполнения алгоритма удаления составляет 0{log п), что объясняется в п. 8.6.3.

Поддержка верхнего уровня

В skip-списке постоянно должна поддерживаться ссылка на верхнюю левую позицию S как на переменную экземпляра, а каждый новый ввод должен осуществляться через верхний уровень. В этой ситуации применяются два возможных подхода, каждый из которых имеет свои особенности.

Один из них предполагает ограничить верхний уровень h неким фиксированным значением п количества элементов, находящихся в текущий момент в словаре (из анализа будет видно, что h = max{10,2flog п\} впблне достаточно, a h =3pog«~| даже надежнее). Реализация такого способа потребует модификации алгоритма ввода, позволяющей прекратить ввод нового элемента при достижении самого верхнего уровня (если только riog п \ не будет меньше Поg(n + 1)1, что позволяет подняться как минимум на один уровень, так как увеличивается предел высоты).

Другой способ заключается во вводе нового элемента столько раз, сколько позволит метод random(). Как показано в анализе skip-списков, вероятность того, что ввод может превзойти 0(log п), достаточно мала, так что такая проектная модель тоже должна срабатывать.

Необходимо, чтобы любой из вариантов обеспечивал возможность поиска, ввода и удаления элементов за время 0(log п).

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии