Conference Proceedings

Practical adaptive search trees with performance bounds

K Fray, K Morgan, A Wirth, J Zobel

Proceedings of the Australasian Computer Science Week Multiconference | ACM Press | Published : 2017

Abstract

© 2017 Copyright held by the owner/author(s). Publication rights licensed to ACM. 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..

View full abstract