Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

Problem Detail: 

Imagine I have an ordering on a bunch of elements like so:

Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right)$.

In order efficiently answer queries like $A \stackrel {?}{<} D$, some sort of labeling or data structure is required. For example, you could number the nodes from left to right, and thus you can simply do integer comparison to answer the query: $A \stackrel {?}{<} D \implies 1 < 4 \implies T$. It would look something like this:

Where the number is the ordering, and the letter is just a name.

But what if you needed to insert elements "in between" two other elements in the ordering, like so:

How can you maintain such an ordering? With simple numbering, you run into the problem that there are no integers "in between" $2,3$ to use.

Asked By : Realz Slaw

Answered By : jbapple

This is known as the "order maintenance" problem. There is a relatively simple solution using $O(1)$ amortized time for both queries and inserts. Now, by "relatively simple", I mean that you have to understand some building blocks, but that once you get those, the rest isn't hard to see.

http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html

The basic idea is a two-level data structure. The top level is like the AVL tree solution by Realz Slaw, but

• The nodes are directly labeled with bit strings of length $O(\lg n)$ with an order that matches their order in the tree. Comparison thus takes constant time

• A tree with fewer rotations than an AVL tree is used, like a scapegoat tree or a weight-balanced tree, so relabellings happen less frequently.

The bottom level is the leaves of the tree. That level uses the same length of labels, $O(\lg n)$, but holds only $O(\lg n)$ items in each leaf in a simple linked list. This gives you enough extra bits to relabel aggressively.

Leaves get too big or too small every $O(\lg n)$ inserts, inducing a change in the top level, which takes $O(\lg n)$ amortized time ($\Omega(n)$ worst-case time). Amortized, this is only $O(1)$.

Much more complex structures exist for performing updates in $O(1)$ worst-case time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14708