Re:Treaps: A Simple Balanced Binary Tree
by ScottBurson on Sunday September 11, 2011 @04:36PM
(#2984743)
Keeping the element counts gives you something called weight-balanced binary trees. Here's a paper on them by Stephen Adams:
http://groups.csail.mit.edu/mac/users/adams/BB/
I used a variation on these for my FSet functional collections library for Common Lisp.
Re:Treaps: A Simple Balanced Binary Tree
by dmlorenzetti on Sunday September 11, 2011 @01:52PM
(#2984294)
I wrote a binary tree that used node counts in a similar way. However, the insertion rules included checking whether a rotation on the inserted node would result in a subtree that could again be rotated by the same rule. This gave a cutoff ratio of left-to-right counts, below which it didn't make sense to rotate-- and hence kept every subtree pretty nicely balanced.
Another benefit to having the node counts-- and this, I think, was the original motivation-- was it made the tree "binary" not only for looking up a particular key, but also for looking up the Nth key-ordered entry (which was important in the application).
Anyway, when it comes to simplicity I will admit it is much more appealing than red-black trees and their 5 billion cases for insert and delete - none of them unreasonable, true, but I didn't like debugging that thing at all the first time I attempted to implement it. So, yeah, that's something you can reliably implement when you don't have time/ can't be bothered to look up the ridiculously complicated stuff and you just want to dish out a fast data structure that you know works (binary heap - 1, suffix tree - 0, treap - 1, RBTree - 0).
As for the problem, it should be quite simple if you just keep tabs on the element count on the left and right subtrees, which is small price to pay (under a few million elements, but even with you're working with hundreds of millions - suck it up and buy an extra gig of ram). Something like this pseudocode (hopefully with added error checking) :
Overall, quite an interesting mix of ordered (search) trees and heaps, I like it.