Authors
Citation
R. Cole, On the dynamic finger conjecture for splay trees. Part II: The proof, SIAM J COMP, 30(1), 2000, pp. T44-T85
Citations number
8
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397
→ ACNP
Volume
30
Issue
1
Year of publication
2000
Pages
T44 - T85
Database
ISI
SICI code
0097-5397(20000606)30:1<T44:OTDFCF>2.0.ZU;2-Y
Abstract
The following result is shown: On an n-node splay tree, the amortized cost
of an access at distance d from the preceding access is O(log(d + 1)). In a
ddition, there is an O(n) initialization cost. The accesses include searche
s, insertions, and deletions.