Question? Leave a message!




AVL Trees

AVL Trees
ECE 250 Algorithms and Data Structures AVL Trees Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.AVL trees 2 Outline Background Define height balancing Maintaining balance within a tree – AVL trees – Difference of heights – Maintaining balance after insertions and erases – Can we store AVL trees as arraysAVL trees 3 Background From previous lectures: – Binary search trees store linearly ordered data – Best case height:Q(ln(n)) – Worst case height: O(n) Requirement: – Define and maintain a balance to ensure Q(ln(n)) height AVL trees 4 Prototypical Examples These two examples demonstrate how we can correct for imbalances: starting with this tree, add 1:AVL trees 5 Prototypical Examples This is more like a linked list; however, we can fix this…AVL trees 6 Prototypical Examples Promote 2 to the root, demote 3 to be 2’s right child, and 1 remains the left child of 2AVL trees 7 Prototypical Examples The result is a perfect, though trivial treeAVL trees 8 Prototypical Examples Alternatively, given this tree, insert 2 AVL trees 9 Prototypical Examples Again, the product is a linked list; however, we can fix this, tooAVL trees 10 Prototypical Examples Promote 2 to the root, and assign 1 and 3 to be its childrenAVL trees 11 Prototypical Examples The result is, again, a perfect tree These examples may seem trivial, but they are the basis for the corrections in the next data structure we will see: AVL treesAVL trees 12 AVL Trees We will focus on the first strategy: AVL trees – Named after AdelsonVelskii and Landis Balance is defined by comparing the height of the two subtrees Recall: – An empty tree has height –1 – A tree with a single node has height 0AVL trees 13 AVL Trees A binary search tree is said to be AVL balanced if: – The difference in the heights between the left and right subtrees is at most 1, and – Both subtrees are themselves AVL treesAVL trees 14 AVL Trees AVL trees with 1, 2, 3, and 4 nodes:AVL trees 15 AVL Trees Here is a larger AVL tree (42 nodes):AVL trees 16 AVL Trees The root node is AVLbalanced: – Both subtrees are of height 4:AVL trees 17 AVL Trees All other nodes (e.g., AF and BL) are AVL balanced – The subtrees differ in height by at most oneAVL trees 18 Height of an AVL Tree By the definition of complete trees, any complete binary search tree is an AVL tree Thus an upper bound on the number of nodes in an AVL tree of h + 1 height h a perfect binary tree with 2 – 1 nodes – What is an lower boundAVL trees 19 Height of an AVL Tree Let F(h) be the fewest number of nodes in a tree of height h From a previous slide: F(0) = 1 F(1) = 2 F(2) = 4 Can we find F(h)AVL trees 20 Height of an AVL Tree The worstcase AVL tree of height h would have: – A worstcase AVL tree of height h – 1 on one side, – A worstcase AVL tree of height h – 2 on the other, and – The root node We get: F(h) = F(h – 1) + 1 + F(h – 2)AVL trees 21 Height of an AVL Tree This is a recurrence relation: 1 h  0   F(h)  2 h  1   F(h 1)  F(h  2) 1 h  1  The solution – Note that F(h) + 1 = (F(h – 1) + 1) + (F(h – 2) + 1) – Therefore, F(h) + 1 is a Fibonacci number: F(0) + 1 = 2 → F(0) = 1 F(1) + 1 = 3 → F(1) = 2 F(2) + 1 = 5 → F(2) = 4 F(3) + 1 = 8 → F(3) = 7 F(4) + 1 = 13 → F(4) = 12 F(5) + 1 = 21 → F(5) = 20 F(6) + 1 = 34 → F(6) = 33AVL trees 22 Height of an AVL Tree Alternatively, if it wasn’t so simple: rsolve( F(0) = 1, F(1) = 2, F(h) = 1 + F(h 1) + F(h 2), F(h) ); h h  2 2  h h  2 5 2 5   3 5 1 1 5 1 3 5 1 5 1 5 1 5   1   10 2 2 2 2 10 2 2  5 (1 5) 5 (1 5) asympt( , h );  (h I) h h  e (3 5 5) (1 5) 1 ( 5 3 5) 2  1 h 5 h 5 (1 5) 2 (1 5) (1 5) h  15 c   2 AVL trees 23 Height of an AVL Tree This is approximately h F(h) ≈ 1.8944 f – 1 where f ≈ 1.6180 is the golden ratio h – That is, F(h) = W(f ) Thus, we may find the maximum value of h for a given n: n1  log lognn11.32771.4404lg11.3277  ff  1.8944  – Recall that the height of a complete tree is h = ⌊lg(n)⌋ • The floor function makes the analysis interesting • With n = 3 nodes, it can be twice the height • For n ≥ 4096, 45 worse is an upper boundAVL trees 24 Height of an AVL Tree In this example, n = 88, the worst and bestcase scenarios differ in height by only 2AVL trees 25 Height of an AVL Tree 6 If n = 10 , the bounds on h are: 6 – The minimum height: log ( 10 ) – 1 ≈ 19 2 6 – the maximum height : log ( 10 / 1.8944 ) 28 fAVL trees 26 Maintaining Balance To maintain AVL balance, observe that: – Inserting a node can increase the height of a tree by at most 1 – Removing a node can decrease the height of a tree by at most 1AVL trees 27 Maintaining Balance Consider this AVL treeAVL trees 28 Maintaining Balance Consider inserting 15 into this tree – In this case, the heights of none of the trees changeAVL trees 29 Maintaining Balance The tree remains balancedAVL trees 30 Maintaining Balance Consider inserting 42 into this tree – In this case, the heights of none of the trees changeAVL trees 31 Maintaining Balance Consider inserting 42 into this tree – Now we see the heights of two subtrees have increased by one – The tree is still balancedAVL trees 32 Maintaining Balance To calculate changes in height, the member function must run in Q(1) time – Our implementation of height is Q(n): template typename Type int BinarynodeType::height() const return empty() 1 : 1 + std::max( left()height(), right()height() ); AVL trees 33 Maintaining Balance Introduce a member variable int treeheight; The member function is now: template typename Type int AVLnodeType::height() const return empty() 1 : treeheight; AVL trees 34 Maintaining Balance Only insert and erase may change the height – This is the only place we need to update the height – These algorithms are already recursiveAVL trees 35 Insert template typename Type bool AVLnodeType::insert( const Type obj, AVLnodeType ptrtothis ) if ( empty() ) ptrtothis = new AVLnode( obj ); return true; else if ( obj element ) if ( left()insert( obj, lefttree ) ) treeheight = max( height(), 1 + left()height() ); return true; else return false; else if ( obj element ) // ... else return false; AVL trees 36 Maintaining Balance If a tree is AVL balanced, for an insertion to cause an imbalance: – The heights of the subtrees must differ by 1 – The insertion must increase the height of the deeper subtree by 1AVL trees 37 Maintaining Balance Suppose we insert 23 into our initial treeAVL trees 38 Maintaining Balance The heights of each of the subtrees from here to the root are increased by oneAVL trees 39 Maintaining Balance However, only two of the nodes are unbalanced: 17 and 36AVL trees 40 Maintaining Balance However, only two of the nodes are unbalanced: 17 and 36 – We only have to fix the imbalance at the lowest nodeAVL trees 41 Maintaining Balance We can promote 23 to where 17 is, and make 17 the left child of 23AVL trees 42 Maintaining Balance Thus, that node is no longer unbalanced – Incidentally, neither is the root now balanced again, tooAVL trees 43 Maintaining Balance Consider adding 6:AVL trees 44 Maintaining Balance The height of each of the trees in the path back to the root are increased by oneAVL trees 45 Maintaining Balance The height of each of the trees in the path back to the root are increased by one – However, only the root node is now unbalancedAVL trees 46 Maintaining Balance To fix this, we will look at the general case…AVL trees 47 Maintaining Balance: Case 1 Consider the following setup – Each blue triangle represents a tree of height hAVL trees 48 Maintaining Balance: Case 1 Insert a into this tree: it falls into the left subtree B of b L – Assume B remains balanced L – Thus, the tree rooted at b is also balancedAVL trees 49 Maintaining Balance: Case 1 The tree rooted at node f is now unbalanced – We will correct the imbalance at this nodeAVL trees 50 Maintaining Balance: Case 1 Here are examples of when the insertion of 7 may cause this situation when h = –1, 0, and 1AVL trees 51 Maintaining Balance: Case 1 We will modify these three pointers – At this point, this references the unbalanced root node fAVL trees 52 Maintaining Balance: Case 1 Specifically, we will rotate these two nodes around the root: – Recall the first prototypical example – Promote node b to the root and demote node f to be the right child of b AVLnodeType b = left(), BR = bright(); AVL trees 53 Maintaining Balance: Case 1 This requires the address of node f to be assigned to the righttree member variable of node b AVLnodeType b = left(), BR = bright(); brighttree = this;AVL trees 54 Maintaining Balance: Case 1 Assign any former parent of node f to the address of node b Assign the address of the tree B to lefttree of node f R AVLnodeType b = left(), BR = bright(); brighttree = this; ptrtothis = b; lefttree = BR;AVL trees 55 Maintaining Balance: Case 1 The nodes b and f are now balanced and all remaining nodes of the subtrees are in their correct positionsAVL trees 56 Maintaining Balance: Case 1 Additionally, height of the tree rooted at b equals the original height of the tree rooted at f – Thus, this insertion will no longer affect the balance of any ancestors all the way back to the rootAVL trees 57 Maintaining Balance: Case 1 In our example case, the correction AVL trees 58 Maintaining Balance: Case 1 In our three sample cases with h = –1, 0, and 1, the node is now balanced and the same height as the tree before the insertionAVL trees 59 Maintaining Balance: Case 2 Alternatively, consider the insertion of c where b c f into our original treeAVL trees 60 Maintaining Balance: Case 2 Assume that the insertion of c increases the height of B R – Once again, f becomes unbalancedAVL trees 61 Maintaining Balance: Case 2 Here are examples of when the insertion of 14 may cause this situation when h = –1, 0, and 1AVL trees 62 Maintaining Balance: Case 2 Unfortunately, the previous correction does not fix the imbalance at the root of this subtree: the new root, b, remains unbalancedAVL trees 63 Maintaining Balance: Case 2 In our three sample cases with h = –1, 0, and 1, doing the same thing as before results in a tree that is still unbalanced… – The imbalance is just shifted to the other sideAVL trees 64 Maintaining Balance: Case 2 Unfortunately, this does not fix the imbalance at the root of this subtreeAVL trees 65 Maintaining Balance: Case 2 Relabel the tree by dividing the left subtree of f into a tree rooted at d with two subtrees of height h – 1AVL trees 66 Maintaining Balance: Case 2 Now an insertion causes an imbalance at f – The addition of either c or e will cause thisAVL trees 67 Maintaining Balance: Case 2 We will reassign the following pointers AVLnodeType b = left(), d = bright(), DL = dleft(), DR = dright();AVL trees 68 Maintaining Balance: Case 2 Specifically, we will order these three nodes as a perfect tree – Recall the second prototypical example AVLnodeType b = left(), d = bright(), DL = dleft(), DR = dright();AVL trees 69 Maintaining Balance: Case 2 To achieve this, b and f will be assigned as children of the new root d AVLnodeType b = left(), d = bright(), DL = dleft(), DR = dright(); dlefttree = b; drighttree = this;AVL trees 70 Maintaining Balance: Case 2 We also have to connect the two subtrees and original parent of f AVLnodeType b = left(), d = bright(), DL = dleft(), DR = dright(); dlefttree = b; drighttree = this; ptrtothis = d; brighttree = DL; lefttree = DR;AVL trees 71 Maintaining Balance: Case 2 Now the tree rooted at d is balancedAVL trees 72 Maintaining Balance: Case 2 Again, the height of the root did not changeAVL trees 73 Maintaining Balance: Case 2 In our three sample cases with h = –1, 0, and 1, the node is now balanced and the same height as the tree before the insertionAVL trees 74 Maintaining balance: Summary There are two symmetric cases to those we have examined: – Insertions into the rightright subtree – Insertions into either the rightleft subtree AVL trees 75 Insert (Implementation) template typename Type void AVLnodeType::insert( const Type obj, AVLnodeType ptrtothis ) if ( empty() ) ptrtothis = new AVLnodeType( obj ); return true; else if ( obj element ) if ( left() insert() ) if ( left()height() right()height() == 2 ) // determine if it is a leftleft or leftright insertion // perform the appropriate correction else treeheight = std::max( height(), left()height() ); return true; else return false; else if ( obj element ) // ...AVL trees 76 Insertion (Implementation) Comments: – Both balances are Q(1) – All insertions are still Q(ln(n)) – It is possible to tighten the previous code – Aside • if you want to explicitly rotate the nodes A and B, you must also pass a reference to the parent pointer as an argument: insert( Type obj, AVLnodeType parent )AVL trees 77 Insertion Consider this AVL treeAVL trees 78 Insertion Insert 73AVL trees 79 Insertion The node 81 is unbalanced – A leftleft imbalanceAVL trees 80 Insertion The node 81 is unbalanced – A leftleft imbalanceAVL trees 81 Insertion The node 81 is unbalanced – A leftleft imbalance – Promote the intermediate node to the imbalanced nodeAVL trees 82 Insertion The node 81 is unbalanced – A leftleft imbalance – Promote the intermediate node to the imbalanced node – 75 is that nodeAVL trees 83 Insertion The node 81 is unbalanced – A leftleft imbalance – Promote the intermediate node to the imbalanced node – 75 is that nodeAVL trees 84 Insertion The tree is AVL balancedAVL trees 85 Insertion Insert 77AVL trees 86 Insertion The node 87 is unbalanced – A leftright imbalanceAVL trees 87 Insertion The node 87 is unbalanced – A leftright imbalanceAVL trees 88 Insertion The node 87 is unbalanced – A leftright imbalance – Promote the intermediate node to the imbalanced nodeAVL trees 89 Insertion The node 87 is unbalanced – A leftright imbalance – Promote the intermediate node to the imbalanced node – 81 is that valueAVL trees 90 Insertion The node 87 is unbalanced – A leftright imbalance – Promote the intermediate node to the imbalanced node – 81 is that valueAVL trees 91 Insertion The tree is balancedAVL trees 92 Insertion Insert 76AVL trees 93 Insertion The node 78 is unbalanced – A leftleft imbalanceAVL trees 94 Insertion The node 78 is unbalanced – Promote 77AVL trees 95 Insertion Again, balancedAVL trees 96 Insertion Insert 80AVL trees 97 Insertion The node 69 is unbalanced – A rightleft imbalance – Promote the intermediate node to the imbalanced nodeAVL trees 98 Insertion The node 69 is unbalanced – A leftright imbalance – Promote the intermediate node to the imbalanced node – 75 is that valueAVL trees 99 Insertion Again, balancedAVL trees 100 Insertion Insert 74AVL trees 101 Insertion The node 72 is unbalanced – A rightright imbalance – Promote the intermediate node to the imbalanced node – 75 is that valueAVL trees 102 Insertion The node 72 is unbalanced – A rightright imbalance – Promote the intermediate node to the imbalanced nodeAVL trees 103 Insertion Again, balancedAVL trees 104 Insertion Insert 64AVL trees 105 Insertion This causes no imbalancesAVL trees 106 Insertion Insert 55AVL trees 107 Insertion The node 69 is imbalanced – A leftleft imbalance – Promote the intermediate node to the imbalanced nodeAVL trees 108 Insertion The node 69 is imbalanced – A leftleft imbalance – Promote the intermediate node to the imbalanced node – 63 is that valueAVL trees 109 Insertion The tree is now balancedAVL trees 110 Insertion Insert 70AVL trees 111 Insertion The root node is now imbalanced – A rightleft imbalance – Promote the intermediate node to the root – 75 is that valueAVL trees 112 Insertion The root node is imbalanced – A rightleft imbalance – Promote the intermediate node to the root – 63 is that nodeAVL trees 113 Insertion The result is AVL balancedAVL trees 114 Erase Removing a node from an AVL tree may cause more than one AVL imbalance – Like insert, erase must check after it has been successfully called on a child to see if it caused an imbalance – Unfortunately, it may cause O(h) imbalances that must be corrected • Insertions will only cause one imbalance that must be fixedAVL trees 115 Erase Consider the following AVL treeAVL trees 116 Erase Suppose we erase the front node: 1AVL trees 117 Erase While its previous parent, 2, is not unbalanced, its grandparent 3 is – The imbalance is in the rightright subtreeAVL trees 118 Erase We can correct this with a simple balanceAVL trees 119 Erase The node of that subtree, 5, is now balancedAVL trees 120 Erase Recursing to the root, however, 8 is also unbalanced – This is a rightleft imbalanceAVL trees 121 Erase Promoting 11 to the root corrects the imbalance AVL trees 122 Erase At this point, the node 11 is balancedAVL trees 123 Erase Still, the root node is unbalanced – This is a rightright imbalanceAVL trees 124 Erase Again, a simple balance fixes the imbalanceAVL trees 125 Erase The resulting tree is now AVL balanced – Note, few erases will require one balance, even fewer will require more than oneAVL trees 126 AVL Trees as Arrays We previously saw that: – Complete tree can be stored using an array using Q(n) memory n – An arbitrary tree of n nodes requires O(2 ) memory Is it possible to store an AVL tree as an array and not require exponentially more memoryAVL trees 127 AVL Trees as Arrays Recall that in the worst case, an AVL tree of n nodes has a height at most log (n) – 1.3277 f Such a tree requires an array of size logf(n) – 1.3277 + 1 2 – 1 We can rewrite this as –0.3277 logf(2) 1.44 2 n ≈ 0.7968 n 1.44 Thus, we would require O(n ) memoryAVL trees 128 AVL Trees as Arrays 1.44 While the polynomial behaviour of n is not as bad as exponential behaviour, it is still reasonably suboptimal when compared to the linear growth associated with link allocated trees 1.44 Here we see n and n on 0, 1000AVL trees 129 Summary In this topic we have covered: – AVL balance is defined by ensuring the difference in heights is 0 or 1 – Insertions and erases are like binary search trees – Each insertion requires at least one correction to maintain AVL balance – Erases may require O(h) corrections – These corrections require Q(1) time – Depth is Q( ln(n) ) ∴ all O(h) operations are O( ln(n) )AVL trees 130 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath dwharderalumni.uwaterloo.ca
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017