Optimal Finger Search Trees in the Pointer Machine

Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas

Technical Report, ALCOMFT-TR-02-77, ALCOM-FT, 17 pages, May 2002.

Abstract

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.

Online version

alcomft-tr-02-77.pdf (205 Kb)

BIBT_EX entry

@techreport{alcomft-tr-02-77,
  author = "Gerth Stølting Brodal and George Lagogiannis and Christos Makris and Athanasios Tsakalidis and Kostas Tsichlas",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-02-77",
  pages = "17",
  title = "Optimal Finger Search Trees in the Pointer Machine",
  year = "2002"
}