On the dynamic finger conjecture for splay trees. Part II: The proof

R. Cole

doi:10.1137/S009753979732699X

On the dynamic finger conjecture for splay trees. Part II: The proof

R. Cole

Computer Science

Research output: Contribution to journal › Article › peer-review

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 addition, there is an O(n) initialization cost. The accesses include searches, insertions, and deletions.

Original language	English (US)
Pages (from-to)	44-85
Number of pages	42
Journal	SIAM Journal on Computing
Volume	30
Issue number	1
DOIs	https://doi.org/10.1137/S009753979732699X
State	Published - 2000

Keywords

Amortized analysis
Binary search tree
Finger search tree
Splay tree

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S009753979732699X

Cite this

@article{1726aee4f6af43879a95c701f2f392bd,

title = "On the dynamic finger conjecture for splay trees. Part II: The proof",

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 addition, there is an O(n) initialization cost. The accesses include searches, insertions, and deletions.",

keywords = "Amortized analysis, Binary search tree, Finger search tree, Splay tree",

author = "R. Cole",

year = "2000",

doi = "10.1137/S009753979732699X",

language = "English (US)",

volume = "30",

pages = "44--85",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - On the dynamic finger conjecture for splay trees. Part II

T2 - The proof

AU - Cole, R.

PY - 2000

Y1 - 2000

N2 - 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 addition, there is an O(n) initialization cost. The accesses include searches, insertions, and deletions.

AB - 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 addition, there is an O(n) initialization cost. The accesses include searches, insertions, and deletions.

KW - Amortized analysis

KW - Binary search tree

KW - Finger search tree

KW - Splay tree

UR - http://www.scopus.com/inward/record.url?scp=0034455378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034455378&partnerID=8YFLogxK

U2 - 10.1137/S009753979732699X

DO - 10.1137/S009753979732699X

M3 - Article

AN - SCOPUS:0034455378

SN - 0097-5397

VL - 30

SP - 44

EP - 85

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -

On the dynamic finger conjecture for splay trees. Part II: The proof

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this