Re:Treaps: A Simple Balanced Binary Tree
by sesqu on Sunday September 11, 2011 @12:56PM
(#2984146)
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.
edit: For the actual comparison between the three: treaps give no guarantees. Red-black trees sacrifice some lookup speed in favor of insertions.