Optimal Finger Search Trees in the Pointer Machine

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

In Proc. 34th Annual ACM Symposium on Theory of Computing, pages 583-591, 2002.


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 © 2002 by the Association for Computer Machinery, Inc.

Online version

stoc02.pdf (189 Kb)



BIBTEX entry

  author = "Gerth St{\o}lting Brodal and George Lagogiannis and Christos Makris and Athanasios Tsakalidis and Kostas Tsichlas",
  booktitle = "Proc. 34th Annual ACM Symposium on Theory of Computing",
  doi = "10.1145/509907.509991",
  isbn = "1-58113-495-9",
  pages = "583-591",
  title = "Optimal Finger Search Trees in the Pointer Machine",
  year = "2002"