I guess this works best if the random numbers you are generating are uniformly distributed. Gaussian distributions, or anything else would likely result in unbalanced trees… though this is intuition talking. I’ve not studied them.

This leads me to wonder though… do you get better performance by using an RNG that has roughly the period equal to the cardinality of your tree nodes? And, as a result, does it make sense to bundle in the RNG specifically for the treap implementation?

I guess this works best if the random numbers you are generating are uniformly distributed. Gaussian distributions, or anything else would likely result in unbalanced trees… though this is intuition talking. I’ve not studied them.

This leads me to wonder though… do you get better performance by using an RNG that has roughly the period equal to the cardinality of your tree nodes? And, as a result, does it make sense to bundle in the RNG specifically for the treap implementation?

I’m not 100% on this, but I think this reminds me a bit of priority heaps as used for A*. I may be tilting at windmilss though.