Practical adaptive search trees with performance bounds

Kevin Fray, Kerri Morgan, Anthony Wirth, Justin Zobel

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

Abstract

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
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventAustralasian Computer Science Conference 2017 - Geelong, Australia
Duration: 31 Jan 20173 Feb 2017
Conference number: 40
https://cs.anu.edu.au/conf/acsc2017/

Conference

ConferenceAustralasian Computer Science Conference 2017
Abbreviated titleACSC 2017
CountryAustralia
CityGeelong
Period31/01/173/02/17
Internet address

Keywords

  • Amortized analysis
  • Search trees
  • Splay trees

Cite this

Fray, K., Morgan, K., Wirth, A., & Zobel, J. (2017). Practical adaptive search trees with performance bounds. In P. Strazdins, & M. Hobbs (Eds.), ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference: January 31 – February 3, 2017. Deakin University Waterfront Campus [a23] Association for Computing Machinery (ACM). https://doi.org/10.1145/3014812.3014836