Title: Fast Adaptive Trees with Performance Bounds
Speaker: Tony Wirth, The University of Melbourne
Date: Wednesday, October 26, 2011 11:00-12:00pm
Location: CoRE Bldg, CoRE 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Dynamic binary search trees are a fundamental kind of dictionary data structure. Amongst these, the splay tree is space efficient and has amortized running-time bounds, but often performs poorly, unless the access sequence has regions of atypical items. We introduce a relaxed version of the splay tree, the ?-Frequent Tree, that performs fewer rotations. We prove that the ?-frequent trees share many distribution-sensitive properties with splay trees.
Conditional Rotation trees, by Cheetham et al., use access counters at each node and have an excellent experimental reputation. We add access counters to ?-frequent trees to create Splay Conditional Rotation (SCR) trees. They have the performance of other counter-based trees, on the tests presented, and the amortized bounds of splay trees.
This is joint work with Kevin Fray, Kerri Morgan, and Justin Zobel.