Lecture 12Types of TreesComplete Binary TreeAVL TreesHeight of a TreeAVL PropertyAVL Tree: ExampleNon-AVL TreeTransforming into AVL TreeTransformationsExample: AVL Tree for AirportsBinary Search Tree for Airport NamesAVL Balancing : Four RotationsAn AVL Tree for Airport NamesAn AVL Tree for Airport Names (contd.)An AVL Tree …An AVL Tree…Search OperationKnown Performance Results of AVL treesPowerPoint PresentationSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33FACTS ABOUT NODE DELETION AND INSERTION:Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41FACTS ABOUT NODE DELETION AND INSERTION: (cont.)Slide 43Slide 441Lecture 12Lecture 12AVL TreesAVL Trees2treesstaticdynamicgame trees search treespriority queues and heapsgraphsbinary searchtreesAVL trees2-3 trees triesHuffman coding treeTypes of TreesTypes of Trees3Complete Binary TreeComplete Binary TreeIs a tree with height h where:Is a tree with height h where:Every node is full upto level h-2,Every node is full upto level h-2,Level h-1 is completely filled.Level h-1 is completely filled.Level h is filled from left to right.Level h is filled from left to right.Yields to array representation. How to Yields to array representation. How to compute indices of parent and child?compute indices of parent and child?How many internal nodes and leafs?How many internal nodes and leafs?4AVL TreesAVL TreesBalanced binary search tree offer a O(log n) Balanced binary search tree offer a O(log n) insert and delete.insert and delete.But balancing itself costs O(n) in the average But balancing itself costs O(n) in the average case.case.In this case, even though delete will be O(log In this case, even though delete will be O(log n), insert will be O(n).n), insert will be O(n).Is there any way to have a O(log n) insert Is there any way to have a O(log n) insert too?too?Yes, by almost but not fully balancing the tree Yes, by almost but not fully balancing the tree : AVL (Adelson Velskii and Landis) balancing: AVL (Adelson Velskii and Landis) balancing5Height of a TreeHeight of a TreeDefinition is same as level. Height of a tree is Definition is same as level. Height of a tree is the length of the longest path from root to the length of the longest path from root to some leaf node. some leaf node. Height of a empty tree is -1.Height of a empty tree is -1.Height of a single node tree is 0.Height of a single node tree is 0.Recursive definition: Recursive definition: height(t) = 0 if number of nodes = 1height(t) = 0 if number of nodes = 1 = -1 if T is empty= -1 if T is empty = 1+ max(height(LT), height(RT)) = 1+ max(height(LT), height(RT)) otherwiseotherwise6AVL PropertyAVL PropertyIf N is a node in a binary tree, node If N is a node in a binary tree, node N has AVL property if the heights N has AVL property if the heights of the left sub-tree and right sub-of the left sub-tree and right sub-tree are equal or if they differ by 1.tree are equal or if they differ by 1.Lets look at some examples.Lets look at some examples.7AVL Tree: ExampleAVL Tree: Example8Non-AVL TreeNon-AVL Tree9Transforming into AVL TreeTransforming into AVL TreeFour different transformations are Four different transformations are available called : rotationsavailable called : rotationsRotations: single right, single left, Rotations: single right, single left, double right, double leftdouble right, double leftThere is a close relationship There is a close relationship between rotations and associative between rotations and associative law of algebra.law of algebra.10TransformationsTransformationsSingle right : Single right : ((T1 + T2) + T3) = (T1 + (T2 + T3)((T1 + T2) + T3) = (T1 + (T2 + T3)Single left : Single left : (T1 + (T2 + T3)) = ((T1 + T2) + T3)(T1 + (T2 + T3)) = ((T1 + T2) + T3)Double right : Double right : ((T1 + (T2 + T3)) + T4) = ((T1+T2) + ((T1 + (T2 + T3)) + T4) = ((T1+T2) + (T3+T4))(T3+T4))Double left :Double left :(T1 ((T2+T3) +T4)) = ((T1+T2) + (T3+T4))(T1 ((T2+T3) +T4)) = ((T1+T2) + (T3+T4))11Example: AVL Tree for Example: AVL Tree for AirportsAirportsConsider inserting Consider inserting sequentiallysequentially: : ORY, JFK, BRU, DUS, ZRX, MEX, ORY, JFK, BRU, DUS, ZRX, MEX, ORD, NRT, ARN, GLA, GCMORD, NRT, ARN, GLA, GCMBuild a binary-search treeBuild a binary-search treeBuild a AVL tree.Build a AVL tree.12 Binary Search Tree for Binary Search Tree for Airport NamesAirport NamesORYZRHJFKBRUMEXARNDUSGLAORDNRTGCM13AVL Balancing : Four AVL Balancing : Four RotationsRotationsSingle rightX3X2X1X2X1 X3X1X2X3Single leftX2X3X1X3X2X1Double rightX3X2 X1X3X1 X2X2X3X1Double left14An AVL Tree for Airport An AVL Tree for Airport NamesNamesORYJFKBRUNot AVL balancedSingle rightJFKBRUORYAVL BalancedAfter insertion of ORY, JFK and BRU :15An AVL Tree for Airport An AVL Tree for Airport Names (contd.)Names (contd.)After insertion of DUS, ZRH, MEX and ORDJFKBRUORYDUS MEXZRHORDStill AVL BalancedAfter insertion of NRT?JFKBRUORYDUS MEXZRHORDNRT16An AVL Tree … An AVL Tree … JFKBRUORYDUS MEXZRHORDNRTNot AVL BalanacedDouble LeftJFKBRUORYDUS NRTZRHORDMEXNow add ARN and GLA; noneed for rotations; Then add GCM17An AVL Tree…An AVL Tree…JFKBRUDUSORYNRTZRHORDMEXARNGLAGCMNOT AVL BALANCEDJFKBRUGCMORYNRTZRHORDMEXARNGLADouble leftDUS18Search OperationSearch OperationFor successful search, average number of For successful search, average number of comparisons: comparisons: sum of all (path length+1) / number of sum of all (path length+1) / number of nodesnodesFor the binary search tree (of airports) it is:For the binary search tree (of airports) it is:39/11 = 3.5539/11 = 3.55For the AVL tree (of airports) it is : For the AVL tree (of airports) it is : 33/11 = 3.033/11 = 3.019Known Performance Known Performance Results of AVL treesResults of AVL treesAVL tree is a sub optimal solution.AVL tree is a sub optimal solution.How to evaluate its performance?How to evaluate its performance?Bounds (upper bound and lower Bounds (upper bound and lower bound) for number of comparisons:bound) for number of comparisons:C > log(n+1) + 1C > log(n+1) + 1C < 1.44 log(n+2) - 0.328C < 1.44 log(n+2) - 0.328AVL trees are no more than 44% AVL trees are no more than 44% worse than optimal trees.worse than optimal trees.20212223The definition of an AVL tree indicates that the minimum number of nodes in a tree is determined by the recurrence