Deletion without Rebalancing in Balanced Search Trees

Joint ACO and ARC Colloquium
Friday, April 1, 2011 - 11:00am for 1 hour (actually 50 minutes)
TSRB Banquet Hall, 85 5th St.
Robert Tarjan – Princeton University
Deletion in a balanced search tree is a problematic operation: rebalancing on deletion has more cases than rebalancing on insertion, and it is easy to get wrong. We describe a way to maintain search trees so that rebalancing occurs only on insertion, not on deletion, but the tree depth remains logarithmic in the number of insertions, independent of the number of deletions. Our results provide theoretical justification for common practice in B-tree implementations, as well as providing a new kind of balanced binary tree that is more efficient in several ways than those previously known. This work was done jointly with Sid Sen. This is a day-long event of exciting talks by meta-learning meta-theorist Nina Balcan, security superman Wenke Lee and prolific mathematician Prasad Tetali, posters by the 10 ARC fellowship winners for the current academic year. All details are posted at The event begins at 9:00AM.