<p>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].</p>

<p>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.)</p>

<p>There is, however, a 2016 paper by Iacono and Langerman [2] that proves a generalization of the dynamic finger property for a <em>different</em> 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.</p>

<p>[1] <a href="https://doi.org/10.1137/1.9781611975482.80" rel="noreferrer">https://doi.org/10.1137/1.9781611975482.80</a></p>

<p>[2] <a href="https://arxiv.org/abs/1810.01785" rel="noreferrer">https://arxiv.org/abs/1810.01785</a></p>

CC BY-SA 4.0
2019-06-04T20:58:35.627Z
2019-06-04T20:58:35.627Z
László Kozma
<p>Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the <em>dynamic finger property</em>, 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.</p>

<p>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 <span class="math-container">$\log n$</span>-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.</p>

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

<reference-request><ds.data-structures>
Simple proof that splay trees have the dynamic finger property?
templatetypedef
# Simple proof that splay trees have the dynamic finger property?

(Asked by: username_0 on 2019-06-04)

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?

**Tags:** reference-request, ds.data-structures

---

## 1 answers

### Answer by username_1 on 2019-06-04. Score: 6 | Accepted answer

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>


---

