I personally found balancing weight balanced trees pretty straightforward: https://yoichihirai.com/bst.pdf

What I like about immutable treaps is that, if you using hashing rather than randomness, you can achieve O(1) equality for entire trees.

Unfortunately, my current language of choice makes hash consing too slow.