April 1, 2011
Robert Tarjan
Princeton University
Title: Deletion without Rebalancing in Balanced Search Trees.
Abstract:
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.
Biography
Robert Endre Tarjan is a renowned expert in the design and analysis of algorithms who has discovered the most efficient known algorithms and data structures for problems from a wide variety of application areas.
Prof. Tarjan is a member of the National Academy of Sciences and the National Academy of Engineering, was awarded the first Nevanlinna Prize in Information Science in 1983 and the Turing Award in 1986. He is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a senior fellow at HP Labs.
