Изменения

Улучшим время работы операции добавления до <tex>O(1)</tex>, для . Для этого будем использовать <tex>\mathrm{y-fast-tree}</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> монет для изменения глобальных меток, тогда операция добавления работает за константное время.

Из-за того, что <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-fast-tree}</tex>, требуется <tex>O(n)</tex> памяти.

Впервые реализацию такой структуры данных со всеми операциями за константное время амортизационно предложили<ref>[http://www.cs.cmu.edu/~sleator/papers/maintaining-order.html Статья Dietz and Sleator "Two algorithms for maintaining order in a list"]</ref> ''Dietz'' и ''Sleator'', однако их доказательство времени работы было намного сложнее вышеизложенного анализа. Поэтому позже группа ученых во главе с ''Michael A. Bender'' разработала<ref>[http://link.springer.com/chapter/10.1007%2F3-540-45749-6_17 Статья Michael A. Bender "Two Simplified Algorithms for Maintaining Order in a List"]</ref> более простое доказательство, изложенное выше, впервые описанное в их статье ''Two simlified algorithms for maintaining order in a list''. Послесловие их статьи таково: