Why FHQ Never Rotates

Freedom from random priorities. No priority is ever compared during a descent, so a split/merge pair yields a balanced sequence from the split points alone.

Persistence and sequence operations. No node is ever restructured in place, so path-copying a split/merge pair yields a fully persistent balanced sequence.

A worst case height bound. Removing rotations makes the height depend only on where the splits fall, so a split/merge pair yields a deterministically balanced sequence.

An $O(1)$ merge of arbitrary treaps. No node is ever restructured in place, so a split/merge pair joins two independent balanced sequences in constant time.