> ...rather than by doing rotations.

DS i've mentioned is using unzip/zip (called split/merge), see [1]

[1] https://cp-algorithms.com/data_structures/treap.html