65
правок
Изменения
Different significant improvements
[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка команда операция <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]'''List order maintance''' (рус. <i>поддержка поддержание порядка в списке</i>) {{---}} проблема поддержки поддержания списка со следующими операциями:
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
* <tex>\mathrm{remove(p)}</tex> {{---}} удаление элемента <tex>p</tex> из списка;
* <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>.Проблема поддержки поддержания порядка в списке возникает, к примеру, при реализации [[Персистентные структуры данных|полностью персистентного дерева поиска]].
== Алгоритм ==
=== Идея ===
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</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> хватит хватило метки. Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.
=== Алгоритм за O(logn) ===
==== Способ хранения меток ====
Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <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> в цифровом боре. Также в каждом узле дополнительно будет храниться:
* <b>в листьях</b> {{---}} используется ли уже эта метка;
[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</tex>.]]
* <b>в нелистовых узлах</b> {{---}} является ли узел переполненным.
Переполненным является назовем узел, для которого для любой <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>\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>O(u)</tex>.
=== Алгоритм за O(1) ===
== Использование памяти ==
== Послесловие ==