Expand description
Persistent (copy-on-write) treap.
Every insert / remove returns a NEW PersistentTreap without
mutating the receiver. The mutation path is copied (O(log N)
nodes); every other subtree is shared via Rc, so memory stays
sub-linear in the number of held versions.
Old versions remain fully queryable. This is the right shape for undo stacks, time-travel debugging, and immutable-by-default sequence builders.
The base Treap in lib.rs is the arena-backed mutable variant.
These two share priority-generation conventions (same LCG) but
intentionally have different memory layouts: the arena base is
cache-dense; the persistent variant trades density for the
shared-subtree invariant Rc enforces.