Mergeable Exact Order Statistics Data Structure

Question

Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that $$ x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1} $$ and let's denote this relationship as $S_i < S_{i+1}$. For each set, we want to build a data structure that supports the following two operations:

• $rank(x)$: Return the rank of $x$ in $S_i$, where $x \in S_i$;

• $merge(A, B)$: Let $A$ and $B$ be the structures built on two sets $S_i$ and $S_j$ with $S_i < S_j$. Merge $A$ and $B$.

One implementation is to use an order statistics tree (such as AVL tree, red-black tree), which is able to support $\mathcal{O}(\log n)$ rank operation, but fails(right?) to provide efficient (i.e., logarithmic or constant) merge operation. A linked-list implementation, however, has poor rank performance. A skip-list may be employed, but its worst time complexity is bad.

Can anyone provide a reference about such a structure or proved lower bounds for a structure that supports these two operations at the same time? Any idea is appreciated. Thanks!

Answer 1

Most balanced trees that have logarithmic-time insert and delete also have logarithmic time $merge$. This includes AVL trees, red-black trees, and B trees.

You can see this question on Stack Overflow for several references results. They include a paper on CGAL (red-black), a reference to the OCaml standard library (AVL), as well as the red-black tree chapter of CLRS's Introduction to Algorithms.

When I was learning about this topic, I was happy to find that $merge$ is actually usually a simpler operation than $insert$ and $delete$.

Answer 2

One option would be a Treap (or (Implicit) Cartesian tree), though it only guarantees $\mathcal{O}(\log n)$ expected time for both operations.

Alternatively, a Splay Tree would give you $\mathcal{O}(\log n)$ amortized time for both operations.