Изменения

Существует реализация такой структуры, где все операции выполняются <tex>\mathrm{order(p, q)}</tex> выполняется за истинную, а команды добавления и удаления за амортизационную <tex>O(1)</tex>.Потребность Проблема поддержки порядка в списке с командой порядка возникает, к примеру, в при реализации [[Персистентные структуры данных|персистентного дерева поиска]].

Все операции кроме <tex>\mathrm{order(p,q)}</tex> за <tex>O(1)</tex> может выполнить обычный [[Список|двусвязный список]]. Проблема возникает в тот момент, когда мы хотим Однако с его помощью невозможно получить порядок элементов, так как связный список не хранит информацию о нём. Пусть порядке объектов, поэтому сопоставим каждому узлу сопоставлено некоторое числотак, при этом чтобы все числа строго возрастают возрастали от начала списка к его концусписка. Таким образом, эти числа, которые в дальнейшим будут называться метками, задают порядок на элементах списка. И, зная ссылки  Ответить на два элемента запрос <tex>\mathrm{order(p,q)}</tex> и можно за <tex>qO(1)</tex>, можно за просто сравнив метки <tex>O(1)p</tex> ответить на запрос и <tex>\mathrm{order(p,q)}</tex>, просто сравнив их метки. Заметим, что добавление меток никак не влияет на реализацию операции <tex>\mathrm{remove(p)}</tex>. Однако с реализацией реализацию <tex>\mathrm{insert(p,q)}</tex> возникают проблемыпотребуется изменить: при добавлении нового элемента <tex>q</tex> после узла <tex>p</tex>, узлу <tex>q</tex> надо присвоить метку, которая строго больше предыдущего элемента и строго меньше следующего. Исходя из предположения, что метки имеют конечную длину, в какой-то момент возникнет ситуация, что новой метки не найдётся. Тогда будем выдавать элементам , тогда перераспределим среди элементов списка новые метки так, чтобы <tex>q</tex> хватило метки. Теперь рассмотрим Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.

<b>Способ хранения меток.</b> Будем хранить все метки в [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>u</tex> (там хранятся не только используемые метки, а вообще все возможные заданной длины). В узлах будем хранить:* <b>в листьях</b> будем хранить, используется ли уже эта метка. Пусть <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве <tex>x</tex>, а <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>;[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для ==== Перераспределение меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</tex>.]]* <b>в нелистовых узлах</b> будем хранить, является ли узел переполненным. Для любой <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>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.  <b>Перераспределение меток.</b> Тогда, как только мы получаем команду вставить элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно между занятыми метками будет не меньше <tex>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>свободных меток.