A self-adjusting binary search tree is one that rearranges itself as it is used, moving recently or frequently requested keys toward the root. The theory of these trees has a famous open question, the dynamic optimality conjecture: is there one online tree that, on every request sequence, costs at most a constant factor more than the best possible offline tree that knows the future? The leading candidates are the splay tree, Greedy BST, and a newer grouped variant called GGREEDY. They have been studied almost entirely on paper. Their cost is counted as nodes touched, and none of the core papers runs them on real hardware or real request logs. That count leaves out a physical fact. Restructuring a tree on a read turns a read into a series of pointer writes, and on modern machines those writes can cost more than the comparisons they save.
We propose to treat each restructuring as an adaptation with a price, in the sense of case-based reasoning. That field learned long ago that the right way to choose a stored solution is by how expensive it will be to adapt, not by how similar it looks. The proposal has two parts. The first is the first wall-clock benchmark of the dynamic-optimality candidates on the traces already used for learned search trees. The second is a restructuring gate that is cheap enough to run on every access. It estimates, from a record of past restructuring episodes, whether rotating now will pay for itself, and skips the rotation when it will not. In two sentences: current candidates for dynamic optimality rotate on every access because their theory treats rotations as free. We measure what that costs on real traces, and we test whether a constant-time, experience-based estimate of when rotating pays off recovers most of the adaptivity at a fraction of the write traffic.
Core Claim
We make two claims. The first is that on skewed real workloads, the gap between self-adjusting trees and plain balanced trees in wall-clock time is set mainly by restructuring writes, not by search depth. If so, the theoretical cost model misranks the candidates. The second is that a gate that restructures only when predicted savings exceed rotation cost is a concrete, testable instance of adaptation-cost similarity. It can bring a Greedy-style tree within a small factor of its full-adaptation access cost while doing many fewer writes, and it beats both fixed-rate thinning of rotations and learned static priorities. We write the gate's decision as
$$\text{restructure at time } t \iff \hat{S}(h_t) > c_w \cdot r_t,$$
where $h_t$ is a short hashed signature of the recent access window, $\hat{S}(h_t)$ is the average number of future comparisons saved by past restructurings taken under signature $h_t$, $r_t$ is the number of pointer writes the candidate rotation would perform, and $c_w$ is the measured cost of a write relative to a comparison on the target machine. The inequality simply says to adapt when the expected benefit exceeds the adaptation cost. The contribution is in how $\hat{S}$ is estimated and in keeping that estimate cheap.
What Prior Work Provides and Leaves Open
The mechanism comes from case-based reasoning. The Re-application Costs and Relevance approach in Case-Based Similarity Assessment: Estimating Adaptability from Experience records past adaptation episodes and their costs. It uses those records to predict the cost of adapting a new candidate, and in the DIAL disaster-planning system this cut adaptation effort from 65 to 36 primitive memory operations. We reuse this idea directly: past restructurings become stored episodes, and $\hat{S}$ is their recorded payoff.
Learning to Integrate Multiple Knowledge Sources for Case-Based Reasoning constrains the design. It showed that growing adaptation libraries impose a retrieval overhead that can make wall-clock time worse. This is why our episode store is a fixed-size table indexed by hashed signatures with O(1) lookup, not a growing library searched by similarity.
Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures supplies a second ingredient, "censors." These are compiled records of failed adaptations that stop a planner from retrying them, and they took 4-goal logistics planning from 916 to about 32 seconds. Our analogue is thrash detection. When a restructuring is largely undone within a short horizon, its signature is marked, and future restructurings under that signature are suppressed.
This connects to the dynamic-optimality literature. Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm shows that Greedy-Future can pay at least twice the optimum and that reversing a sequence can roughly double its cost. These are precisely cases where local restructuring rules keep doing work that does not pay off, so they give us adversarial test sequences.
The candidate algorithms come from three papers. On Dynamic Optimality for Binary Search Trees gives Greedy BST in the geometric view, where a tree execution is a set of points in key-by-time space that must satisfy a rectangle condition. The Group Access Bounds for Binary Search Trees gives GGREEDY, with an $O(\sqrt{\log n})$ competitive ratio and the unified bound. Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition proves linear-time behavior on structured traversal sequences. All four of these papers report no implementation, no timing, and no real traces. The first paper itself notes that turning geometric point additions into efficient pointer-level rotations is not trivial.
The empirical side sets the bar. Learning Augmented Binary Search Trees builds a Treap, a tree whose shape is set by per-key priorities, with priorities taken from predicted frequencies. It evaluates on CAIDA and AOL and reports that model inference ("oracle overhead") can wipe out the time saved by shorter paths. On the Power of Learning-Augmented Search Trees adds a working-set priority for temporal locality, but leaves out spatial locality, the unified bound, and the cost of querying the oracle. Our gate addresses the oracle-cost problem by construction, since its "model" is a table lookup. The Greedy and GGREEDY backbones cover the spatial locality that learned Treaps miss.
Research Program
The first step is engineering. We will build pointer-level, array-backed implementations of splay trees, Greedy BST, and GGREEDY that are careful about cache behavior, plus Red-Black, AVL, and both learned Treaps. All trees will share one node layout and allocator so that differences come from the algorithms. For Greedy we use the known online-to-tree transformation from the geometric view and report its constant-factor overhead separately. That number is itself an answer to the open implementation question.
The second step is measurement. For every tree and trace we record comparisons, nodes touched, pointer writes, cache misses from hardware counters, and nanoseconds per operation. We also need an estimate of how far each algorithm is from optimal. Exact offline OPT cannot be computed at trace scale, so we bracket it. We run offline Greedy-Future on each trace, which gives an upper bound on OPT. We also compute a standard combinatorial lower bound on OPT from the point-set view. From these we report an interval of empirical competitive ratios.
The third step is the gate itself. It keeps a table of $2^{k}$ entries, indexed by a hash of the last few accessed keys' coarse key ranges and repeat flags. Each entry stores a running mean of how many comparisons past restructurings under that signature saved over a fixed horizon, along with a thrash counter that implements the censor. The gate wraps both splay and Greedy.
The fourth step is analysis. We test whether the gated tree keeps a worst-case $O(\log n)$ amortized guarantee. One way is a fallback that forces a restructuring whenever an access path exceeds $c \log n$, and we will try to prove a bound for that variant.
Baselines
The naive reference point is a Red-Black tree, since it performs no restructuring on reads. It is the structure production systems actually use, and any adaptive tree must beat it in wall-clock time, not just in comparisons, to matter.
The strongest existing adaptive methods are the splay tree and the working-set learned Treap of On the Power of Learning-Augmented Search Trees. The splay tree is the classical zero-oracle adaptive tree. The learned Treap is the only published structure that combines learned frequencies with temporal locality. The most specific reported number comes from Learning Augmented Binary Search Trees: on synthetic Zipfian data, the learned Treap uses 25% fewer comparisons than splay trees and over 30% fewer than AVL and Red-Black trees. For CAIDA and AOL we found no reported numeric result on Lacuna; that paper reports only that the learned Treap was competitive with Red-Black trees. For wall-clock time on any of these traces we likewise found no reported result on Lacuna. We will therefore re-run every baseline ourselves.
Fairness rules are as follows. The learned Treap's predictor gets the same training prefix our gate uses to warm its table, and we charge its inference time. Every method gets the same tuning budget of 20 configurations per trace on a held-out prefix. All runs are single-threaded on the same pinned core.
The key ablation is a gate that fires at random, at the same rate the learned gate fires. This isolates whether the recorded adaptation-cost signal matters, or whether any thinning of rotations would do. We also remove the thrash censor to measure its separate contribution.
Beating the baselines means the following. The gated tree must have lower median and 99th-percentile wall-clock time than both the Red-Black tree and the learned Treap on at least CAIDA and AOL. It must also be significantly faster than the rate-matched random gate across seeds.
Why not just…?
Why not just use a splay tree? It adapts with no oracle at all. However, it writes on every read, and the Zipfian comparison result in Learning Augmented Binary Search Trees already shows it leaves depth unrealized. Our measurements will show whether writes or depth dominate its wall-clock cost. If ungated splay turns out to be fastest, that is a clean negative result for our second claim, and we will report it as such.
Why not just splay with a fixed probability, or on every k-th access? This is the real threat, because it cuts writes with no bookkeeping at all. The rate-matched random-gate ablation is designed to settle it. If the random gate matches the learned gate, then the adaptation-cost part of the idea adds nothing beyond thinning, and the contribution shrinks to the benchmark alone.
Why not just use a learned-priority Treap with working-set updates? It is theoretically clean. Its authors, however, identify the lack of spatial locality as open, and its predecessor reports that inference cost can erase its gains. We charge that cost explicitly. We also include sequential and range-scan traces, where Greedy-style trees should win because they capture spatial locality.
Why not just keep a Red-Black tree? It remains the right answer if skew is mild. We map the Zipf skew threshold below which it wins, so the result tells practitioners when adaptivity is worth paying for.
Proposed Experiments and Decisive Checks
The workloads are the CAIDA IP flow traces and the 21-million-query AOL log, both from Learning Augmented Binary Search Trees. We add synthetic Zipf traces with skew from 0.6 to 1.5, and the uniform, adversarial, and mixture streams used in On the Power of Learning-Augmented Search Trees. Finally, we include sequential, deque-style, and reversed sequences built on the F-tree and (k, r)-tree constructions of Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm, which stress restructuring that does not pay off.
There are three decisive checks. The first tests whether, on AOL and CAIDA, the ranking of trees by nodes touched disagrees with the ranking by wall-clock time. If it does, the theoretical cost model is shown empirically to misrank the candidates. The second tests whether gated Greedy keeps within 10% of ungated Greedy's comparison count while performing at least 40% fewer writes, and whether it beats the rate-matched random gate. The third tests whether, on the reversal and mixed-stable sequences, the censor removes most of the extra cost that the lower-bound paper predicts for Greedy-Future. Throughout, we report the bracketed empirical competitive ratio, which gives the dynamic optimality conjecture its first measurement on real request logs.
References
- Case-Based Similarity Assessment: Estimating Adaptability from Experience
- Learning to Integrate Multiple Knowledge Sources for Case-Based Reasoning
- Storing and Indexing Plan Derivations through Explanation-based Analysis of Retrieval Failures
- Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm
- On Dynamic Optimality for Binary Search Trees
- The Group Access Bounds for Binary Search Trees
- Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
- Learning Augmented Binary Search Trees
- On the Power of Learning-Augmented Search Trees