List order maintenance

Для такого списка команда [math]\mathrm{order(D,B)}[/math] выдаст [math]\mathrm{false}[/math].

List order maintance — проблема поддержки списка со следующими командами:

• [math]\mathrm{insert(p, q)}[/math] — вставка нового элемента [math]p[/math] в список сразу после [math]q[/math];
• [math]\mathrm{remove(p)}[/math] — удаление элемента [math]p[/math] из списка;
• [math]\mathrm{order(p, q)}[/math] — команда, возвращающая [math]\mathrm{true}[/math] , если [math]p[/math] в списке находится до [math]q[/math] и [math]\mathrm{false}[/math] иначе.

Структура данных подходит и для односвязных, и для двусвязных списков.

Алгоритм

Пример расставления меток для списка, [math]u=3[/math].

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

Для выполнения [math]\mathrm{remove(p)}[/math] просто удалим элемент [math]p[/math] вместе с его меткой, проверим, удовлетворяет ли [math]u[/math] неравенству, если нет - пересчитаем. Для [math]\mathrm{insert(p,q)}[/math] существуют два возможных случая:

Метка [math]r[/math]: [math]\mathrm{r.label}\gt \mathrm{p.label} + 1[/math], где [math]r[/math] — следующий за [math]p[/math] элемент в списке. Тогда между метками [math]p[/math] и [math]r[/math] есть свободная метка, которую мы дадим [math]q:\mathrm{q.label} = \dfrac{\mathrm{p.label}+\mathrm{r.label}}{2}[/math]. После этого опять проверим [math]u[/math] на соответствие неравенству.

Точка - метка в листе используется.

В случае, если между метками [math]p[/math] и [math]q[/math] свободной метки нет, нам придется пересчитать метки следующим образом. Построим виртуальное дерево отрезков над всеми возможными метками, где в каждом узле будем хранить [math]1[/math] бит. В листьях будем хранить, используется ли уже эта метка. Пусть [math]\mathrm{weight(x)}[/math] — это количество помеченных (используемых) листьев (меток) в поддереве [math]x[/math], а [math]\mathrm{size(x)}[/math] — это количество всех листьев в поддереве [math]x[/math]. Для любой [math]1\lt \alpha\lt 2[/math] будем считать, что узел дерева переполнен, если [math]\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\gt \dfrac{1}{\alpha^{\mathrm{height(x)}}}[/math]. Именно наличие переполненности мы и будем хранить во всех нелистовых узлах. Стоит заметить, что все листья всегда непереполнены. В худшем случае: [math] \dfrac{\mathrm{weight(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}[/math]. Получается, что чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.

Пример виртуального дерева отрезков над метками, где узел с крестиком - переполненный узел, а с галочкой - не переполненный.

Тогда, как только мы получаем команду вставить элемент элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента [math]p[/math], пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к [math]u[/math] позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как [math]\dfrac{\mathrm{weight(x)}}{size(x)}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}[/math], если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно [math]\dfrac{1}{\alpha^{\mathrm{height(x)}}}[/math].

Тогда чтобы после перераспределения меток в поддереве узла [math]x[/math], мы заново пришли к этому же узлу за перераспределением, нужно, чтобы его сын снова переполнился. Если [math]y[/math] — сын [math]x[/math], то он переполнится, когда [math]\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}\gt \dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}[/math]. Чтобы это произошло, требуется, чтобы было сделано еще [math]\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)}}}[/math] добавлений.

См. также

• Список
• Персистентный стек

Источники информации

• — Лекция А.С. Станкевича
• — Wikipedia: order maintance problem