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