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 | |
State | Published - 2000 |
Keywords
- Amortized analysis
- Binary search tree
- Finger search tree
- Splay tree
ASJC Scopus subject areas
- General Computer Science
- General Mathematics