Abstract
We present the zipper tree, an O(log log n)-competitive online binary search tree that performs each access in O(logn) worst-case time. This shows that for binary search trees, optimal worst-case access time and near-optimal amortized access time can be guaranteed simultaneously.
| Originalsprog | Engelsk |
|---|---|
| Bogserie | Lecture Notes in Computer Science |
| Vol/bind | 6139 |
| Sider (fra-til) | 38-49 |
| Antal sider | 12 |
| ISSN | 0302-9743 |
| DOI | |
| Status | Udgivet - 2010 |
Bibliografisk note
Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)Fingeraftryk
Dyk ned i forskningsemnerne om 'An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times'. Sammen danner de et unikt fingeraftryk.Citationsformater
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver