Thanks for that paper, it looks to show that treaps are are better on average than I presumed. I'll have to take some time and read the whole thing.
That said, their definition of optimal is big-O, which is unimpressive and I believe also reached without any balancing, provided the input has no duplicates.
> That said, their definition of optimal is big-O,
There are balanced search trees with shorter maximum height, but they often take asymptotically longer for local operations (finger update and finger search).
> which is unimpressive
What do you mean?
> I believe also reached without any balancing
I don't know what this means in context. Treaps are randomly balanced, making them have height O(lg n) with high probability.
> provided the input has no duplicates.
Duplicate keys are handled properly. The problem of duplicate priorities is discussed in the paper.
By unimpressive, I meant precisely that all balanced search trees have shorter maximum height - they are "more optimal". I expected other performance indicators.
I believe, but haven't verified, that expected logarithmic height is achieved just by randomly permuting the input sequence and not doing any subsequent balancing - so the treap approach is simply deferring the permuting to insertion time.
I can't think of a search tree with worse finger search performance than the treap - can you expand on that?
> I believe, but haven't verified, that expected logarithmic height is achieved just by randomly permuting the input sequence and not doing any subsequent balancing - so the treap approach is simply deferring the permuting to insertion time.
That is false. (edit: What I mean is that your belief about the mechanism of randomization is false. If you look at the paper I linked to above, you will see that the authors explain that the randomness must be independent of the input key values.)
> I can't think of a search tree with worse finger search performance than the treap - can you expand on that?
I'm not sure anymore, but I stand by my "asymptotically worse performance on finger updates" claim.
> What I mean is that your belief about the mechanism of randomization is false.
Sorry, I'm not following. Does the treap balancing mechanism not result in a tree equivalent to what one would get permuting the input sequence with "order by rand()"? I'm pretty sure it does. That has nothing to do with the input key values.
> I stand by my "asymptotically worse performance on finger updates" claim.
Excellent. Can you give me an example of that, then? I've never read an analysis of finger updates, but I'm willing to tentatively accept better expected-case performance. I'm not able to handwave my way to anything asymptotically better, though.
> Does the treap balancing mechanism not result in a tree equivalent to what one would get permuting the input sequence with "order by rand()"? I'm pretty sure it does.
Yes, it does, but I was responding to you comment that "expected logarithmic height is achieved just by randomly permuting the input sequence". It achieves the effect of having randomly permuted the input sequence, but it does not actually perform input sequence permutation.
> Can you give me an example of that, then?
Any tree with nodes that store the number of descendents (weight-balanced search trees, for instance) take Omega(lg n) for finger updates. See also "Heterogeneous Decomposition of Degree-Balanced Search Trees and Its Applications" by Shan Leung ("Maverick") Woo, section 1.1.4 and "Robust balancing in B-trees" by Scott Huddleston and Kurt Mehlhorn. They both mention that the original flavors of B-tree have sequences of k insertion and deletion operations where the update costs alone are omega(k).
Another example is repeated insertion and then deletion of a single element in a full binary tree viewed as an AVL tree. Node height (or even single bit height-balance information like "which child is heavier") propagates all the way to the root for both operations.
That said, their definition of optimal is big-O, which is unimpressive and I believe also reached without any balancing, provided the input has no duplicates.