Rehabilitation Of An Unloved Child: Semi-splaying

摘要

Splay trees are widely considered as the classic examples of self-adjusting binary search trees and are part of most courses on data structures and algorithms. Already in the first seminal paper on splay trees (J. Assoc. Comput. Mach. 1985; 32(3):652-686) alternative operations were introduced, among which is semi-splaying. On the one hand, the analysis of semi-splaying gives a smaller constant for the amortized complexity, but on the other hand the authors write: Whether any version of semi-splaying is an improvement over splaying depends on the access sequence. Semi-splaying may be better when the access pattern is stable, but splaying adapts much faster to changes in usage. Maybe this sentence was the reason that nobody seriously ran tests to compare the performance of semi-splaying and splaying. Semi-splaying is conceptually simpler than splaying, has the same asymptotic amortized complexity and, as will be clear from empirical data presented in this paper, the practical performance is better for a very broad variety of access patterns. Therefore, its efficiency is a good reason to use semi-splaying for applications instead of its more prominent brother. Moreover, its simplicity also makes it very attractive for teaching purposes.