On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences

R. Cole; B. Mishra; J. Schmidt; A. Siegel

doi:10.1137/S0097539797326988

On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences

R. Cole, B. Mishra, J. Schmidt, A. Siegel

Computer Science

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

Abstract

The splay tree is a binary search tree in which each access will cause some rotations to be performed on the tree. A special instance of the splay sorting problem related to the dynamic finger conjecture is investigated. The splay sort conjecture is proven in a variety of sequences. A number of features and several new techniques for proving amortized results are introduced.

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

Keywords

Amortized analysis
Binary search tree
Finger search tree
Splay tree

ASJC Scopus subject areas

Computer Science(all)
Mathematics(all)

Access to Document

10.1137/S0097539797326988

Cite this

@article{e8ea1c28a52e4e499239f2dd5d600633,

title = "On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences",

abstract = "The splay tree is a binary search tree in which each access will cause some rotations to be performed on the tree. A special instance of the splay sorting problem related to the dynamic finger conjecture is investigated. The splay sort conjecture is proven in a variety of sequences. A number of features and several new techniques for proving amortized results are introduced.",

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

author = "R. Cole and B. Mishra and J. Schmidt and A. Siegel",

year = "2000",

doi = "10.1137/S0097539797326988",

language = "English (US)",

volume = "30",

pages = "1--43",

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 I

T2 - Splay sorting log n-block sequences

AU - Cole, R.

AU - Mishra, B.

AU - Schmidt, J.

AU - Siegel, A.

PY - 2000

Y1 - 2000

N2 - The splay tree is a binary search tree in which each access will cause some rotations to be performed on the tree. A special instance of the splay sorting problem related to the dynamic finger conjecture is investigated. The splay sort conjecture is proven in a variety of sequences. A number of features and several new techniques for proving amortized results are introduced.

AB - The splay tree is a binary search tree in which each access will cause some rotations to be performed on the tree. A special instance of the splay sorting problem related to the dynamic finger conjecture is investigated. The splay sort conjecture is proven in a variety of sequences. A number of features and several new techniques for proving amortized results are introduced.

KW - Amortized analysis

KW - Binary search tree

KW - Finger search tree

KW - Splay tree

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

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

U2 - 10.1137/S0097539797326988

DO - 10.1137/S0097539797326988

M3 - Article

AN - SCOPUS:0034456263

SN - 0097-5397

VL - 30

SP - 1

EP - 43

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -

On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this