Georgia Institute of Technology College of Sciences

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 http://www.arc.gatech.edu/arc4.php. The event begins at 9:00AM.