One data structure I recently found myself wanting is a tree-based "array", with O(log n) access by index / insertion anywhere / deletion anywhere.
Kinda weird how rare it seems to be.
Kinda weird how rare it seems to be.
Which is why usually you would use a red-black tree rather than a BTree, as it has much lower constant for insertion and access by index. However higher for traversal in order.
And indeed, I don't recall seeing something like that. At a first glance O(log n) seems easy to do in the average case, but perhaps not in the worst case.
[1] https://hypirion.com/musings/understanding-persistent-vector...