65
правок
Изменения
half of proof added
[[Файл:ListABCD.jpg|300px250px|thumb|right|Для такого списка команда <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]
'''List order maintance''' {{---}} проблема поддержки списка со следующими командами:
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
* <tex>\mathrm{order(p, q)}</tex> {{---}} команда, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.
== Алгоритм ==
Для выполнения <tex>\mathrm{remove(p)}</tex> просто удалим элемент <tex>p</tex> вместе с его меткой, проверим, удовлетворяет ли <tex>u</tex> неравенству, если нет - пересчитаем. Для <tex>\mathrm{insert(p,q)}</tex> существуют два возможных случая:
Метка <tex>r</tex>: <tex>\mathrm{r.label}>\mathrm{p.label} + 1</tex>, где <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|Точка - метка в листе используется.]]
В случае, если между метками <tex>p</tex> и <tex>q</tex> свободной метки нет, нам придется пересчитать метки следующим образом. Построим виртуальное дерево отрезков над всеми возможными метками, где в каждом узле будем хранить <tex>1</tex> бит. В листьях будем хранить, используется ли уже эта метка. Пусть <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве <tex>x</tex>, а <tex>\mathrm{size(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> \dfrac{\mathrm{weight(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}</tex>. Получается, что чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.
[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример виртуального дерева отрезков над метками, где узел с крестиком - переполненный узел, а с галочкой - не переполненный.]]
Тогда, как только мы получаем команду вставить элемент элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{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> добавлений.
== Применение ==
== См. также==
