Изменения

Список с командой порядка используется в разных алгоритмах и структурах, к примеру, в реализации полностью [[Персистентные структуры данных|персистентного дерева поиска]].

Рассмотрим реализацию списка с командой порядка, где все операции выполняются за амортизационную <tex>O(logn\log n)</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>\mathrm{order(p,q)}</tex> можно сделать, сравнив метки за <tex>O(1)</tex>. Теперь опишем Опишем взаимодействие с метками при выполнении других команд.операций:

* Для <b>операция порядка:</b> <tex>\mathrm{order(p,q)}</tex> можно сделать, просто сравнив метки за <tex>O(1)</tex> (так как они идут по возрастанию);* <b>удаление вершины:</b> для выполнения <tex>\mathrm{remove(p)}</tex> просто удалим элемент <tex>p</tex> вместе с его меткойза <tex>O(1)</tex> , проверим, удовлетворяет ли <tex>u</tex> неравенству, если нет {{---}} пересчитаем. ;* Для <b>добавление вершины:</b> для <tex>\mathrm{insert(p,q)}</tex> существуют два возможных случая:** Метка <tex>r</texb>есть свободная метка: <tex>\mathrm{r.label}>\mathrm{p.label} + 1</texb>проверим, где есть ли между элементом <tex>r</tex> {{---}} следующий и следующим за <tex>p</tex> элемент в спискеним элементом свободная метка. Тогда между метками <tex>p</tex> и <tex>r</tex> Если есть свободная метка, которую мы дадим <tex>q:\mathrm{q.label} = \dfrac{\mathrm{p.label}+\mathrm{r.label}}{2}</tex>любую свободную метку между ними. После этого опять проверим <tex>u</tex> на соответствие неравенству. [[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка {{---}} метка в листе используется.]]** <b>свободной метки нет:</b> В случае, если между метками <tex>p</tex> и <tex>q</tex> следующим за ним элементом свободной метки нет, нам придется пересчитать метки следующим образом:описанным ниже способом.

<b>Способ хранения меток.</b> Все метки хранятся в [[Сверхбыстрый цифровой бор | цифровом боре ]] высоты <tex>u</tex> (там хранятся не только используемые метки, а вообще все возможные заданной длины). В узлах будем хранить:* <b>в листьях </b> будем хранить, используется ли уже эта метка. Пусть <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве <tex>x</tex>, а <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>;* <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(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}</tex>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.

<b>Перераспределение меток.</b> Тогда, как только мы получаем команду вставить элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно <tex>\dfrac{1}{\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>. Чтобы это произошло, требуется, чтобы было сделано еще <tex>\mathrm{size(y)}*(\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \mathrm{size(y)}*\dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> добавлений.

<b>Докажем амортизационную стоимость операции добавления.</b>* С одной стороны, повторное перераспределение меток в поддереве узла <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>. Чтобы это произошло, требуется, чтобы было сделано еще <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> добавлений.* С другой стороны, следующее перераспределение переспределение меток произойдет, когда <tex>\mathrm{weight(x)} = \dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex>. Получается, что за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций перераспределения меток требуется сделать <tex>\mathrm{size(y)}*\dfrac{\alpha - 1}{\alpha^{\mathrm{height(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_{\dfracfrac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за логарифмическое время от <tex>O(\log n)</tex>.

Улучшим Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится делать перераспределение меток. Используем <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex> (модифицированный цифровой бор), чтобы улучшить время работы операции добавления до <tex>O(1)</tex>. Для этого будем использовать <tex>\mathrm У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная {{y-fast-tree-}}положение элемента внутри блока. Описание взаимодействия с метками: * <b>локальные метки</texb> (улучшенный цифровой бор). Внутри внутри каждого кусочка блока будем тоже присваивать каждому элементу метку от <tex>0</tex> до <tex>2^{2u-1}</tex> жадно, тогда у каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает кусочек, локальная {{---}} положение элемента внутри кусочка. Стоит заметить, что внутри кусочка блока никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если мы каждый раз в качестве метки будем брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию). А ;* <b>глобальные метки </b> будут организованы в структуру, описанную вышеиспользовавшуюся в реализации операции за логарифмическое время. Глобальные метки для кусочков блоков нам придется менять, когда один из кусочков блоков переполнился. Тогда разделим кусочек блок на два, присвоив метку второму, методом, описанным выше (поднимемся до первого непереполненного). Каждый кусочек блок будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то кусочке блок становится слишком мало ключей, мы его сливаем с соседним.  Внутри кусочков блоков мы присваиваем ключи за <tex>O(1)</tex>, а, аналогичный приведенному выше анализ показывает, что, чтобы потребовалось перераспределение глобальных меток, требуется <tex>\Omega(u)</tex> изменений локальных меток. За эти изменения накопим <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.

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

[[Категория:Дискретная математика и алгоритмы]][[Категория: Алгоритмы и структуры данных]]