Practical adaptive search trees with performance bounds

Dynamic binary search trees are a fundamental class of dic- tionary 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 coun- ters to α-frequent trees, we create Splay Conditional Rota- tion (SCR) trees. These have the experimental performance of other counter-based trees, and the amortized bounds of splay trees.