6 006 Intro to Algorithms Recitation 04 February 11 2011 AVL Trees Recall the operations e g find insert delete of a binary search tree The runtime of these operations were all O h where h represents the height of the tree defined as the length of the longest branch In the worst case all the nodes of a tree could be on the same branch In this case h n so the runtime of these binary search tree operations are O n However we can maintain a much better upper bound on the height of the tree if we make efforts to balance the tree and even out the length of all branches AVL trees are binary search trees that balances itself every time an element is inserted or deleted Each node of an AVL tree has the property that the heights of the sub tree rooted at its children differ by at most one Upper Bound of AVL Tree Height We can show that an AVL tree with n nodes has O log n height Let Nh represent the minimum number of nodes that can form an AVL tree of height h If we know Nh 1 and Nh 2 we can determine Nh Since this Nh noded tree must have a height h the root must have a child that has height h 1 To minimize the total number of nodes in this tree we would have this sub tree contain Nh 1 nodes By the property of an AVL tree if one child has height h 1 the minimum height of the other child is h 2 By creating a tree with a root whose left sub tree has Nh 1 nodes and whose right sub tree has Nh 2 nodes we have constructed the AVL tree of height h with the least nodes possible This AVL tree has a total of Nh 1 Nh 2 1 nodes Nh 1 and Nh 2 coming from the sub trees at the children of the root the 1 coming from the root itself The base cases are N1 1 and N2 2 From here we can iteratively construct Nh by using the fact that Nh Nh 1 Nh 2 1 that we figured out above Using this formula we can then reduce as such Nh Nh 1 Nh 2 1 Nh 1 Nh 2 Nh 3 1 Nh Nh 2 Nh 3 1 Nh 2 1 Nh 2Nh 2 h Nh 2 2 1 2 3 4 5 h 2 log Nh log 2 2 log Nh h h O log Nh Showing that the height of an AVL tree is indeed O log n 6 7 8 6 006 Intro to Algorithms Recitation 04 February 11 2011 AVL Rotation We ve shown that if we can indeed keep the tree balanced we can keep the height of the tree at O log n which speeds up the worst case runtime of the tree operations The next step is to show how to keep the tree balanced as we insert and delete nodes from the tree Since we need to maintain the property that the height of the children must not differ by more than 1 for every node it would be useful if we could access a node s height without needing to examine the entire length of the branch that it s on Recall that for a binary search tree each node contained a key left right and a parent AVL trees will also contain an additional parameter height to help us keep track of balance There are two operations needed to help balance an AVL tree a left rotation and a right rotation Rotations simply re arrange the nodes of a tree to shift around the heights while maintaining the order of its elements Making a rotation requires re assigning left right and parent of a few nodes but nothing more than that Rotations are O 1 time operations AVL Insertion Now delegating to recitation notes from fall of 2009 6 006 Intro to Algorithms Recitation 04 February 11 2011 When we insert a node into node n we have three possible cases 1 Children of n have same height k Inserting into either sub tree will still result in a valid AVL tree 2 The left child of n is heavier than the right child Inserting into the left child may imbalance the AVL tree 3 The right child of n is heavier than the left child Inserting into the right child may imbalance the AVL tree When the AVL tree gets imbalanced we must make rotations in the tree to re arrange the nodes so that the AVL tree becomes balanced once again Note that adding a node into a k height tree does not always turn it into a k 1 height tree since we could have inserted the node on a shorter branch of that tree However for now we are looking specifically at the situations where adding a node into a k height tree does turn it into a k 1 height tree Let s examine the case where we insert a node into a heavy right child 6 006 Intro to Algorithms Recitation 04 February 11 2011 There are two cases here that will imbalance the AVL tree We will once again look at the problem on a case by case basis In the first case B had height k 1 C had height k 1 and a node was inserted into C making its current height k We call a left rotation on n to make the y node the new root and 6 006 Intro to Algorithms Recitation 04 February 11 2011 shifting the B sub tree over to be n s child The order of the elements are preserved In both trees A n B y C but after the rotation we get a balanced tree In the second case B had height k 1 C had height k 1 and a node was inserted into B making its current height k In this case no single rotation on a node will result in a balanced tree but if we make a right rotation on y and then a left rotation on x we end up with a happy AVL tree If we insert a node into a heavy left child instead the balancing solutions are flipped i e right rotations instead of left rotations and vice versa but the same concepts apply AVL insertions are binary search tree insertions plus at most two rotations Since binary search tree insertions take O h time rotations are O 1 time and AVL trees have h O log n AVL insertions take O log n time There are only a finite number of ways to imbalance an AVL tree after insertion AVL insertion is simply identifying whether or not the insertion will imbalance the tree figuring out what imbalance case it causes and making the rotations to fix that particular case AVL Deletion AVL deletion is not too different from insertion The key difference here is that unlike insertion which can only imbalance one node at a time …
View Full Document
Unlocking...