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