[pavpanchekha]

I remember a paper that compared fast implementations of treaps, AVL, and red-black trees, and found that they are approximately equally well suited. rbtrees are best at insertion, AVL at selection, treaps at overall performance (if I recall correctly). I don't have the reference though...

[jrockway]

That result surprises me. Red-black trees do their work at insertion time, and AVL trees split the work between insertion and selection. This should make red-black trees faster at selection and AVL trees faster at insertion, and both should do a set of insertions and selections in the same time.

(A red-black tree is a plain-old binary search tree for everything but modifications.)

[pavpanchekha]

AVL trees give shorter path lengths. So the resulting structure ends up being better, depending on your exact balance of insertion and selection.

[SamReidHughes]

Whaaa? AVL trees don't split the work between insertion and selection. Selections are plain old read-only BST lookups.

[sesqu]

I read a paper in the spring that purported to compare, among others, red-black trees and treaps. It found that treaps were better for ordered operations but worse for random operations.

edit: For the actual comparison between the three: treaps give no guarantees. Red-black trees sacrifice some lookup speed in favor of insertions.