Optimal Finger Search Trees in the Pointer Machine

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

In Journal of Computer and System Sciences, Special issue on STOC 2002, volume 67(2), pages 381-418, 2003.

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.

Copyright notice

Copyright © 2003 by Elsevier Inc.. All rights reserved.

Online version

jcss03.pdf (384 Kb)

DOI

10.1016/S0022-0000(03)00013-8

BIBTEX entry

@article{jcss03,
  author = "Gerth Stølting Brodal and George Lagogiannis and Christos Makris and Athanasios Tsakalidis and Kostas Tsichlas",
  doi = "10.1016/S0022-0000(03)00013-8",
  issn = "0022-0000",
  journal = "Journal of Computer and System Sciences, Special issue on STOC 2002",
  number = "2",
  pages = "381-418",
  title = "Optimal Finger Search Trees in the Pointer Machine",
  volume = "67",
  year = "2003"
}

Other versions