BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Rank-Balanced Trees
DTSTART:20090525T161500
DTSTAMP:20260407T002711Z
UID:cbff6c41aef34bca4cb7e2cefb1b7e2080dfe6751e3a9f4c195e585e
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Robert E. Tarjan\, Princeton University\, USA\nSince the
  invention of AVL trees in 1962\, a wide variety of ways to balance binary
  search trees have been proposed.  Notable are red-black\ntrees\, 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 tre
 es has not been fully explored.  We introduce the rank-balanced tree\, a r
 elaxation of AVL trees. Rank-balanced trees have properties like those of 
 red-black trees but better. We also introduce a novel way to analyze balan
 ced trees\, which we use to show that in rank-balanced trees (as well as i
 n red-black trees)\, rebalancing after insertions and deletions modifies n
 odes exponentially infrequently in their height. \nThis is joint work with
  Bernhard Haeupler and Siddhartha Sen.\n\nBio: Robert E. Tarjan is the Jam
 es S. McDonnell Distinguished University Professor of Computer Science at 
 Princeton University and a Senior Fellow at HP Labs.  He is an expert in t
 he design and analysis of combinatorial algorithms and data structures.  H
 e has written over 175 refereed journal articles and two books.  He was aw
 arded the Nevanlinna Prize in Informatics in 1982 and the A. M. Turing Awa
 rd in 1986\, and is a member of the U.S. National Academy of Sciences and 
 the U.S. National Academy of Engineering.\n\nR. Tarjan's homepage  
LOCATION:INM202
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR