Rank-Balanced Trees
Event details
| Date | 25.05.2009 |
| Hour | 16:15 |
| Speaker | Prof. Robert E. Tarjan, Princeton University, USA |
| Location |
INM202
|
| Category | Conferences - Seminars |
Since the invention of AVL trees in 1962, a wide variety of ways to balance binary search trees have been proposed. Notable are red-black
trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We introduce the rank-balanced tree, a relaxation of AVL trees. Rank-balanced trees have properties like those of red-black trees but better. We also introduce a novel way to analyze balanced trees, which we use to show that in rank-balanced trees (as well as in red-black trees), rebalancing after insertions and deletions modifies nodes exponentially infrequently in their height.
This is joint work with Bernhard Haeupler and Siddhartha Sen.
Bio: Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a Senior Fellow at HP Labs. He is an expert in the design and analysis of combinatorial algorithms and data structures. He has written over 175 refereed journal articles and two books. He was awarded the Nevanlinna Prize in Informatics in 1982 and the A. M. Turing Award in 1986, and is a member of the U.S. National Academy of Sciences and the U.S. National Academy of Engineering.
R. Tarjan's homepage
Practical information
- General public
- Free