New balanced search trees Siddhartha sen Princeton University Joint work with Bernhard Haeupler and robert e tarjan
New Balanced Search Trees Siddhartha Sen Princeton University Joint work with Bernhard Haeupler and Robert E. Tarjan
Research agenda Elegant solutions to fundamental problems Systematically explore the design space Keep design simple allow complexity in analysis Theoretical justification for elegant solutions Look at what people do in practice
Research Agenda • Elegant solutions to fundamental problems – Systematically explore the design space – Keep design simple, allow complexity in analysis • Theoretical justification for elegant solutions – Look at what people do in practice
Searching: Dictionary problem Maintain a set of items so that Access: find a given item Insert, add a new item Delete: remove an item are efficient Assumption: items are totally ordered, binary comparison is possible
Searching: Dictionary Problem Maintain a set of items, so that Access: find a given item Insert: add a new item Delete: remove an item are efficient Assumption: items are totally ordered, binary comparison is possible
Balanced search trees AVL trees red-black trees binary weight balanced trees LLRB trees, aa trees 2,3 trees multiway B trees etc
Balanced Search Trees AVL trees red-black trees weight balanced trees LLRB trees, AA trees 2,3 trees B trees etc. multiway binary
Agenda Rank-balanced trees [wads 2009] Proof technique Ravl trees [soda 2010] Proofs ° Experiments
Agenda • Rank-balanced trees [WADS 2009] – Proof technique • Ravl trees [SODA 2010] – Proofs • Experiments