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 pathProblem 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