Practical adaptive search trees with performance bounds

Kevin Fray, Kerri Morgan, Anthony Wirth, Justin Zobel

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch


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.

Original languageEnglish
Title of host publicationACSW '17 Proceedings of the Australasian Computer Science Week Multiconference
Subtitle of host publicationJanuary 31 – February 3, 2017. Deakin University Waterfront Campus
EditorsPeter Strazdins, Michael Hobbs
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Electronic)9781450347686
Publication statusPublished - 2017
Externally publishedYes
EventAustralasian Computer Science Conference 2017 - Geelong, Australia
Duration: 31 Jan 20173 Feb 2017
Conference number: 40th


ConferenceAustralasian Computer Science Conference 2017
Abbreviated titleACSC 2017
Internet address


  • Amortized analysis
  • Search trees
  • Splay trees

Cite this