Spring til hovednavigation Spring til søgning Spring til hovedindhold

An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times

  • Carleton University

Publikation: Bidrag til tidsskrift › Konferenceartikel › Forskning › peer review

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.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind6139
Sider (fra-til)38-49
Antal sider12
ISSN0302-9743
DOI
StatusUdgivet - 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