MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 6 006 Recitation Build 2008 7 Outline Basic concepts review AVL algorithms Python implementation for AVLs BST Invariants 8 Binary rooted tree All left descendants have keys node s key All right descendants have keys node s key 10 3 1 14 6 4 7 13 Node Height Leaves height 0 Null tree height 1 8 Inner nodes height max children height 1 Rationale a subtree operation takes O h time 10 3 1 14 6 4 7 13 Node Height Leaves height 0 Null tree height 1 8 Inner nodes height max children height 1 10 3 1 14 6 0 Rationale a subtree operation takes O h time 4 0 7 0 13 0 Node Height 8 Leaves height 0 Inner nodes height max children height 1 Null tree height 1 10 3 1 6 1 14 0 Rationale a subtree operation takes O h time 4 0 7 0 13 0 1 Node Height 8 Leaves height 0 2 Inner nodes height max children height 1 Null tree height 1 10 3 1 6 1 14 0 Rationale a subtree operation takes O h time 4 0 7 0 13 0 1 Node Height 8 Leaves height 0 Inner nodes height max children height 1 Null tree height 1 2 2 10 3 1 6 1 14 0 Rationale a subtree operation takes O h time 4 0 7 0 13 0 1 Node Height 8 Leaves height 0 2 2 Inner nodes height max children height 1 Null tree height 1 3 10 3 1 6 1 14 0 Rationale a subtree operation takes O h time 4 0 7 0 13 0 1 Balanced Trees Small tree height means fast operations Pack many nodes in trees with low heights Perfectly balanced tree 2 1 nodes We only care about asymptotic notation Nodes f height must be exponential h 1 AVL Trees 8 Each subtree is AVL 2 2 Regular BST with extra invariants absolute value left child height right child height 1 3 10 3 1 6 1 14 0 4 0 7 0 13 0 1 Least dense AVL Least dense AVL 1 Least dense AVL 2 1 Least dense AVL 3 4 2 1 Least dense AVL 5 6 3 7 4 2 1 Least dense AVL 8 5 11 12 10 6 9 3 7 4 2 1 Least dense AVL 13 8 18 20 16 19 17 5 11 12 15 14 10 6 9 3 7 4 2 1 Least dense structure Nodes 1 0 h Nodes 0 1 Nodes h 1 Nodes h 1 Nodes h 2 Looks like Fibonacci must be exponential h 2 h 1 Pwnage with AVLs 101 Goals Reuse the code we wrote before Start with an AVL end up with an AVL Managerial Input the doh words Insert and delete like it s a BST Patch to make it an AVL again Key Observation Key Observation Adding or removing a node only upsets the heights on a single path to the root Pwnage with AVLs 201 Will obviously have to move nodes around But must keep track of Height Augmented data Invariants for AVL BST Need a tool that preserves most structure Uberpoke rotations p p Left x Right y A B y C x A C B Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p x y A B C Huh Do that again p p x y A B C y x A C B Rebalancing Rotations are quite teh uberpoke Need a master plan for using them Managerial Input call it rebalancing Divide and conquer start from the bottom x up the tree level by level Rebalancing easy k 1 x y A k 1 or k B k 1 C k Rebalancing easy k 1 Rotate left x y A k 1 or k B k 1 C k Rebalancing easy k 1 Rotate left x y A k 1 or k B k 1 C k k or k 1 k 1 A y x k 1 C B k 1 or k k Rebalancing easy k 1 x y A k B k 1 C k 1 Rebalancing easy k 1 Rotate left x y A k B k 1 C k 1 Rebalancing easy k 1 x y A k B k 1 C k 1 y Rotate left k 1 k 1 A x C B k k 1 WTF k 1 x y A k B k 1 C k 1 y Rotate left k 1 k 1 A x C B k k 1 WTF k 1 x y A k B k 1 C k 1 y Rotate left k 1 k 1 A x C B k k 1 WTF k 1 x y A k B k 1 C k 1 y Rotate left k 1 k 1 A B cannot be taller than C x C B k k 1 Rebalancing hack it up k 1 y A k k 1 or k 2 x D z k 1 C E k 1 k 1 or k 2 Rebalancing hack it up k 1 y A k k 1 or k 2 x D z k 1 Rotate right C E k 1 k 1 or k 2 Rebalancing hack it up k 1 D x x y A k k 1 or k 2 z k 1 Rotate right C E k 1 k 1 or k 2 k 1 z A k 1 or k 2 y D k 1 or k 2 k 1 E k C k 1 and in the end it s right k 1 x z A k 1 or k 2 y D k 1 or k 2 k 1 E k C k 1 and in the end it s right k 1 x z A k 1 or k 2 Rotate left y D k 1 or k 2 k 1 E k C k 1 and in the end it s right k 1 x z A k 1 or k 2 Rotate left y D k 1 or k 2 k 1 E k k C k 1 k 1 A z k 1 x y D k 1 or k 2 E k C k 1 Rebalancing one level AVL violation at current node Right is than left Right left taller than right right Rotate right to the right Either way rotate current to the left Left is heavier than right symmetry Rebalancing wrap up Know how to x one …
View Full Document
Unlocking...