3622
правки
Изменения
м
→Идея
=== Идея ===
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
Все операции, кроме <tex>\mathrm{order(p,q)}</tex>, за <tex>O(1)</tex> может выполнить обычный [[Список|двусвязный список]], но с его помощью невозможно получить информацию о порядке объектов. Чтобы реализовать эту операцию, Для реализации этой операции каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Таким образом, эти числа, которые в дальнейшим будут называться <b>метками</b>, задают порядок на элементах списка.
Ответить на запрос <tex>\mathrm{order(p,q)}</tex> можно за <tex>O(1)</tex>, просто сравнив метки <tex>p</tex> и <tex>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> нашлась метка. Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.
