7
$\begingroup$

Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in a splay tree is logarithmic in the magnitude of the rank difference between the queried key and the most-recently-queried key.

It seems like the first proof that splay trees have the dynamic finger property comes from a two-paper series by Cole et al ("On the Dynamic Finger Conjecture for Splay Trees I: Splay Sorting $\log n$-Block Sequences" and "On the Dynamic Finger Conjecture for Splay Trees II: The Proof.") These papers collectively are over eighty pages long and involve fairly complicated, technical proofs. They also seem to be the papers cited by future work in splay trees and related structures when referring to the dynamic finger property.

Has there been any follow-up work in this area that provides a simpler proof of the dynamic finger conjecture?

$\endgroup$
5
$\begingroup$

There has been a lot of further work more broadly on Splay trees and related data structures after the two papers that you mention, for example the 2019 paper of Levy and Tarjan [1].

However, there have been no alternative proofs or simplifications of the dynamic finger result of Cole et al. that you mention. (Any such attempt would be quite interesting to those working on these problems.)

There is, however, a 2016 paper by Iacono and Langerman [2] that proves a generalization of the dynamic finger property for a different data structure called Greedy BST, that matches many (all) known properties of Splay. The proof techniques here are easier and quite different from those in the Splay dynamic finger paper.

[1] https://doi.org/10.1137/1.9781611975482.80

[2] https://arxiv.org/abs/1810.01785

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.