Abstract Splay trees (Sleator and Tarjan) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma. Our main result (i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms (Subramanian, Georgakopoulos and Mc-Clurkin), as well as Greedy BST, introduced by Demaine et al. and shown to satisfy the access lemma by Fox, (ii) implies that BST algorithms based on "strict" depth-halving satisfy the access lemma, addressing an open question that was raised several times since 1985, and (iii) yields an extremely short proof for the O(log n log log n) amortized access cost for the path-balance heuristic (proposed by Sleator), matching the best known bound (Balasubramanian and Raman) to a lower-order factor. One of our combinatorial properties is locality. We show that any BST-algorithm that satisfies the access lemma via the sum-of-log (SOL) potential is necessarily local. The other property states that the sum of the number of leaves of the after-tree plus the number of side alternations in the search path must be at least a constant fraction of the length of the search path. We show that a weak form of this property is necessary for sequential access to be linear.
Introduction
Binary Search Trees (BSTs) are fundamental data structures, yet their static variants struggle with non-uniform access patterns. Self-adjusting BSTs, most notably the Splay Tree, address this by dynamically reorganizing themselves after each access, moving frequently queried items closer to the root. The efficiency of these structures is typically proven via the Access Lemma, which guarantees logarithmic amortized cost and robust performance on sequences with high locality.
While the Access Lemma has been the cornerstone of BST analysis for decades, the underlying physical properties that make it hold have remained somewhat opaque. This research uncovers the "secret sauce" of efficient self-adjustment by identifying two simple combinatorial properties—locality and a balance between leaf creation and path alternations—that provide a unified framework for understanding and designing self-adjusting BSTs.
The Combinatorial Framework
The authors focus on "minimally self-adjusting BSTs," which are algorithms that only modify nodes along the search path and ensure the accessed element becomes the new root. The core of their analysis lies in the transformation from the before-path (the sequence of nodes visited during a search) to the after-tree (the new structure formed by those same nodes).
To analyze this transformation, the search path is decomposed into three distinct node sets:
- Subtree-disjoint sets: Nodes whose resulting subtrees do not overlap in the after-tree.
- Monotone sets: Nodes that maintain a consistent side relative to the accessed element and preserve their depth relationship.
- Zigzag sets: Nodes where the search path switches directions (e.g., from a left-child to a right-child).
By applying the standard Sum-of-Log (SOL) potential function to these sets, the authors derive sufficient conditions for the Access Lemma.
Key Insights: Leaves and Turns
A pivotal discovery is the Leaf-Alternation Balance. The authors demonstrate that efficiency is essentially a trade-off between the number of "leaves" in the restructured tree and the number of "turns" (side alternations) in the original search path. Specifically, for the Access Lemma to hold, the sum of these two values must be at least a constant fraction of the total path length. This implies that if a search path is relatively straight (few turns), the restructuring algorithm must create many leaves to maintain balance.
Furthermore, the paper proves that locality is mandatory for proofs using the SOL potential. A "local" algorithm is one that restructures the tree by examining only a small, constant-sized window of the search path. This provides a deep geometric link between an algorithm's complexity and its theoretical efficiency.
Results and Implications
The framework successfully unifies several disparate results in the field. It provides a single proof covering Splay trees, Greedy BSTs, and all local BST algorithms. Notably, it settles a long-standing question from 1985 by proving that "strict depth-halving"—a simpler heuristic than splaying—satisfies the Access Lemma.
Additionally, the authors provide a significantly simplified proof for the $O(\log n \log \log n)$ amortized cost of the "path-balance" heuristic. By viewing these algorithms through a global combinatorial lens rather than a series of specific rotations, the analysis becomes much more intuitive and extensible.
Conclusion
This work moves the field closer to the "Dynamic Optimality Conjecture" by clarifying the requirements for efficient BST self-adjustment. While the current conditions are sufficient for the Access Lemma under the SOL potential, future research may explore whether non-local algorithms or alternative potential functions can unlock even stronger guarantees, such as the elusive "deque" or "traversal" conjectures.
Summary updated