4 ms·

I've never understood the allure of treaps. As long as it's only probabilistically balanced, the only thing it offers beyond random binary search trees is unpre

by sesqu 15y ago

I've never understood the allure of treaps. As long as it's only probabilistically balanced, the only thing it offers beyond random binary search trees is unpredictability in the face of ordered input. In essence, the treap is the same approach to balancing as the skip list. What's wrong with AVL trees? edit: that said, if you do have a genuine need to prioritize some nodes, the observation that the BST property does not preclude the heap property is a very nice one.

pavpanchekha 15y ago
Simplicity of code, and the existence of hooks to add orthogonal functionality. Not all of programming is picking an optimal data structure and then implementing it; sometimes, it involves planning for maintenance and change.
- sesqu 15y ago
  Fair enough, but I personally believe the AVL structure is sufficiently simple. Let me compare treaps and AVL trees: Both insert at the same point, then proceed to rebalance. The treap will rotate upwards until p_new>p_parent. The AVL will update balance information upwards until bal_parent%2==1, then update and possibly rotate once. That's a couple of conditional operations extra, and field operations instead of tree operations. The final step in particular is less elegant, but straggling cleanup operations are everyday things and well worth the better performance, to me.
jbapple 15y ago
> I've never understood the allure of treaps. Ignoring the simplicity argument, treaps can perform some other operations (local updates and nearby searches) in optimal expected time (see theorems 3.1 and 3.2): http://sims.berkeley.edu/~aragon/pubs/rst96.pdf http://sims.berkeley.edu/~aragon/pubs/rst96.pdf > As long as it's only probabilistically balanced, the only thing it offers beyond random binary search trees is unpredictability in the face of ordered input. The randomness treaps use should be independent of the input keys, so ordered input should produce a treap with a shape drawn from the same distribution as the one for unordered input.
- sesqu 15y ago
  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.
  - jbapple 15y ago
    > 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.
    - sesqu 15y ago
      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?
      - jbapple 15y ago
        > 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.

by sesqu 15y ago

pavpanchekha 15y ago

Simplicity of code, and the existence of hooks to add orthogonal functionality. Not all of programming is picking an optimal data structure and then implementing it; sometimes, it involves planning for maintenance and change.

sesqu 15y ago
Fair enough, but I personally believe the AVL structure is sufficiently simple. Let me compare treaps and AVL trees: Both insert at the same point, then proceed to rebalance. The treap will rotate upwards until p_new>p_parent. The AVL will update balance information upwards until bal_parent%2==1, then update and possibly rotate once. That's a couple of conditional operations extra, and field operations instead of tree operations. The final step in particular is less elegant, but straggling cleanup operations are everyday things and well worth the better performance, to me.

jbapple 15y ago

> I've never understood the allure of treaps. Ignoring the simplicity argument, treaps can perform some other operations (local updates and nearby searches) in optimal expected time (see theorems 3.1 and 3.2): http://sims.berkeley.edu/~aragon/pubs/rst96.pdf http://sims.berkeley.edu/~aragon/pubs/rst96.pdf > As long as it's only probabilistically balanced, the only thing it offers beyond random binary search trees is unpredictability in the face of ordered input. The randomness treaps use should be independent of the input keys, so ordered input should produce a treap with a shape drawn from the same distribution as the one for unordered input.

sesqu 15y ago
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.
- jbapple 15y ago
  > 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.
  - sesqu 15y ago
    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?
    - jbapple 15y ago
      > 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.