Изменения

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

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

[[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка {{- --}} метка в листе используется.]]

В случае, если между метками <tex>p</tex> и <tex>q</tex> свободной метки нет, нам придется пересчитать метки следующим образом. Построим виртуальное дерево отрезков над всеми возможными метками, где Все метки хранятся в каждом узле будем хранить цифровом боре высоты <tex>1u</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>.]]

[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|Визуализация локальных и глобальных y-fast-tree для меток.]]Улучшим время работы операции добавления до <tex>O(1)</tex>, для этого разобьем весь список на кусочки длины от будем использовать <tex>\dfracmathrm{u}{2y-fast-tree}</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''. Послесловие их статьи таково: