On 23/05/13 18:44, Dan Stromberg wrote:
On Thu, May 23, 2013 at 9:41 AM, duncan smith <buzzard@invalid.invalid
<mailto: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.
Dan,
Faster on average, but it depends what you're averaging over. As
far as insertion and deletions are concerned my results agree with those
in the paper, except they have treaps performing slightly faster than
RBTs for insertion with randomly ordered data.
Deletion in your code is slightly different to that in mine. It might
make a difference. Also, your code doesn't use sentinels (pros and
cons). It could be down to implementation details.
Duncan
--
http://mail.python.org/mailman/listinfo/python-list
