Some New Results on the Dynamic Optimality Problem

Rolf Fagerburg

Binary Search Trees (BSTs) are a fundamental data structure. The Dynamic Optimality Problem is to determine how close to optimal that online algorithms for dynamic BSTs can serve sequences of searches. Despite quite active research, this has been an open problem for around 30 years. It is often referred to as the Splay Tree Conjecture, since for a long time, Splay Trees were the only plausible contender for achieving optimality (to within a constant factor). Indeed, they are often conjectured to do so, based on a number of existing upper bounds on their adaptive behavior.

In a recent development (SODA'09), Demaine et al. have given a new, purely geometric framework for studying adaptive BSTs. One of the insights included in this work is that an existing offline BST algorithm, conjectured to be very close to optimal, can be transformed into an online BST algorithm (with only a constant factor slowdown), which by transfer of conjecture constitutes a new contender. However, no actual upper bounds of any type were known for the algorithm.

Very recently, Kyle Fox, student at University of Illinois at Urbana-Champaign, has proved that many of the upper bounds known to hold for Splay Trees also hold for the new algorithm (results to appear at WADS'11). In this talk we will give a brief background of the area, and some details of Fox' new results.