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.7Outline • Basic concepts review • AVL algorithms • Python implementation for AVLsBST Invariants • Binary rooted tree • All left descendants have keys < node’s key • All right descendants have keys > node’s key 8 3 10 61 14 4 7 13Node Height • Leaves: height = 0 • Inner nodes: height = max(children height) +1 • Null tree: height = -1 • Rationale: 8 3 10 61 14 4 7 13 • a subtree operation takes O(h) timeNode Height • Leaves: height = 0 • Inner nodes: height = max(children height) +1 • Null tree: height = -1 • Rationale: 8 3 10 61 14 4 7 13 0 0 0 0 • a subtree operation takes O(h) timeNode Height • Leaves: height = 0 • Inner nodes: height = max(children height) +1 • Null tree: height = -1 • Rationale: 8 3 10 61 14 4 7 13 0 0 0 0 11 • a subtree operation takes O(h) timeNode Height • Leaves: height = 0 • Inner nodes: height = max(children height) +1 • Null tree: height = -1 • Rationale: 8 3 10 61 14 4 7 13 0 0 0 0 11 2 • a subtree operation takes O(h) timeNode Height • Leaves: height = 0 • Inner nodes: height = max(children height) +1 • Null tree: height = -1 • Rationale: 8 3 10 61 14 4 7 13 0 0 0 0 11 22 • a subtree operation takes O(h) timeNode Height • Leaves: height = 0 • Inner nodes: height = max(children height) +1 • Null tree: height = -1 • Rationale: 8 3 10 61 14 4 7 13 0 0 0 0 11 22 3 • a subtree operation takes O(h) timeBalanced Trees • Small tree height means fast operations • Pack many nodes in trees with low heights • Perfectly balanced tree: 2h+1 - 1 nodes • We only care about asymptotic notation • Nodes = f(height) must be exponentialAVL Trees • Regular BST with extra invariants: • absolute value(left child height - right child height) <= 1 • Each subtree is AVL 8 3 10 61 14 4 7 13 0 0 0 0 11 22 3Least dense AVLLeast dense AVL 1Least dense AVL 1 2Least dense AVL 1 2 3 4Least dense AVL 1 2 3 4 5 6 7Least dense AVL 1 2 3 4 5 6 7 8 9 10 11 12Least dense AVL 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 19Least dense structure h-2 h-1 h• Nodes(-1) =0 • Nodes(0) = 1 • Nodes(h) = 1 + Nodes(h-1) + Nodes(h-2) • Looks like Fibonacci, must be exponentialPwnage 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 againKey ObservationKey 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 structureUberpoke (rotations) p p x y A Left Right y x C B C A BHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C pHuh? Do that again ? x y A B C p =Huh? Do that again ? x y A B C p y x C A B p =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, fix up the tree level by levelRebalancing: easy x y A B C k-1 k+1 kk-1 or :( kRebalancing: easy x A k-1 k+1 k-1 or :( Rotate left y B Ck kRebalancing: easy Rotate left k or yx C k+1k-1x yA :( k+1 k+1 k B C k-1A Bk-1kk-1 or or kkRebalancing: easy? x y A B C k-1 k+1 k-1k :(Rebalancing: easy? Rotate leftx y A B C k-1 k+1 k :( k-1Rebalancing: easy? y :(Rotate leftx yA :( k+1 k+1x Ck-1k-1 k-1A Bkk B C k-1WTF? y :(Rotate leftx yA :( k+1 k+1x Ck-1k-1 k-1A Bkk B C k-1WTF? y :(Rotate leftx yA :(k+1 k+1 k-1k-1 k-1 kk B C k-1 x C A BWTF? y :(Rotate leftx yA :(k+1 k+1 k-1k-1 k-1 kk B C k-1 x C A B B cannot be taller than CRebalancing: hack it up x y A C k-1 k+1 k-1k :( z D E k-1 or k-2 k-1 or k-2Rebalancing: hack it up Rotate right k-1 x y A C k-1 k+1 k :( z D E k-1 or k-2 k-1 or k-2Rebalancing: hack it up k-1 k-1 Rotate right k-1 k k-1 or k-2 D E k-1 E Ck-1 k-1 k-1 or or or k-2 k-2 k-2 x y A C k+1 k :( z x z A D k+1 :( yand in the end it’s right x z A D k-1 k+1 k-1 k :( y E C k-1 or k-2 k-1 or k-2and in the end it’s right x z A D k-1 k+1 k :( y E C k-1 or k-2 k-1 or k-2 Rotate left k-1and in the end it’s right Rotate left x z A D k-1 k+1 k-1 k :( y E C k-1 or k-2 k-1 or k-2 z y CE k+1 k k-1 k x A D k-1 or k-2 k-1Rebalancing 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: symmetryRebalancing wrap-up • Know how to fix one level, use that to fix everything along the path to the root • Must recompute height on-the-go • If recomputing for all nodes along the path on each rotation, O(log2(h)) • Why is rebalancing O(log(h))?Python Code ‘cause you can’t live on bubbles and linesAVL Design • BST • incorporate the deletion hack • AVL • inherited from BST, uses AVLnode • AVLnode • does all the heavy liftingReturn values matter! • insert: returns the newly inserted node • delete: returns the deleted node (its parent link still indicates where it was hanging)BST, take 2 1 class BST(object): 2 def __init__(self, NodeType=BSTnode): 3 self.root = None 4 self.NodeType = NodeType 5 self.psroot = self.NodeType(None, None) 6 7 def reroot(self): 8 self.root = self.psroot.left 9 10 def …
View Full Document
Unlocking...