Practical adaptive search trees with performance bounds

Dynamic binary search trees are a fundamental class of dictionary data structure. Amongst these, the splay tree is space efficient and has amortized running-time bounds. In practice, splay trees perform best when the access sequence has regions of atypical items. Continuing a tradition started by Sleator and Tarjan themselves, we introduce a relaxed version, the α-Frequent Tree, that performs fewer rotations than the standard splay tree. We prove that the α-frequent trees inherit many of the distribution-sensitive properties of splay trees. 

Meanwhile, Conditional Rotation trees [Cheetham et al.] maintain access counters - one at each node - and have an excellent experimental reputation. By adding access counters to α-frequent trees, we create Splay Conditional Rotation (SCR) trees. These have the experimental performance of other counter-based trees, and the amortized bounds of splay trees.