Faster join of treap-like data structures with approximately the same size

Question

Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $T_1$ and $T_2$ in time $O(1+|h(T_1) - h(T_2)|)$, where $h(T)$ denotes the height of a tree $T$ (as long as trees store their height).

This is also possible for red-black trees, and I assume many other kinds of balanced trees as well.

Is this possible for treaps or treap-like data structures? What if we leave out $t_r$?

The treaps paper in Algorithmica shows how to do this in $O(\min(h(T_1),h(T_2)))$ expected time. If there is a way to perform O(1) expected join on treaps (or treap-like data structures) with roughly the same size (or root priority), I think it might be possible to use a trick of Kaplan & Tarjan of bootstrapping the spines in order to make treaps (or treap-like data structures) with doubly-logarithmic join.

Answer 1

Nope, it's not possible to do this with ordinary Treaps if the priorities are random.

The precise claim I'll make is that to perform such a merge on two equally sized treaps with random priorities requires updating $\Theta(\log n)$ pointers in expectation.

Here's a rough proof sketch:

Consider the number of pointers you have to change in expectation to perform the operation. It's easier to prove a $\Theta(\log n)$ bound if we don't insert $t_r$ but just merge $T_1$ and $T_2$. Consider the right spine $S_1$ of $T_1$ and the left spine $S_2$ of $T_2$. Color the elements of $S_1$ red and those of $S_2$ blue. Order $S_1 \cup S_2$ by priority. We have to change a pointer each time the color changes in this sequence. Since both spines have size $\Theta(\log n)$ with high probability, and the priorities are random, it's not too hard to see that the # of color changes in the sequence is also $\Theta(\log n)$. So we need to update $\Theta(\log n)$ pointers for the merge (without adding $t_r$).

Now, adding $t_r$ while doing the merge doesn't really help much. The number of pointer changes in that case can be lower bounded as follows: Order $S_1 \cup S_2 \cup \{t_r\}$ by priority. Delete everything less than $t_r$ in the sequence. Then # of color changes in the resulting sequence is our lower bound. Since $t_r$ has random priority, the expected height of the subtree rooted at it in the final treap is $O(1)$, so it only has $O(1)$ nodes of $S_1 \cup S_2$ with lower priority than it in expectation, so we lost only $O(1)$ pointer changes in our lower bound when adding $t_r$.

Now, that said, there's probably a way to get a "treap-like" data structure which allows for constant expected time merges.

Answer 2

Update: see below for an update on the incorrectness of this join operation

Here is a very rough sketch of a possible solution:

I think I may have a solution to this problem using a type of randomly-balanced B+-tree. Like treaps, these trees have a unique representation. Unlike treaps, they store some keys multiple times. It might be possible to fix that using a trick from Bent et al's "Biased Search Trees" of storing each key only in the highest (that is, closest-to-the-root) level in which it appears)

A tree for an ordered set of unique values is created by first associating each value with a stream of bits, similar to the way each value in a treap is associated with a priority. Each node in the tree contains both a key and a bit stream. Non-leaf nodes contain, in addition, a natural number indicating the height of the tree rooted at that node. Internal nodes may have any non-zero number of children. Like B+-trees, every non-self-intersecting path from the root to a leaf is the same length.

Every internal node $v$ contains (like in B+-trees) the largest key $k$ of its descendant leaves. Each one also contains a natural number $i$ indicating the height of the tree rooted at $v$, and the stream of bits associated with $k$ from the $i+1$th bit onward. If every key in the tree rooted at $v$ has the same first bit in its bit stream, every child of $v$ is a leaf and $i$ is $1$. Otherwise, the children of $v$ are internal nodes all of which have the same $i$th bit in the bit stream associated with their key.

To make a tree from a sorted list of keys with associated bit streams, first collect the keys into contiguous groups based on the first bit in their streams. For each of these groups, create a parent with the key and bit stream of the largest key in the group, but eliding the first bit of the stream. Now do the same grouping procedure on the new parents to create grandparents. Continue until only one node remains; this is the root of the tree.

The following list of keys and (beginning of) bit streams is represented by the tree below it. In the bit stream prefixes, a '.' means any bit. That is, any bit stream for the key A with a 0 in the first place with produce the same tree as any other, assuming no other key's bit stream is diffferent.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Every child of a particular internal node has the same bit in the first place of its bit stream. This is called the "color" of the parent - 0 is red, 1 is green. The child has a "flavor" depending on the first bit of its bit stream - 0 is cherry, 1 is mint. Leaves have flavors, but no color. By definition, a cherry node can't have a green parent, and a mint node can't have a red parent.

Assuming the bits in the bit streams are IID from the uniform distribution, the PMF of the number of parents of $n$ nodes is $2^{1-n}$ ${n-1}\choose{i-1}$ and the expected value is $(n+1)/2$. For all $n \geq 2$, this is $\leq \frac{3}{4}n$, so the expected tree height is $O(\lg n)$.

To join two trees of equal height, first check to see if their roots are the same color. If so, sever from the left root its right-most child and from the right root its left-most child, then recursively join these two trees. The result will be a tree of the same height or one taller since the trees have the same flavor (see below). If the result of recursively joining the two trees has same height as the two severed children, make it the middle child of a root with the remaining children of the left root before it and the remaining children of the right root after it. If it is taller by 1, make its children the middle children of a root with the remaining children of the left root before it and the remaining children of the right root after it. If the roots have different colors, check to see if they have the same flavor. If they do, give them a new parent with the key and bit stream of the right root, eliding its first bit. If they do not, give each root a new parent with the key and bit stream of the old root (eliding each first bit), then recursively join those trees.

There are two recursive calls in this algorithm. The first is when the roots have the same color, the second is when the roots have different colors and different flavors. The roots have the same color with probability $1/2$. The recursive call in this case always sees roots with the same flavor, so the second type of recursion never occurs after the first. However, the first can occur repeatedly, but each time with probability $1/2$, so the expected running time is still $O(1)$. The second recursive call happens with probability $1/4$, and subsequent recursive calls are always on trees with different colors, so the same analysis applies.

To join two trees of unequal height, first trace down the left spine of the right tree, assuming the right tree is taller. (The other case is symmetric.) When two trees of equal height are reached, perform the join operation for two trees of equal height, modified as follows: If the result has the same height, replace the tree that was a child with the result of the join. If the result is taller, join the parent of the tree on the right to the root of the other tree, after it has been made taller by one by adding a parent for the root. The tree will be the same height with probability $1/2$, so this terminates in $O(1)$ expected.

Update: Thanks to QuickCheck, I discovered that the above join method does not produce the same trees as the uniquely represented trees above. The problem is that parent choices near the leaves may change depending on the available siblings. To fix up those changes, join would have to traverse all the way to the leaves, which is not $O(1)$. Here is the example QuickCheck found:

a 01110
b 110..
c 10...
d 00000

The the tree made by [a,b] has height 2, the tree made by [c,d] has height 2, and the tree made by joinEqual (tree [a,b]) (tree [c,d]) has height 3. However, the tree made by [a,b,c,d] has height 5.

Here is the code I used to find this error.