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 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 Lecture 4 Balanced Binary Search Trees Lecture Overview The importance of being balanced AVL trees De nition Balance Insert Other balanced trees Data structures in general Readings CLRS Chapter 13 1 and 13 2 but di erent approach red black trees Recall Binary Search Trees BSTs rooted binary tree each node has key left pointer right pointer parent pointer See Fig 1 3 41 65 1 2 20 11 1 29 50 26 Figure 1 Heights of nodes in a BST 1 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 x x x Figure 2 BST property BST property see Fig 2 height of node length edges of longest downward path to a leaf see CLRS B 5 for details The Importance of Being Balanced BSTs support insert min delete rank etc in O h time where h height of tree height of root h is between lg n and n Fig 3 vs Perfectly Balanced Path Figure 3 Balancing BSTs balanced BST maintains h O lg n all operations run in O lg n time 2 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 AVL Trees De nition AVL trees are self balancing binary search trees These trees are named after their two inventors G M Adel son Vel skii and E M Landis 1 An AVL tree is one that requires heights of left and right children of every node to di er by at most 1 This is illustrated in Fig 4 k 1 k Figure 4 AVL Tree Concept In order to implement an AVL tree follow two critical steps Treat nil tree as height 1 Each node stores its height This is inherently a DATA STRUCTURE AUGMENTATION procedure similar to augmenting subtree size Alternatively one can just store dif ference in heights A good animation applet for AVL trees is available at this link To compare Binary Search Trees and AVL balancing of trees use code provided here 1 Original Russian article Adelson Velskii G E M Landis 1962 An algorithm for the organization of information Proceedings of the USSR Academy of Sciences 146 263266 English translation by Myron J Ricci in Soviet Math Doklady 3 12591263 1962 3 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 Balance The balance is the worst when every node di ers by 1 Let Nh min nodes Nh Nh 1 Nh 2 1 2Nh 2 Nh 2h 2 1 h lg h 2 Alternatively nth Fibonacci number Nh Fn In fact Nh Fn 2 1 simple induction h Fh rounded to nearest integer 5 1 5 1 618 where golden ratio 2 maxh log n 1 440 lg n AVL Insert 1 insert as in simple BST 2 work your way up tree restoring AVL property and updating heights as you go Each Step suppose x is lowest node violating AVL assume x is right heavy left case symmetric if x s right child is right heavy or balanced follow steps in Fig 5 else follow steps in Fig 6 then continue up to x s grandparent greatgrandparent 4 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 x k 1 y y A k 1 Left Rotate x k 1 C B k k k 1 x k k 1 B A x k 1 y z A k C C B k 1 k x k 1 Left Rotate x k 1 k k A C B Figure 5 AVL Insert Balancing x k 1 y z A k Right Rotate z Left Rotate x k 1 k k 1 k 1 A k 1 or k 2 z x k 1 y D B k 1 C Figure 6 AVL Insert Balancing 5 B or k 2 C k D k 1 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 Example An example implementation of the AVL Insert process is illustrated in Fig 7 x 29 left left case Insert 23 3 41 65 1 2 20 11 41 50 1 29 11 23 Done Insert 55 3 41 3 41 2 20 65 1 2 20 50 1 26 11 29 23 23 Done 3 41 23 2 20 2 65 1 26 50 29 41 2 20 65 1 1 26 x 65 left right case 11 50 2 29 1 26 26 11 65 1 20 50 1 29 11 55 23 1 26 1 55 50 65 29 Figure 7 Illustration of AVL Tree Insert Process Comment 1 In general process may need several rotations before an Insert is completed Comment 2 Delete min harder but possible 6 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 Balanced Search Trees There are many balanced search trees AVL Trees B Trees 2 3 4 Trees BB Trees Red black Trees Splay Trees Skip Lists Scapegoat Trees Treaps Adel son Velsii and Landis 1962 Bayer and McCreight 1972 see CLRS 18 Nievergelt and Reingold 1973 CLRS Chapter 13 Sleator and Tarjan 1985 Pugh 1989 Galperin and Rivest 1993 Seidel and Aragon 1996 Note 1 Skip Lists and Treaps use random numbers to make decisions fast with high probability Note 2 Splay Trees and Scapegoat Trees are amortized adding up costs for several operations fast on average 7 Lecture 4 Balanced Binary Search Trees 6 006 Spring 2008 Splay Trees Upon access search or insert move node to root by sequence of rotations and or doublerotations just like AVL trees Height can be linear but still O lg n per operation on average amortized Note We will see more on amortization in a couple of lectures Optimality For BSTs cannot do better than O lg n per search in worst case In some cases can do better e g in order traversal takes n time for n elements put more frequent items near root A Conjecture Splay trees are O best BST for every access pattern With fancier tricks can achieve O lg lg u performance for integers 1 u Van Ernde Boas see 6 854 or 6 851 Advanced Data Structures Big Picture Abstract Data Type ADT interface spec e g Priority Queue Q new empty queue Q insert x x Q deletemin vs Data Structure DS algorithm for each op There are many possible DSs for one ADT One example that we will discuss much later in the course is the heap priority queue 8
View Full Document
Unlocking...