Order-maintenance problem
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. Paul Dietz first introduced a data structure to solve this problem in1982. This datastructure supports insert(X, Y) in (in Big O notation)amortized time and order(X, Y) in constant time but doesnot support deletion. Athanasios Tsakalidis used BB[α] trees with the same performance bounds that supportsdeletion 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. Michael Bender, Richard Cole and Jack Zito published significantly simplified alternatives in 2004. Bender, Fineman, Gilbert, Kopelowitz and Montes also published a deamortized solution in 2017. Efficient data structures for order-maintenance have applications inmany areas, including data structure persistence, graph algorithms and fault-tolerant data structures. (Wikipedia).
