In Computer Science the Order-Maintenance Problem involves maintaining a totally ordered set supporting the following operations:
Contents
- List labeling
- List labeling and binary search trees
- Data structure
- Order
- Insert
- Delete
- Analysis
- Lower bound on list labeling
- O1 amortized insertion via indirection
- References
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; anddelete(X)
, which removes X from the set.The first data structure for order-maintenance was given by Dietz in 1982. This data structure supports insert(X, Y)
in
order(X, Y)
in constant time but does not support deletion. Tsakalidis published a data structure in 1984 based on BB[α] trees with the same performance bounds that supports deletion in
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 order(X, Y)
operation the solution must maintain an assignment of labels from a universe of integers
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.
For efficiency, it is desirable for the size
However, under some restrictions,
List-labeling and binary search trees
List-labeling in a universe of size polynomial in the number
If the tree has height
Therefore, the list-labeling problem can be solved by maintaining a balanced binary search tree on the elements in the list augmented with path labels for each node. However, since every rebalancing operation of the tree would have to also update these path labels, not every self-balancing tree data structure is suitable for this application. Note, for example, that rotating a node with a subtree of size
Data structure
The list-labeling problem can be solved with a universe of size polynomial in the number of elements
Order
Given two nodes X and Y, order(X, Y)
determines their order by comparing their path labels.
Insert
Given a new node for X and a pointer to the node Y, insert(X, Y)
inserts X immediately after Y in the usual way. If a rebalancing operation is required, the appropriate subtree is rebuilt, as usual for a scapegoat tree. Then that subtree is traversed depth first and the path labels of each of its nodes is updated. As described above, this asymptotically takes no longer than the usual rebuilding operation.
Delete
Deletion is performed similarly to insertion. Given the node X to be deleted, delete(X)
removes X as usual. Any subsequent rebuilding operation is followed by a relabeling of the rebuilt subtree.
Analysis
It follows from the argument above about the rebalancing performance of a scapegoat tree augmented with path labels that the insertion and deletion performance of this data structure are asymptotically no worse than in a regular scapegoat tree. Then, since insertions and deletions take
Furthermore, since a scapegoat tree with parameter α maintains a height of at most
Of course, the order of two nodes can be determined in constant time by comparing their labels. A closer inspection shows that this holds even for large
Lower bound on list-labeling
It has been shown that any solution to the list-labeling problem with a universe polynomial in the number of elements will have insertion and deletion performance no better than
However, this lower bound does not apply to the order-maintenance problem and, as stated above, there are data structures that give worst-case constant time performance on all order-maintenance operations.
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
The new data structure is completely rebuilt whenever it grows too large or too small. Let
During the rebuilding operation, the
Order
Given the sublist nodes X and Y, order(X, Y)
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 path labels of their representatives in the tree are compared. This takes constant time.
Insert
Given a new sublist node for X and a pointer to the sublist node Y, insert(X, Y)
inserts X immediately after Y in the sublist of Y. If X is inserted at the end of the sublist, it is given the local label
In the hard case, the neighbours of X have contiguous local labels and the sublist has to be rebuilt. However, in this case at least
If the sublist has size
Delete
Given a sublist node X to be deleted, delete(X)
simply removes X from its sublist in constant time. If this leaves the sublist empty, then we need to remove the representative of the sublist from the tree. Since at least