AVL Trees 1 AVL Trees An AVL tree is a binary search tree with a balance condition AVL is named for its inventors Adel son Vel skii and Landis AVL tree approximates the ideal tree completely balanced tree AVL Tree maintains a height close to the minimum Definition An AVL tree is a binary search tree such that for any node in the tree the height of the left and right subtrees can differ by at most 1 2 Figure 19 21 Two binary search trees a an AVL tree b not an AVL tree unbalanced nodes are darkened 3 Figure 19 22 Minimum tree of height H 4 Properties The depth of a typical node in an AVL tree is very close to the optimal log N Consequently all searching operations in an AVL tree have logarithmic worst case bounds An update insert or remove in an AVL tree could destroy the balance It must then be rebalanced before the operation can be considered complete After an insertion only nodes that are on the path from the insertion point to the root can have their balances altered 5 Rebalancing Suppose the node to be rebalanced is X There are 4 cases that we might have to fix two are the mirror images of the other two 1 2 3 4 An insertion in the left subtree of the left child of X An insertion in the right subtree of the left child of X An insertion in the left subtree of the right child of X or An insertion in the right subtree of the right child of X Balance is restored by tree rotations 6 Balancing Operations Rotations Case 1 and case 4 are symmetric and requires the same operation for balance Cases 1 4 are handled by single rotation Case 2 and case 3 are symmetric and requires the same operation for balance Cases 2 3 are handled by double rotation 7 Single Rotation A single rotation switches the roles of the parent and child while maintaining the search order Single rotation handles the outside cases i e 1 and 4 We rotate between a node and its child Child becomes parent Parent becomes right child in case 1 left child in case 4 The result is a binary search tree that satisfies the AVL property 8 Figure 19 23 Single rotation to fix case 1 Rotate right 9 Figure 19 26 Symmetric single rotation to fix case 4 Rotate left 10 Figure 19 25 Single rotation fixes an AVL tree after insertion of 1 11 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order Answer 1 12 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order Answer 1 2 13 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order Answer 1 2 14 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 2 1 3 15 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order Answer 2 1 3 16 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 2 1 3 17 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 2 1 3 18 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 2 1 3 6 19 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 2 1 3 6 20 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 2 1 3 6 7 21 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order Answer 4 2 1 6 3 5 7 22 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 6 3 5 7 4 5 23 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 6 3 5 7 4 5 4 8 24 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 6 3 4 8 4 5 7 5 25 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 6 3 4 8 4 5 7 5 5 5 26 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 5 3 4 8 4 5 6 5 5 7 27 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 5 3 4 8 4 5 6 5 5 7 5 7 28 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 5 6 4 7 4 8 5 5 2 4 5 1 5 7 3 29 Example Start with an empty AVL tree and insert the items 3 2 1 and then 4 through 7 in sequential order 4 2 1 5 3 4 8 4 5 6 5 5 7 4 7 30 Analysis One rotation suffices to fix cases 1 and 4 Single rotation preserves the original height The new height of the entire subtree is exactly the same as the height of the original subtree before the insertion Therefore it is enough to do rotation only at the first node where imbalance exists on the path from inserted node to root Thus the rotation takes O 1 time Hence insertion is O logN 31 Double Rotation Single rotation does not fix the inside cases 2 and 3 These cases require a double rotation involving three nodes and four subtrees 32 Figure 19 28 Single rotation does not fix case 2 33 Left right double rotation to fix case 2 Lift this up first rotate left between k1 k2 then rotate right betwen k3 k2 34 Left Right Double Rotation A left right double rotation is equivalent to a sequence of two single rotations 1st rotation on the original tree a left rotation between X s left child and grandchild 2nd rotation on the new tree a right rotation between X and its new left child 35 Figure 19 30 Double rotation …
View Full Document
Unlocking...