On Fri, Aug 31, 2012 at 05:45:27AM +0100, Richard O'Keefe wrote:
Consider the following interface
type Ord k = Sliding_Window k v
entries :: Sliding_Window k v - [(k,v)]
The cost is expected to be linear in the length of
the result. The pairs are listed in
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