[Haskell-cafe] Sliding Window functional data structure

ok at cs.otago.ac.nz ok at cs.otago.ac.nz
Fri Aug 31 14:24:40 CEST 2012

> Any search tree implementation will do add and purge in O(log n) time.

Add's obvious, but could you explain to me about purge?
All of the explanations of search trees I'm familiar with,
if they bother to explain deletion at all, talk about how
to repair the balance of a tree after deleting *one* element.
It's not at all obvious to me how to quickly rebalance an
AVL tree after purging it, for example.

> A finger tree will do add in O(1) and purge in O(log(min(r, n-r))) time,

Thanks for that and the sample code.

More information about the Haskell-Cafe mailing list