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
Pages (from-to)381-418
Number of pages38
Publication statusPublished - 2003

Bibliographical note

Special issue on STOC 2002

See relations at Aarhus University Citationformats

ID: 280807