AVL TreesReadingsBinary Search Tree - Best TimeBinary Search Tree - Worst TimeBalanced and unbalanced BSTApproaches to balancing treesBalancing Binary Search TreesPerfect BalanceAVL - Good but not Perfect BalanceHeight of an AVL TreeSlide 11Node HeightsNode Heights after Insert 7Insert and Rotation in AVL TreesSingle Rotation in an AVL TreePowerPoint PresentationSlide 17Slide 18Slide 19Slide 20Slide 21Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30ImplementationSingle RotationDouble RotationInsertion in AVL TreesInsert in BSTInsert in AVL treesExample of Insertions in an AVL TreeSlide 38Single rotation (outside case)Double rotation (inside case)AVL Tree DeletionSlide 42Double Rotation SolutionAVL TreesCSE 373Data StructuresLecture 812/26/03 AVL Trees - Lecture 8 2Readings•Reading ›Section 4.4,12/26/03 AVL Trees - Lecture 8 3Binary Search Tree - Best Time•All BST operations are O(d), where d is tree depth•minimum d is for a binary tree with N nodes›What is the best case tree? ›What is the worst case tree?•So, best case running time of BST operations is O(log N) Nlogd212/26/03 AVL Trees - Lecture 8 4Binary Search Tree - Worst Time•Worst case running time is O(N) ›What happens when you Insert elements in ascending order?•Insert: 2, 4, 6, 8, 10, 12 into an empty BST›Problem: Lack of “balance”: •compare depths of left and right subtree›Unbalanced degenerate tree12/26/03 AVL Trees - Lecture 8 5Balanced and unbalanced BST42 51 3152437642 65 71 3Is this “balanced”?12/26/03 AVL Trees - Lecture 8 6Approaches to balancing trees•Don't balance›May end up with some nodes very deep•Strict balance›The tree must always be balanced perfectly•Pretty good balance›Only allow a little out of balance•Adjust on access›Self-adjusting12/26/03 AVL Trees - Lecture 8 7Balancing Binary Search Trees•Many algorithms exist for keeping binary search trees balanced›Adelson-Velskii and Landis (AVL) trees (height-balanced trees) ›Splay trees and other self-adjusting trees›B-trees and other multiway search trees12/26/03 AVL Trees - Lecture 8 8Perfect Balance•Want a complete tree after every operation›tree is full except possibly in the lower right•This is expensive›For example, insert 2 in the tree on the left and then rebuild as a complete treeInsert 2 &complete tree64 981 552 86 91 412/26/03 AVL Trees - Lecture 8 9AVL - Good but not Perfect Balance•AVL trees are height-balanced binary search trees•Balance factor of a node›height(left subtree) - height(right subtree)•An AVL tree has balance factor calculated at every node›For every node, heights of left and right subtree can differ by no more than 1›Store current heights in each node12/26/03 AVL Trees - Lecture 8 10Height of an AVL Tree•N(h) = minimum number of nodes in an AVL tree of height h.•Basis›N(0) = 1, N(1) = 2•Induction›N(h) = N(h-1) + N(h-2) + 1•Solution (recall Fibonacci analysis)›N(h) > h (  1.62)h-1h-2h12/26/03 AVL Trees - Lecture 8 11Height of an AVL Tree•N(h) > h (  1.62)•Suppose we have n nodes in an AVL tree of height h.›n > N(h) (because N(h) was the minimum)›n > h hence log n > h (relatively well balanced tree!!)›h < 1.44 log2n (i.e., Find takes O(logn))12/26/03 AVL Trees - Lecture 8 12Node Heights1002064 981 51height of node = hbalance factor = hleft-hrightempty height = -100height=2 BF=1-0=1064 91 51Tree A (AVL) Tree B (AVL)12/26/03 AVL Trees - Lecture 8 13Node Heights after Insert 72103064 981 51height of node = hbalance factor = hleft-hrightempty height = -1102064 91 510707balance factor 1-(-1) = 2-1Tree A (AVL) Tree B (not AVL)12/26/03 AVL Trees - Lecture 8 14Insert and Rotation in AVL Trees•Insert operation may cause balance factor to become 2 or –2 for some node ›only nodes on the path from insertion point to root node have possibly changed in height›So after the Insert, go back up to the root node by node, updating heights›If a new balance factor (the difference hleft-hright) is 2 or –2, adjust tree by rotation around the node12/26/03 AVL Trees - Lecture 8 15Single Rotation in an AVL Tree2102064 981 51070102064981 510712/26/03 AVL Trees - Lecture 8 16Let the node that needs rebalancing be .There are 4 cases: Outside Cases (require single rotation) : 1. Insertion into left subtree of left child of . 2. Insertion into right subtree of right child of . Inside Cases (require double rotation) : 3. Insertion into right subtree of left child of . 4. Insertion into left subtree of right child of .The rebalancing is performed through four separate rotation algorithms.Insertions in AVL Trees12/26/03 AVL Trees - Lecture 8 17jkX YZConsider a validAVL subtreeAVL Insertion: Outside Case hhh12/26/03 AVL Trees - Lecture 8 18jkXYZInserting into Xdestroys the AVL property at node jAVL Insertion: Outside Case hh+1 h12/26/03 AVL Trees - Lecture 8 19jkXYZDo a “right rotation”AVL Insertion: Outside Case hh+1 h12/26/03 AVL Trees - Lecture 8 20jkXYZDo a “right rotation”Single right rotationhh+1 h12/26/03 AVL Trees - Lecture 8 21jkXYZ“Right rotation” done!(“Left rotation” is mirror symmetric)Outside Case CompletedAVL property has been restored!hh+1h12/26/03 AVL Trees - Lecture 8 22jkX YZAVL Insertion: Inside Case Consider a validAVL subtreehhh12/26/03 AVL Trees - Lecture 8 23Inserting into Y destroys theAVL propertyat node j jkXYZAVL Insertion: Inside CaseDoes “right rotation”restore balance?hh+1h12/26/03 AVL Trees - Lecture 8 24jkXYZ“Right rotation”does not restorebalance… now k isout of balanceAVL Insertion: Inside Casehh+1h12/26/03 AVL Trees - Lecture 8 25Consider the structureof subtree Y…jkXYZAVL Insertion: Inside Casehh+1h12/26/03 AVL Trees - Lecture 8 26jkXVZWiY = node i andsubtrees V and WAVL Insertion: Inside Casehh+1hh or h-112/26/03 AVL Trees - Lecture 8 27jkXVZWiAVL Insertion: Inside CaseWe will do a left-right “double rotation” . . .12/26/03 AVL Trees - Lecture 8 28jkXVZWiDouble rotation : first rotationleft rotation complete12/26/03 AVL Trees - Lecture 8 29jkXVZWiDouble rotation : second rotationNow do a right rotation12/26/03 AVL Trees - Lecture 8 30jkXVZWiDouble rotation : second rotationright rotation completeBalance has been restoredhhh or h-112/26/03 AVL Trees - Lecture 8 31Implementationbalance (1,0,-1)keyrightleftNo need to keep the height; just the difference in height, i.e. the balance factor;