ALCOMFT-TR-02-77

Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis and Kostas Tsichlas
Optimal Finger Search Trees in the Pointer Machine
Århus and Patras. Work package 4. 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.

Postscript file: ALCOMFT-TR-02-77.ps.gz (352 kb).