<div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">On Thu, May 23, 2013 at 9:41 AM, duncan smith <span dir="ltr"><<a href="mailto:buzzard@invalid.invalid" target="_blank">buzzard@invalid.invalid</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
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.<br>

<br>
No surprise that find() is generally quicker for RBTs, they tend to be better balanced.<br>
<br>
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.<br>
<br>
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).<br>
<br>
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.<br>
<br>
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.<span class=""><font color="#888888"><br>
</font></span></blockquote><div> </div><div>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. <br></div></div><br>The code I used is here: <a href="http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/">http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/</a><br>
<br></div><div class="gmail_extra">See also <a href="https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons">https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons</a> , which found that treaps were faster on average the red black trees.<br>
<br><br></div></div>