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 &lt; t_r &lt; 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 &amp; Tarjan of bootstrapping the spines in order to make treaps (or treap-like data structures) with doubly-logarithmic join.
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.