Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 28, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Robert E. Tarjan (Princeton Univ. and HP Labs)
Since the invention of AVL trees in 1962, a wide variety of ways to balance binary search trees has 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.
Joint work with Bernhard Haeupler and Siddhartha Sen.
Automatic MiSe System Software Version 1.4803M | admin login