DIMACS Theoretical Computer Science Seminar

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


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.

See: http://paul.rutgers.edu/~yixinxu/theory-fall11.html