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

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.

• Here's some Haskell code I wrote showing fast join of AVL trees with approximately the same size: haskell.pastebin.com/nfGV8Ffz – jbapple Jan 6 '11 at 8:29
• I doubt that it is possible, because it seems (without a proof) that the expected depth of the new node (containing the value t_r) is more than a constant even in the case where h(T_1)=h(T_2). – Tsuyoshi Ito Jan 6 '11 at 10:44
• Tsuyoshi Ito: I agree, if you assign the new node a priority the same way you assign priorities to other nodes. What if you assign it a priority guaranteed to be higher than those of the root nodes? That destroys the IID nature of the priorities, but what if you then mark the other priorities as shifted, somehow, like paths in persistent red-black trees get marked at the endpoints? Or what if one stores the values only in the leaves of a treap, and performs a join without a t_r? – jbapple Jan 6 '11 at 15:23
• Nodes in treaps with n descendants have i left descendants with probability 1/n. This may contribute to the long merge times even for equally-sized treaps - selecting a new root requires navigating to it, which, since the average depth in the tree is Theta(lg n), also takes Theta(lg n) time. What if a treap node with n descendants has i left children with probability (n choose i)/2^n, and values are only stored at leaves like in a B+-tree. Then joining two equally-sized redistributes a small number of elements from one tree to another in expectation. – jbapple Jan 17 '11 at 3:20
• If my calculations are correct, the expected number of elements redistributed is Theta(sqrt n), which, assuming everything else could be worked out (like the finger search property), would still take Theta(lg n) time in expectation. What about using an even tighter distribution? – jbapple Jan 17 '11 at 3:21

## 2 Answers

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.

• Yes, I am looking for a "treap-like" data structure. Although I mentioned as much in the comments and my defunct answer, I didn't put it in the title or question. – jbapple Jan 14 '11 at 3:31
• Thanks for your answer. I have changed the title and text of the question so as to be less ambiguous. – jbapple Jan 14 '11 at 3:40

### 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.