Aarhus University Seal

Optimal Finger Search Trees in the Pointer Machine

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

  • Gerth Stølting Brodal
  • George Lagogiannis, Denmark
  • Christos Makris, Denmark
  • Athanasios Tsakalidis, Denmark
  • Kostas Tsichlas, University of Patras, Greece
  • Department of Computer Science
We develop a new finger search tree with worst-case constant update time in the Pointer Machine (PM) model of computation. This was a major problem in the field of Data Structures and was tantalizingly open for over twenty years while many attempts by researchers were made to solve it. The result comes as a consequence of the innovative mechanism that guides the rebalancing operations combined with incremental multiple splitting and fusion techniques over nodes.
Original languageEnglish
JournalJournal of Computer and System Sciences
Volume67
Issue2
Pages (from-to)381-418
Number of pages38
ISSN0022-0000
DOIs
Publication statusPublished - 2003

Bibliographical note

Special issue on STOC 2002

See relations at Aarhus University Citationformats

ID: 280807