6 006 Introduction to Algorithms Lecture 4 Prof Piotr Indyk Lecture Overview 1 5 6 Review Binary Search Trees Importance of being balanced Balanced BSTs AVL trees definition rotations insert 7 10 12 7 5 1 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 The importance of being balanced for n nodes 1 7 5 6 5 10 7 1 10 6 12 12 h log n h n Balanced BST Strategy Augment every node with some data Define a local invariant on data Show prove that invariant guarantees log n height Design algorithms to maintain data and the invariant AVL Trees Definition Adelson Velskii and Landis 62 Data for every node maintain its height augmentation Leaves have height 0 NIL has height 1 Invariant for every node x the heights of its left child and right child differ by at most 1 32 7 5 1 21 10 6 4 0 10 0 1 12 0 x k k 1 AVL trees have height log n Invariant for every node x the heights of its left child and right child differ by at most 1 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 h 1 nh 2h 2 h 2 lg nh The constant 2 can be improved How can we maintain the invariant h 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 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 We will fix the subtree of x and move up 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 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 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 Conclusions Can maintain balanced BSTs in O log n time per insertion Search etc take O log n time 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 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 7 5 1 2 1 6 4 0 3 10 0 1 12 0 And some people like to do nothing
View Full Document
Unlocking...