> of course the downside with any probabilistic data structure is that you're counting on the amortized bounds No. With typical probabilistic data structures y

> of course the downside with any probabilistic data structure is that you're counting on the amortized bounds No. With typical probabilistic data structures you're counting on the average bounds. If you have good amortized bounds and that's what you care about, you don't need to bother with the randomization. Per-operation versus amortized and worst-case versus average-case are orthogonal distinctions.