PowerPoint PresentationOutlineIntroductionDefinitionsHeight-Balanced TreesPicking Out AVL TreesPicking Out AVL Trees (Cont’d)Why AVL Trees?Why AVL Trees? (Cont’d)Added ComplexityViolationsThe Balance FactorThe Balance Factor (Cont’d)Slide 14What is a rotation?Single Rotations (Cont’d)Single RotationsSlide 18Slide 19Double RotationsDouble Rotations (Cont’d)Slide 22Slide 23Slide 24Slide 25The EndPresented by:Presented by:Chien-Pin HsuChien-Pin HsuCS146CS146Prof. Sin-Min LeeProf. Sin-Min LeeOutlineOutlineIntroductionIntroductionDefinitionsDefinitionsHeight-Balanced TreesHeight-Balanced TreesPicking Out AVL TreesPicking Out AVL TreesWhy AVL Trees?Why AVL Trees?Added ComplexityAdded ComplexityViolationsViolationsThe Balance FactorThe Balance FactorWhat is a rotation?What is a rotation?Single RotationsSingle RotationsDouble RotationsDouble RotationsIntroductionIntroductionAVL tree is the first balanced binary AVL tree is the first balanced binary search tree (name after its discovers, search tree (name after its discovers, Adelson-Velskii and Landis).Adelson-Velskii and Landis).The AVL tree is a balanced search tree The AVL tree is a balanced search tree that has an additional balance condition.that has an additional balance condition. The balance condition must be easy to The balance condition must be easy to maintain and ensures that the depth of the maintain and ensures that the depth of the tree is O(logN)tree is O(logN)DefinitionsDefinitionsAn AVL tree is a binary search tree that is An AVL tree is a binary search tree that is height balanced meaning that it has these height balanced meaning that it has these two properties..two properties.. 1. The sub-tree of every node must differ 1. The sub-tree of every node must differ in height by at most one.in height by at most one. 2. Every sub-tree is an AVL tree2. Every sub-tree is an AVL treeHeight-Balanced TreesHeight-Balanced TreesHeight of a tree is the length of the longest path from a Height of a tree is the length of the longest path from a root to a leaf.root to a leaf.A binary search tree T is a height-balanced k-tree or A binary search tree T is a height-balanced k-tree or HB[k]-tree, if each node in the tree has the HB[k] HB[k]-tree, if each node in the tree has the HB[k] property.property.A node has the HB[k] property if the height of the left and A node has the HB[k] property if the height of the left and right sub-trees of the node differ in height by at most k.right sub-trees of the node differ in height by at most k.A HB[1] tree is called an AVL tree.A HB[1] tree is called an AVL tree.Picking Out AVL TreesPicking Out AVL TreesNotation: NODE = Left-Ht, Right-HtNotation: NODE = Left-Ht, Right-HtYes!5 = 2, 14 = 1, 03 = 0, 07 = 0, 0 No!10 = 3, 1Picking Out AVL Trees (Cont’d)Picking Out AVL Trees (Cont’d)Notation: NODE = Left-Ht, Right-HtNotation: NODE = Left-Ht, Right-HtNo!8 = 4, 24 = 3, 13 = 2, 0Why AVL Trees?Why AVL Trees?The worst case for Binary Search Trees:The worst case for Binary Search Trees: Insert: O(n).Insert: O(n). Delete: O(n).Delete: O(n). Search :O(n).Search :O(n). The worst case for AVL trees:The worst case for AVL trees: Insert: O(log n).Insert: O(log n). Delete: O(log n).Delete: O(log n). Search:O(log n).Search:O(log n). Recall when comparing the time complexityRecall when comparing the time complexity O(log n) < O(n)O(log n) < O(n)Why AVL Trees? (Cont’d)Why AVL Trees? (Cont’d)AVL trees allow for logarithmic Inserts and AVL trees allow for logarithmic Inserts and Deletes, and they allow for easy Deletes, and they allow for easy traversals, such as the “In-order” traversal traversals, such as the “In-order” traversal if we want to sort our elements.if we want to sort our elements.Added ComplexityAdded ComplexityAlthough we have made the Insertion, Although we have made the Insertion, Deletion & Searching better, an additional Deletion & Searching better, an additional amount of complexity does arise during amount of complexity does arise during the Insertions and the Deletions.the Insertions and the Deletions.After Inserting and Deleting for an AVL After Inserting and Deleting for an AVL tree, the new tree might violate the two tree, the new tree might violate the two properties of the AVL tree.properties of the AVL tree.ViolationsViolationsNo!No!5 = 2, 05 = 2, 0No!5 = 3,14 = 2,0Notation: NODE = Left-Ht, Right-HtNotation: NODE = Left-Ht, Right-HtThe Balance FactorThe Balance FactorIn order to detect when a “violation” of a In order to detect when a “violation” of a AVL tree occurs, we need to have each AVL tree occurs, we need to have each node keep track of the difference in height node keep track of the difference in height between its right and left sub-trees.between its right and left sub-trees.Notation for the balance factor:Notation for the balance factor: bf (node) = Left-Ht – Right- Htbf (node) = Left-Ht – Right- HtTo be a valid AVL Tree, -1 <= bf(x) <= 1 for To be a valid AVL Tree, -1 <= bf(x) <= 1 for all nodes.all nodes.The Balance Factor (Cont’d)The Balance Factor (Cont’d)Notation for the balance factor:Notation for the balance factor: bf (node) = Left-Ht – Right- Htbf (node) = Left-Ht – Right- Htbf(8) = 3 – 3 = 0bf(4) = 2 – 1 = 1bf(10) = 1 – 2 = -1bf(3) = 1 – 0 = 1bf(5) = 0 – 0 = 0bf(9) = 0 – 0 = 0bf(11) = 0 – 1 = -1bf(1) = 0 – 0 = 0bf(12) = 0 – 0 = 0Valid Tree!!The Balance Factor (Cont’d)The Balance Factor (Cont’d)Notation for the balance factor:Notation for the balance factor: bf (node) = Left-Ht – Right- Htbf (node) = Left-Ht – Right- Htbf(8) = 2 – 0 = 2bf(4) = 1 – 0 = 1Bf(3) = 0 – 0 = 0Invalid Tree!!What is a rotation?What is a rotation?A rotation is an operation to rearrange A rotation is an operation to rearrange nodes to maintain balance of an AVL tree nodes to maintain balance of an AVL tree after adding and removing a nodeafter adding and removing a nodeThere are two case to perform the rotationThere are two case to perform the rotation 1) Single Rotation1) Single Rotation 2) Double Rotation2) Double RotationWhen to perform rotations?When to perform rotations? we need to perform a rotation anytime a we need to perform a rotation anytime a node’s balance factor is 2 or -2node’s balance factor is 2 or -2Single Rotations (Cont’d)Single Rotations (Cont’d)Algorithm for right rotationAlgorithm for right rotation Algorithm rotateRight(nodeN) nodeC = left child of nodeN Set nodeN’s