5 Nov
2003
5 Nov
'03
2:55 a.m.
G'day all. Quoting Tom Pledger <Tom.Pledger@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