Order-maintenance problem

In Computer Science the Order-Maintenance Problem involves maintaining a totally ordered set supporting the following operations:

The first data structure for order-maintenance was given by Dietz in 1982. This data structure supports insert(X, Y) in ${\displaystyle O(\log n)}$ amortized time and 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 ${\displaystyle O(\log n)}$ and showed how indirection can be used to improve insertion and deletion performance to ${\displaystyle O(1)}$ amortized time. In 1987 Dietz and Sleator published the first data structure supporting all operations in worst-case constant time.

...
Wikipedia