Expiring cached data?

[ajb at spamcop.net]

G'day all.

Quoting Tom Pledger <Tom.Pledger at peace.com>:

> It sounds like the term "splay tree" means different things to
> different people.  I was thinking in particular of one which, whenever
> it finds a key it was looking for, does some rotation so that the
> key's node's depth is reduced.

The one I'm thinking of (and I believe it's "the original") is Sleator and
Tarjan's "Self-adjusting binary search trees" from JACM some time in the
mid-80s.  Their algorithm moves the just-accessed key to the root.

Cheers,
Andrew Bromage