> 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

> 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). http://reports-archive.adm.cs.cmu.edu/anon/2009/CMU-CS-09-133.pdf http://reports-archive.adm.cs.cmu.edu/anon/2009/CMU-CS-09-13... http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlhorn-RobustBalancing.pdf http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Huddleston-Mehlhorn-... 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.