Изменения

[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка команда операция <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]'''List order maintance''' (рус. <i>поддержка поддержание порядка в списке</i>) {{---}} проблема поддержки поддержания списка со следующими операциями:

* <tex>\mathrm{order(p, q)}</tex> {{---}} командаоперация, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.

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

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

Ответить на запрос <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>O(1)</tex> по аналогии с [[Динамический массив | саморасширяющимся массивом]]. Позже, в доказательстве времени работы, значение <tex>u</tex> будет несколько уточнено.

Все метки будут храниться в [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>u</tex> (там представлены не только используемые метки, а вообще все возможные заданной длины). Введем некоторые обозначения:* <tex>\mathrm{weight(x)}</tex> {{---}} количество помеченных (используемых) листьев (меток) в поддереве узла <tex>x</tex>;* <tex>\mathrm{size(x)}</tex> {{---}} количество всех листьев в поддереве <tex>x</tex>;* <tex>\mathrm{height(x)}</tex> {{---}} высота узла <tex>x</tex> в цифровом боре. Также в каждом узле дополнительно будет храниться:

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

Перераспределение меток потребуется выполнить в случае, когда для нового элемента нет не будет свободной метки. Ниже будет описан способ выполнения перераспределения меток: как только Пусть требуется вставить элемент выполнить операцию <tex>\mathrm{insert(p, q)}</tex>, которому не хватает меткино метка, следующая за меткой <tex>q</tex> уже присвоена элементу <tex>z</tex>. Тогда будем подниматься вверх от метки элемента, следующего за <tex>qz</tex>до тех пор, пока не будет найден первый непереполненный узел. Может случиться такое, что на всем пути до корня не встретится ни одного непереполненного узла. Чтобы этого избежать, уточним границы <tex>u</tex> будут уточнены позже. Как только будет найден первый непереполненный узел, переназначим метки в его поддереве этого узла так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого между занятыми метками будет не меньше <tex>\alpha^{\mathrm{height(x)}}</tex> свободных меток.

Ниже будут рассмотрены операции добавления более подробно, чтобы оценитьРассмотрим, как часто происходит перераспределение меток: * Если в поддереве узла было проведено перераспределение меток, то повторное перераспределение меток в поддереве узла <tex>x</tex> потребуется, когда сын этого узла снова переполнится. Если <tex>y</tex> {{---}} сын <tex>x</tex>, то он переполнится, когда <tex>\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, требуется, чтобы было сделано еще добавлений: <center><tex>\mathrm{size(y)} \cdot (\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex>;</center>  * С другой стороны, следующее перераспределение меток произойдет, когда <tex>\mathrm{weight(x)}</tex> станет больше

* Если в поддереве узла было проведено перераспределение меток, то повторное перераспределение меток в поддереве узла <tex>x</tex> потребуется, когда сын этого узла снова переполнится. Если <tex>y</tex> {{---}} сын <tex>x</texcenter>, то он переполнится, когда <tex>\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, требуется, чтобы было сделано еще <tex>\mathrm{size(y)} \cdot (\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - = \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = 2\mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> добавлений;.</center>

Получается, что за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций перераспределения меток требуется сделать <tex>\mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> операций добавления. Из этого следуетИспользуя [[Амортизационный анализ | метод предоплаты]], видно, что, если за каждую операцию добавления брать <tex>\dfrac{2}{\alpha-1}</tex> монет, то за добавления накопится достаточное количество монет, чтобы расплатиться за следующую операцию перераспределения в узле <tex>x</tex>.

Далее будут уточнены Для того, чтобы на пути к корню точно встретился непереполненный узел, требуется уточнить границы <tex>u</tex>, чтобы корень никогда не переполнялся: <tex>\dfrac{\mathrm{weight(root)}}{\mathrm{size(root)}} < \dfrac{1}{\alpha^{\mathrm{height(root)}}} \Rightarrow \dfrac{n}{2^u} < \dfrac{1}{\alpha ^u} \Rightarrow u \geqslant \log_{\frac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за <tex>O(\log n)</tex>.

Из-за того, что Выбор <tex>u\alpha</tex> зависит от выбранной сильно влияет на реализацию структуры, так как <tex>\alphau</tex>, зависит от выбранной <tex>\alpha</tex> сильно влияет на реализацию. Увеличивая <tex>\alpha</tex>, уменьшается стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличивается <tex>u</tex>, значит, требуется больше памяти, а, уменьшая <tex>\alpha</tex>, возникает выигрыш в памяти, но проигрыш во времени операции добавления. Так как для реализации структуры используется <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex>, требуется <tex>O(n)</tex> памяти.