ПРИНЦИПЫ ОРГАНИЗАЦИИ СТРУКТУРЫ ДАННЫХ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ И БЫСТРОЙ ОПЕРАЦИЕЙ ВСТАВКИ ИЛИ УДАЛЕНИЯ

структура данных произвольный доступ вставка удаление.

ПРОПУСКНЫЕ ДОКУМЕНТЫ ИНТЕГРИРОВАНННЫХ СИСТЕМ БЕЗОПАСНОСТИ, ФУНКЦИОНАЛЬНЫЕ ПОДСИСТЕМЫ И ЭЛЕМЕНТЫ АВТОМАТИЧЕСКОЙ СИСТЕМЫ ПАСПОРТНОГО КОНТРОЛЯ ДЛЯ ПУНКТОВ ПРОПУСКА ЧЕРЕЗ ГОСУДАРСТВЕННУЮ ГРАНИЦУ РОССИЙСКОЙ ФЕДЕРАЦИИ, ...

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

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт