普林斯顿大学：平衡查找树（PPT讲稿）New Balanced Search Trees

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