Persistent sequences with insert and delete and canonical structure?

2 min read Original article ↗

I am wondering if there can be such a thing as a persistent data structure for sequences that a) supports the following operations:

  • insert(index, elem) in $O(log\, n)$ amortised time
  • delete(index) in $O(log\, n)$ amortised time
  • lookup(index) in $O(log\, n)$

while b) ensuring a canonical structure, such that equivalent sequences are represented by exactly the same data structure. I am interested in that because I would like to compute a hash (SHA-256) for the sequence as part of the insert and delete operations, such that equivalent sequences get the same hash, no matter in what order insertions and deletions happened.

For persistent maps, this seems to be possible, via treaps, where the priority is chosen as a function of the key. So if instead of insert and delete I would instead just want an update operation for sequences, that should be possible then.

But for persistent sequences with insert and delete, is this possible? Or has it maybe shown that this is impossible?

You could for example try weight-balanced trees. I've implemented a weight-balanced tree with the condition that $|\text{left child}| \leq |\text{right child}| \leq |\text{left child}|+1$, which corresponds to almost perfectly balanced trees, but testing shows that it doesn't achieve efficient insert/delete operations.