20
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
УДК 004.9
М.В. Виноградова, Э.Г. Игушев
ПРИНЦИПЫ ОРГАНИЗАЦИИ
СТРУКТУРЫ ДАННЫХ
С ПРОИЗВОЛЬНЫМ ДОСТУПОМ
И БЫСТРОЙ ОПЕРАЦИЕЙ ВСТАВКИ
ИЛИ УДАЛЕНИЯ
Сформулирована задача разработки структуры данных с произволь-
ным доступом и с меньшим временем удаления, чем у обычного мас-
сива, а также предложены принципы ее решения.
E-mail:
vinogradova.m@gmail.com
Ключевые слова
:
структура данных, произвольный доступ, вставка,
удаление.
Введение.
Существуют две базовые структуры организации дан-
ных: массив и список. Массив — структура с произвольным доступом к
данным, но с трудоемкой линейной операцией вставки или удаления.
Список — структура с последовательным доступом к данным, имеющая
быструю константную операцию вставки или удаления.
В настоящее время различные задачи в информационных техноло-
гиях предъявляют все большие требования к структурам данных.
Например, при поиске по сети Интернет после формирования списка
документов, его необходимо пропустить через фильтр для удаления не-
которых записей. Во время обхода сети Интернет поисковым роботом
вследствие неправильного конфигурирования системным администра-
тором прав доступа какого-либо ресурса робот может записать в базу
личные данные пользователей этого ресурса или другие данные, кото-
рые не должны быть в поисковой выдаче. Однако поисковая база об-
новляется в лучшем случае раз в сутки, а документы должны быть уда-
лены из выдачи немедленно после выявления подобного факта. Для
этого и разработан фильтр, удаляющий некоторые документы из выда-
чи на последнем этапе фильтрации. Подобное удаление происходит
редко, однако оно не должно влиять на скорость, так как формирование
осуществляется в режиме реального времени [2]. Кроме того, получен-
ная структура данных с множеством документов требует произвольного
доступа к ее элементам. Поэтому была сформулирована задача разра-
ботки структуры данных с произвольным доступом и с меньшим вре-
менем удаления, чем у обычного массива.
Аналоги и прототипы.
Структура
FastArray
(
рис. 1) представля-
ет собой бинарное дерево, в одних узлах которого записаны элемен-
ты, а в других — количество листьев в левом поддереве [4].
Доступ к элементу по индексу (рис. 2,
а
)
осуществляется путем
прохождения от корня к листу и сравнения требуемого индекса со
значением в узле:
—
если найден требуемый элемент, то алгоритм закончен;