65
правок
Изменения
full proof added
В случае, если между метками <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>\alpha=1,5</tex>.]]
Тогда, как только мы получаем команду вставить элемент элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <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> добавлений.
С другой стороны, следующее перераспределение меток произойдет, когда <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>\dfrac{2}{\alpha-1}</tex> монет, то за добавления накопится столько монет, чтобы расплатиться за следующую операцию перераспределения в узле <tex>x</tex>. Проблема в том, что таким образом надо платить за каждый уровень, а количество уровней (бит) равно <tex>u</tex>. Тогда амортизированная стоимость добавления <tex>O(u)</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_{\dfrac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за логарифмическое время от <tex>n</tex>, а не за константное.
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|Визуализация локальных и глобальных меток.]]
Улучшим время работы операции добавления до <tex>O(1)</tex>, для этого разобьем весь список на кусочки длины от <tex>\dfrac{u}{2}</tex> до <tex>2u</tex>. Внутри каждого кусочка будем тоже присваивать каждому элементу метку, от <tex>0</tex> до <tex>2^{2u-1}</tex> жадно, тогда у каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает кусочек, локальная - положение элемента внутри кусочка. Стоит заметить, что внутри кусочка никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если мы каждый раз в качестве метки будем брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию). А глобальные метки будут организованы в структуру, описанную выше. Глобальные метки для кусочков нам придется менять, когда один из кусочков переполнился, тогда разделим кусочек на два, присвоив метку второму методом, описанным выше (поднимемся до первого непереполненного). Каждый кусочек будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то кусочке слишком мало ключей становится, мы его сливаем с соседним. Внутри кусочков мы ключи присваиваем за <tex>O(1)</tex>, а, аналогичный приведенному выше, анализ показывает, что, чтобы потребовалось перераспределение глобальных меток, требуется <tex>\Omega(u)</tex> изменений локальных меток. За эти изменения накопим <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.
== Использование памяти ==
== Применение ==
== Послесловие ==
Впервые реализацию такой структуры данных со всеми операциями за константное время предложили ''Dietz'' и ''Sleator'', однако их доказательство времени работы было намного сложнее вышеизложенного анализа. Поэтому позже группа ученых во главе с ''Michael A. Bender'' разработала более простое доказательство, изложенное выше, впервые описанное в их статье ''Two simlified algorithms for maintaining order in a list''. Послесловие их статьи таково:
Dietz and Sleator is quite influential
With its tags and its proofs by potential
But to teach it in class
Is a pain in the ass
So our new result is preferential.
== См. также==
* [https://www.lektorium.tv/lecture/14321 {{---}} Лекция А.С. Станкевича]
* [https://en.wikipedia.org/wiki/Order-maintenance_problem {{---}} Wikipedia: order maintance problem]
* [http://link.springer.com/chapter/10.1007%2F3-540-45749-6_17 {{---}} Статья ''Michael A. Bender'' с описанием более простого доказательства.]
[[Категория:Дискретная математика и алгоритмы]]
