In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations:
Paul Dietz first introduced a data structure to solve this problem in
1982. This data
structure supports codice_1 in formula_1 (in Big O notation)
amortized time and codice_2 in constant time but does
not support deletion. Athanasios Tsakalidis used BB[α] trees with the same performance bounds that supports
deletion in formula_1 and improved insertion and deletion performance to
formula_3 amortized time with indirection. Dietz and Daniel Sleator published an improvement to worst-case constant time in 1987. Michael Bender, Richard Cole and Jack Zito published significantly simplified alternatives in 2002. Bender, Fineman, Gilbert, Kopelowitz and Montes also published a deamortized solution in 2017.
Efficient data structures for order-maintenance have applications in
many areas, including data structure persistence, graph algorithms and fault-tolerant data structures.
List labeling.
A problem related to the order-maintenance problem is the
list-labeling problem in which instead of the codice_6 operation the solution must maintain an assignment of labels
from a universe of integers formula_4 to the
elements of the set such that X precedes Y in the total order if and
only if X is assigned a lesser label than Y. It must also support an
operation codice_7 returning the label of any node X.
Note that codice_2 can be implemented simply by
comparing codice_7 and codice_10 so that any
solution to the list-labeling problem immediately gives one to the
order-maintenance problem. In fact, most solutions to the
order-maintenance problem are solutions to the list-labeling problem
augmented with a level of data structure indirection to improve
performance. We will see an example of this below.
For a list-labeling problem on sets of size up to formula_5, the cost of list labeling depends on how large formula_6 is a function of formula_5. The relevant parameter range for order maintenance are for formula_8, for which an formula_1 amortized cost solution is known, and formula_10 for which a constant time amortized solution is known
O(1) amortized insertion via indirection.
Indirection is a technique used in data structures in which a problem
is split into multiple levels of a data structure in order to improve
efficiency. Typically, a problem of size formula_5 is split into
formula_12 problems of size formula_13. For
example, this technique is used in y-fast tries. This
strategy also works to improve the insertion and deletion performance
of the data structure described above to constant amortized time. In
fact, this strategy works for any solution of the list-labeling
problem with formula_1 amortized insertion and deletion
time.
The new data structure is completely rebuilt whenever it grows too
large or too small. Let formula_15 be the number of elements of
the total order when it was last rebuilt. The data structure is
rebuilt whenever the invariant formula_16 is
violated by an insertion or deletion. Since rebuilding can be done in
linear time this does not affect the amortized performance of
insertions and deletions.
During the rebuilding operation, the formula_15 elements of the
total order are split into formula_18 contiguous
sublists, each of size formula_19. The list labeling problem is solved on the set 
set of nodes representing each of
the sublists in their original list order. The labels for this subproblem are taken to be polynomial --- say formula_20, so that they can be compared in constant time and updated in amortized formula_21 time. 
For each sublist a
doubly-linked list of its elements is built storing with each element a
pointer to its representative in the tree as well as a local integer
label. The local integer labels are also taken from a range formula_22, so that the can be compared in constant time, but because each local problem involves only formula_23 items, the labels range formula_6 is exponential in the number of items being labeled. Thus, they can be updated in formula_3 amortized time.
See the list-labeling problem for details of both solutions.
Order.
Given the sublist nodes X and Y, codice_2 can be
answered by first checking if the two nodes are in the same
sublist. If so, their order can be determined by comparing their local
labels. Otherwise the labels of their representatives in the first list-labeling problem are compared. 
These comparisons take constant time.
Insert.
Given a new sublist node for X and a pointer to the sublist node Y,
codice_1 inserts X immediately after Y in the sublist
of Y, if there is room for X in the list, that is if the length of the list is no greater than formula_26 after the insertion. It's local label is given by the local list labeling algorithm for exponential labels. This case takes formula_3 amortized time.
If the local list overflows, it is split evenly into two lists of size formula_28, and the items in each list are given new labels from their (independent) ranges. This creates a new sublist, which is inserted into the list of sublists, and the new sublist node is given a label in the list of sublists by the list-labeling algorithm. Finally X is inserted into the appropriate list. 
This sequence of operations take formula_21 time, but there have been formula_19 insertions since the list was created or last split. Thus the amortized time per insertion is formula_3. 
Delete.
Given a sublist node X to be deleted, codice_3 simply
removes X from its sublist in constant time. If this leaves the
sublist empty, then we need to remove the representative of the
list of sublists. Since at least formula_19
elements were deleted from the sublist since it was first built we can afford to spend the formula_21 time, the amortized cost of a deletion is formula_3.
References.
 ;templatestyles src="Reflist/styles.css" / ;