On Thu, May 23, 2013 at 9:41 AM, duncan smith <buzzard@invalid.invalid>wrote:
> > RBT is quicker than Treap for insertion with randomized data, but slower > with ordered data. Randomized data will tend to minimize the number of tree > rotations needed to keep the RBT balanced, whilst the Treap will be > performing rotations to maintain the heap property in an already reasonably > well balanced tree. With ordered data the RBT will have to work harder to > keep the tree balanced, whilst the Treap will be able to maintain the heap > property with fewer rotations. > > No surprise that find() is generally quicker for RBTs, they tend to be > better balanced. > > Deletion is a bit more confusing. I suppose deletion from a better > balanced tree will tend to be quicker, but deletion from a treap > constructed from ordered data is (for some reason) quickest of all. > > All these operations require a call to find(), and that is generally going > to be quicker for RBTs. Treaps tend to require fewer subsequent rotations, > but they have variable worth (in terms of rebalancing). > > Looks like RBTs are better than treaps if they are being populated with > randomly ordered data, but not if they are being populated with ordered > data. RBTs are better for use cases that are heavy on finds. > > Both types of tree appear to be better balanced (on the basis of the find > results) if populated from ordered data. Treaps appear to perform better on > insertion, find and deletion when populated from ordered data. > Strange. I was comparing randomized data (95% get, 50-50 get and set, 95% set) when I found that treaps were quite a bit faster than red black trees. The code I used is here: http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/ See also https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons , which found that treaps were faster on average the red black trees.
-- http://mail.python.org/mailman/listinfo/python-list
