ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
21
—
если требуемый индекс меньше, то алгоритм продолжается
рекурсивно в левом поддереве;
—
если индекс уменьшается на значение в узле, то алгоритм про-
должается рекурсивно в правом поддереве.
Рис. 1. Структура FastArray
Сложность операции доступа к элементу по индексу составляет
O
(
log
2
N
).
Удаление элемента по индексу (рис. 2,
б
)
происходит путем про-
хождения от корня к листу и сравнения требуемого индекса со значе-
нием в узле:
—
если найден элемент, то он удаляется и все узлы на пути от
корня с одним потомком также удаляются;
—
если требуемый индекс меньше, то значение в узле декремен-
тируется и алгоритм продолжается рекурсивно в левом поддереве;
—
если индекс уменьшается на значение в узле, то алгоритм про-
должается рекурсивно в правом поддереве.
Сложность операции удаления элемента по индексу —
O
(
log
2
N
).
Вставка элемента по индексу (рис. 2,
в
)
также осуществляется пу-
тем прохождения от корня к листу и сравнения требуемого индекса
со значением в узле:
—
если найден элемент, на место которого необходимо вставить
новый элемент, то на его месте образуется поддерево с узлом и еди-
ничным значением, новым элементом в качестве левого потомка и
текущим элементом в качестве правого потомка;
—
если индекс меньше, то значение в узле инкрементируется и
алгоритм продолжается рекурсивно в левом поддереве;
—
если индекс уменьшается на значение в узле, то алгоритм про-
должается рекурсивно в правом поддереве.
Обратим внимание, что индексы всех элементов, расположенных
«
справа» от нового элемента, сдвигаются «автоматически».
Сложность операции вставки по индексу —
O
(
log
2
N
).
Данная структура обладает отличными свойствами.