Optimal finger search trees in the pointer machine

✍ Scribed by Gerth Stølting Brodal; George Lagogiannis; Christos Makris; Athanasios Tsakalidis; Kostas Tsichlas

• Book ID: 104147673
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 461 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00013-8

✦ Synopsis

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 20 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.