Проблема поддержания порядка

В информатике проблема поддержания порядка включает поддержание полностью упорядоченного набора, поддерживающего следующие операции:

Пол Дитц впервые представил структуру данных для решения этой проблемы в 1982 году. ^[1] Эта структура данных поддерживает (в insert(X, Y)нотации Big O ) амортизированное время и постоянное время, но не поддерживает удаление. Афанасиос Цакалидис использовал деревья BB[α] с теми же ограничениями производительности, которые поддерживают удаление, и улучшил производительность вставки и удаления до амортизированного времени с косвенностью. ^[2] Дитц и Дэниел Слейтор опубликовали улучшение постоянного времени для наихудшего случая в 1987 году. ^[3] Майкл Бендер, Ричард Коул и Джек Зито опубликовали значительно упрощенные альтернативы в 2004 году. ^[4]${\ Displaystyle О (\ журнал п)}$order(X, Y)${\ Displaystyle О (\ журнал п)}$${\ Displaystyle О (1)}$Бендер, Файнман, Гилберт, Копеловиц и Монтес также опубликовали деамортизированное решение в 2017 году. ^[5]

Эффективные структуры данных для поддержания порядка имеют приложения во многих областях, включая постоянство структуры данных , ^[6] графовые алгоритмы ^{[7] [8]} и отказоустойчивые структуры данных. ^[9]

Проблема, связанная с проблемой поддержания порядка, - это проблема маркировки списка, в которой вместо order(X, Y)операции решение должно поддерживать присвоение меток из множества целых чисел элементам множества, так что X предшествует Y в общем порядке, если и только если X назначена метка меньше, чем Y. Он также должен поддерживать операцию, возвращающую метку любого узла X. Обратите внимание, что это может быть реализовано просто путем сравнения и${\ Displaystyle \ {1,2, \ ldots, м \}}$label(X)order(X, Y)label(X)label(Y)так что любое решение проблемы маркировки списков немедленно приводит к решению проблемы поддержания порядка. На самом деле, большинство решений проблемы поддержания порядка являются решениями проблемы маркировки списков, дополненными уровнем косвенности структуры данных для повышения производительности. Пример этого мы увидим ниже.

Для задачи маркировки списков на наборах размером до , стоимость маркировки списка зависит от того, насколько велика функция . Соответствующий диапазон параметров для ведения заказа составляет для , для которого известно решение по амортизированной стоимости ^[10] и для которого известно решение по амортизированной стоимости за постоянное время ^[11]${\ Displaystyle п}$${\ Displaystyle м}$${\ Displaystyle п}$${\ Displaystyle м = п ^ {1+ \ Тета (1)}}$${\ Displaystyle О (\ журнал п)}$${\ Displaystyle 2 ^ {\ Омега (п)}}$

Структура данных обслуживания заказа с косвенностью. Элементы общего порядка хранятся в смежных подсписках размера , каждый из которых имеет представителя в дереве козла отпущения.${\ Displaystyle О (Н / \ журнал N)}$${\ Displaystyle О (\ журнал N)}$