In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations:

insert(X, Y), which inserts X immediately after Y in the total order; order(X, Y), which determines if X precedes Y in the total order; and delete(X), which removes X from the set.

Order-maintenance problem

Paul Dietz first introduced a data structure to solve this problem in

1982. This data

structure supports insert(X, Y) in (in Big O notation) amortized time and order(X, Y) in constant time but does not support deletion. Athanasios Tsakalidis used BB[α] trees with the same performance bounds that supports deletion in and improved insertion and deletion performance to amortized time with indirection. Dietz and Daniel Sleator published an improvement to worst-case constant time in 1987.<ref name="DietzSleator">. Full version, Tech. Rep. CMU-CS-88-113, Carnegie Mellon University, 1988.</ref> 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.

Order-maintenance problem

Efficient data structures for order-maintenance have applications in

many areas, including data structure persistence,<ref

name="Driscoll">.</ref> graph algorithms<ref

name="Eppstein">.</ref> and fault-tolerant data structures.<ref

name="Aumann">.</ref>

List labeling

A problem related to the order-maintenance problem is the

list-labeling problem in which instead of the order(X, Y) operation the solution must maintain an assignment of labels from a universe of integers 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 label(X) returning the label of any node X. Note that order(X, Y) can be implemented simply by comparing label(X) and label(Y) 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.

Order-maintenance problem

For a list-labeling problem on sets of size up to , the cost of list labeling depends on how large is a function of . The relevant parameter range for order maintenance are for , for which an amortized cost solution is known, and 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 is split into

problems of size . 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 amortized insertion and deletion

time.

The new data structure is completely rebuilt whenever it grows too

large or too small. Let be the number of elements of

the total order when it was last rebuilt. The data structure is

rebuilt whenever the invariant 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 elements of the

total order are split into contiguous

sublists, each of size . 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 , so that they can be compared in constant time and updated in amortized 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 , so that the can be compared in constant time, but because each local problem involves only items, the labels range is exponential in the number of items being labeled. Thus, they can be updated in amortized time.

See the list-labeling problem for details of both solutions.