Authors
Citation
A. Subramanian, AN EXPLANATION OF SPLAYING, Journal of algorithms, 20(3), 1996, pp. 512-525
Citations number
4
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
ISSN journal
01966774
Volume
20
Issue
3
Year of publication
1996
Pages
512 - 525
Database
ISI
SICI code
0196-6774(1996)20:3<512:AEOS>2.0.ZU;2-A
Abstract
We propose a framework for studying bottom-up restructuring heuristics
for binary search trees. We identify the key role played by depth-red
ucing rules in obtaining logarithmic amortized cost per access. We sho
w that splaying is by no means the only heuristic that offers logarith
mic amortized cost. (C) 1996 Academic Press, Inc.