3 ms·

Interesting, though it's balanced only on average. I suppose it's possible that you can both get elements inserted in order and have the random priorities selec

Interesting, though it's balanced only on average. I suppose it's possible that you can both get elements inserted in order and have the random priorities selected in decreasing order. The chance of ending in a worst case for a tree of non-trivial size would be exceedingly low so I don't see it causing much issue in practice. It is random, though, and sometimes you might prefer systems that are deterministic (say if you absolutely can't afford bad cases). 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) : pos n root = if root.right.count >= n then pos n root.right else if n == 1 || root.right.count - n == 1 then (root.key, root.value) else pos (n - root.right.count) root.left Overall, quite an interesting mix of ordered (search) trees and heaps, I like it.

deleted 15y ago
[deleted]
eru 15y ago
> 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. To be fair, Red-Black trees get much simpler in a functional setting. (If you don't look at deletion.)
dmlorenzetti 15y ago
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).
ScottBurson 15y ago
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.

deleted 15y ago

[deleted]

eru 15y ago

> 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. To be fair, Red-Black trees get much simpler in a functional setting. (If you don't look at deletion.)

dmlorenzetti 15y ago

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).

ScottBurson 15y ago

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.