Изменения

Все операции кроме <tex>\mathrm{order(p,q)}</tex> за <tex>O(1)</tex> может выполнить обычный [[Список|двусвязный список]], но с его помощью невозможно получить информацию о порядке объектов. Чтобы реализовать эту операцию, каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Таким образом, эти числа, которые в дальнейшим будут называться <b>метками</b>, задают порядок на элементах списка.

Ответить на запрос <tex>\mathrm{order(p,q)}</tex> можно за <tex>O(1)</tex>, просто сравнив метки <tex>p</tex> и <tex>q</tex>. Добавление меток никак не влияет на реализацию операции <tex>\mathrm{remove(p)}</tex>. Однако реализацию <tex>\mathrm{insert(p,q)}</tex> потребуется изменить: при добавлении нового элемента <tex>q</tex> после узла <tex>p</tex>, узлу <tex>q</tex> необходимо присвоить метку, которая строго больше предыдущего элемента и строго меньше следующего. В какой-то момент возникнет ситуация, что новой метки не найдётся, тогда метки можно перераспределить среди элементов списка так, чтобы для узла <tex>q</tex> хватило меткинашлась метка. Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.

Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>u</tex> {{---}} длина каждой метки, то для начала пусть <tex>u:\dfrac{n}{2}<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления или удаления элементов какому-то элементу не хватит метки, увеличим <tex>u</tex> перестанет удовлетворять неравенству, на <tex>1</tex> и пересчитаем все метки заново, распределив их равномерно. Заметим, что сразу после перераспределения меток, в среднем, между каждыми двумя элементами списка будет только одна свободная метка, так как при переходе к новому <tex>u</tex> количество меток будет примерно в два раза больше количества элементов списка. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с [[Динамический массив | саморасширяющимся массивом]]. Позже, в доказательстве времени работы, значение <tex>u</tex> будет несколько уточнено.

* <b>в листьях</b> {{---}} используется ли уже эта метка;

* <b>в нелистовых узлах</b> {{---}} является ли узел переполненным.

<b>Переполненным </b> назовем узел, для которого для любой <tex>1<\alpha<2</tex> выполнено <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. В листьях не хранится наличие переполненности, так как все листья всегда непереполнены. В крайнем случае для листа: <tex> \dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}} = 1 \ngtr 1 = \dfrac{1}{\alpha^{0}} = \dfrac{1}{\alpha^{\mathrm{height(x)}}} </tex>.