Chirag PatelAVL Trees IntroductionHistoryAVL Tree ExampleSingle RotationSingle rotation cont..Single Rotation cont..Example of Single RotationDouble RotationDouble Rotation cont…Slide 11Slide 12Example of Double RotationTime ComplexityBefore the quizPracticePractice cont…Slide 18Chirag PatelChirag PatelAVL trees.AVL trees.18/4/200318/4/2003Enjoy.Enjoy.AVL Trees IntroductionAVL Trees Introduction4.4 AVL trees4.4 AVL treesHistoryHistorySingle RotationSingle RotationDouble RotationDouble RotationTime ComplexityTime ComplexityUsageUsageHistoryHistoryAn AVL (Adelson – Velskii and Landis) tree An AVL (Adelson – Velskii and Landis) tree is a binary search tree with a is a binary search tree with a balancebalance condition.condition.A balance condition must be maintained and A balance condition must be maintained and this ensures that the depth of the tree is this ensures that the depth of the tree is O(log N).O(log N).ALV tree is a binary tree however we take ALV tree is a binary tree however we take into consideration that ever node in the tree into consideration that ever node in the tree the height of the left and the right sub tree the height of the left and the right sub tree can can differ by at most 1differ by at most 1..AVL Tree ExampleAVL Tree ExampleSingle RotationSingle RotationThe book covers this The book covers this point very clearly. point very clearly. page 120page 120Single rotation cont..Single rotation cont..Perform Single RotationSingle Rotation cont..Single Rotation cont..Example of Single RotationExample of Single RotationDouble RotationDouble RotationFigure 4.34 in the book page123Figure 4.34 in the book page123Double Rotation cont…Double Rotation cont…Double Rotation cont…Double Rotation cont…Double RotationDouble Rotation cont…Double Rotation cont…Example of Double RotationExample of Double RotationTime ComplexityTime ComplexityI would recommend that you go to this site I would recommend that you go to this site to better understand the time complexity, as to better understand the time complexity, as well as a few more ideas on AVL trees.well as a few more ideas on AVL trees.http://www.ecf.utoronto.ca/apsc/courses/ecehttp://www.ecf.utoronto.ca/apsc/courses/ece242/2004spring/notes/bst2.pdf242/2004spring/notes/bst2.pdfBefore the quizBefore the quizInsert these numbers into a AVL tree.Insert these numbers into a AVL tree.Remember AVL tree is a binary search tree Remember AVL tree is a binary search tree but a tree that is balanced.but a tree that is balanced.Important this is the same when you insert a Important this is the same when you insert a node or when you delete a node.node or when you delete a node.Hence the difference of left sub tree and the Hence the difference of left sub tree and the right sub tree should be no more than h = 1.right sub tree should be no more than h = 1.Practice these inputs because we might have Practice these inputs because we might have a quiz today a quiz today ..PracticePracticeInput these numbers in an AVL tree.Input these numbers in an AVL tree.3,2,1,4,5,6,7,16,15,143,2,1,4,5,6,7,16,15,14Here is how you start,Here is how you start,Practice cont…Practice cont…Here is the final tree!!!Here is the final tree!!!THE ENDTHE