News for hackers. Stuff that matters.
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).

There are no comments on this comment yet.