News for hackers. Stuff that matters.
Re:Treaps: A Simple Balanced Binary Tree by pavpanchekha on Monday September 12, 2011 @05:37AM (#2986461)
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.
Re:Treaps: A Simple Balanced Binary Tree by sesqu on Tuesday September 13, 2011 @08:46AM (#2991156)
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.