Order-maintenance problem
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.
Athanasios Tsakalidis used BB[α] trees with the same performance bounds that supports deletion in
[2] Dietz and Daniel Sleator published an improvement to worst-case constant time in 1987.
[3] Michael Bender, Richard Cole and Jack Zito published significantly simplified alternatives in 2002.
[4] Bender, Fineman, Gilbert, Kopelowitz and Montes also published a deamortized solution in 2017.
[5] Efficient data structures for order-maintenance have applications in many areas, including data structure persistence,[6] graph algorithms[7][8] and fault-tolerant data structures.
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.
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.
For a list-labeling problem on sets of size up to
, the cost of list labeling depends on how large
The relevant parameter range for order maintenance are for
for which a constant time amortized solution is known[11] 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.
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.
be the number of elements of the total order when it was last rebuilt.
Since rebuilding can be done in linear time this does not affect the amortized performance of insertions and deletions.
elements of the total order are split into
The list labeling problem is solved on the set set of nodes representing each of the sublists in their original list order.
, so that they can be compared in constant time and updated in amortized
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.
, so that the can be compared in constant time, but because each local problem involves only
See the list-labeling problem for details of both solutions.
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.
, and the items in each list are given new labels from their (independent) ranges.
insertions since the list was created or last split.
elements were deleted from the sublist since it was first built we can afford to spend the
