Optimal finger search trees in the pointer machine
Gerth Stølting Brodal, George Lagogiannis, Christos H. Makris, Athanasios Tsakalidis, Kostas Tsichlas · 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.