6 006 Introduction to Algorithms Lecture 4 Prof Patrick Jaillet Lecture Overview 1 5 6 Review Binary Search Trees Importance of being balanced Balanced BSTs AVL trees definition rotations insert Other balanced trees 1 7 10 12 7 5 10 6 12 Binary Search Trees BSTs root Each node x has key x Pointers left x right x p x Property for any node x For all nodes y in the left subtree of x key y key x For all nodes y in the right subtree of x key y key x 10 5 1 12 6 7 leaf height 3 BST for runway reservation system 5 1 49 R 37 41 46 49 56 current landing times 37 41 now x 46 49 x x 56 3 1 41 time mins x remove t from the set when a plane lands R 41 46 49 56 add new t to the set if no other landings are scheduled within 3 minutes from t 44 reject 46 in R 53 ok delete insert conflict checking take O h where h is the height of the tree 1 1 56 1 37 46 4 1 49 2 1 1 41 56 1 46 1 53 The importance of being balanced for n nodes vs Perfectly Balanced h log n Path h n Balanced BST Strategy Augment every node with some property Define a local invariant on property Show prove that invariant guarantees log n height Design algorithms to maintain property and the invariant AVL Trees Definition Adelson Velskii and Landis 62 3 41 Property for every node store its height augmentation Leaves have height 0 NIL has height 1 65 1 2 20 0 11 1 29 50 0 26 0 x Invariant for every node x the heights of its left child and right child differ by at most 1 k k 1 AVL trees have height log n Let nh be the minimum number of nodes of an AVL tree of height h We have nh 1 nh 1 nh 2 nh 2nh 2 nh 2h 2 h 2 lg nh Better bounds h h 1 h 2 Rotations RIGHT ROTATE B B A LEFT ROTATE A A B Rotations maintain the inorder ordering of keys a b c a A b B c 1 2 1 LEFT ROTATE 1 3 2 3 Insertions Deletions Insert new node u as in the simple BST Can create imbalance Work your way up the tree restoring the balance Similar issue solution when deleting a node h 1 h 1 h 2 u Balancing Let x be the lowest violating node Assume the right child of x is deeper than the left child of x x is right heavy Scenarios Case 1 Right child y of x is right heavy Case 2 Right child y of x is balanced Case 3 Right child y of x is left heavy x y A B C Case 1 y is right heavy x LEFT ROTATE x y k 1 y x k 1 C A k 1 B C k k 1 A B k 1 k Case 2 y is balanced x y LEFT ROTATE x y k 1 x k 1 C A k B C Same as Case 1 k k 1 A B k k Case 3 y is left heavy x y LEFT ROTATE x y k 1 x k 1 C A k B C k 1 Need to do more k 1 A B k k 1 Case 3 y is left heavy RIGHT ROTATE y LEFT ROTATE x x y k 1 A k 1 k z C z k k 1 k 1 B k 1 or k 2 D And we are done y x k 1 A B or k 2 D C k 1 Examples of insert balancing Insert 23 3 41 41 65 1 2 20 11 x 29 left left case 50 1 29 11 23 Done Insert 55 3 41 3 41 50 1 26 29 23 2 20 65 1 2 20 11 23 23 1 26 50 29 Done 3 41 41 2 20 65 1 1 26 x 65 left right case 11 50 2 29 1 26 26 11 65 1 20 2 20 2 65 50 1 29 55 11 23 1 26 1 55 50 29 65 Balanced Search Trees AVL trees Adelson Velsii and Landis 1962 Red black trees see CLRS 13 Splay trees Sleator and Tarjan 1985 Scapegoat trees Galperin and Rivest 1993 Treaps Seidel and Aragon 1996
View Full Document
Unlocking...