There are some balanced trees with a weight attached to each node. I have an implementation in containers-data [signature](https://c-cube.github.io/ocaml-containers/3.2/containers-data/CCWBTree/module-type-S/index.html) . There is a random_choose function that does the traversal and exploits the weight to pick left/right for each node. I implemented this years ago but the comments say: Most of this comes from "implementing sets efficiently in a functional language", Stephen Adams. The coefficients 5/2, 3/2 for balancing come from "balancing weight-balanced trees" -- Simon Cruanes