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
Problem with bsts: Imbalance How to bound height? Maintain local balance condition a rebalance after insert/delete balanced tree Restructure after each access self-adjusting tree
Problem with BSTs: Imbalance How to bound height? • Maintain local balance condition, rebalance after insert/delete balanced tree • Restructure after each access self-adjusting tree a b c d e f
Problem with bsts: Imbalance How to bound height? Maintain local balance condition a rebalance after insert/delete balanced tree Restructure after each access self-adjusting tree Store balance information in nodes rebalance bottom-up or top-down) Update balance information Restructure along access path
Problem with BSTs: Imbalance How to bound height? • Maintain local balance condition, rebalance after insert/delete balanced tree • Restructure after each access self-adjusting tree Store balance information in nodes, rebalance bottom-up (or top-down) • Update balance information • Restructure along access path a b c d e f
Restructuring primitive: Rotation right left B C Preserves symmetric order Changes heights Takes o(1) time
Restructuring primitive: Rotation Preserves symmetric order Changes heights Takes O(1) time y x A B C x y B C A right left
Known Balanced bsts AVL trees small height red-black trees little rebalancing weight balanced trees LLRB trees, aa trees etc Goal: small height little rebalancing simple algorithms
Known Balanced BSTs AVL trees red-black trees weight balanced trees LLRB trees, AA trees etc. Goal: small height, little rebalancing, simple algorithms − small height − little rebalancing
Ranked Binary trees Each node has integer rank Convention: leaves have rank-1 Estimate for heigl cht rank difference of child rank of parent- rank of child i-child; node of rank difference i i,i-node: children have rank differences i and j
Ranked Binary Trees Each node has integer rank Convention: leaves have rank 0, missing nodes have rank -1 rank difference of child = rank of parent − rank of child i-child: node of rank difference i i,j-node: children have rank differences i and j Estimate for height