tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 11.2 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of AVL trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | AVL Trees 3/20/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 AVL Trees v 6 8 3 4 © 2014 Goodrich, Tamassia, Goldwasser z AVL Trees 1 AVL Tree Definition ! AVL trees are 4 balanced ! An AVL Tree is a 44 2 binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1 © 2014 Goodrich, Tamassia, Goldwasser 3 17 78 1 2 32 1 88 50 1 48 62 1 An example of an AVL tree where the heights are shown next to the nodes AVL Trees 2 1 AVL Trees 3/20/14 n(2) 3 4 Height of an AVL Tree n(1) Fact: The height of an AVL tree storing n keys is O(log n). Proof (by induction): Let us bound n(h): the minimum number of internal nodes of an AVL tree of height h. ! We easily see that n(1) = 1 and n(2) = 2 ! For n > 2, an AVL tree of height h contains the root node, one AVL subtree of height n-1 and another of height n-2. ! That is, n(h) = 1 + n(h-1) + n(h-2) ! Knowing n(h-1) > n(h-2), we get n(h) > 2n(h-2). So n(h) > 2n(h-2), n(h) > 4n(h-4), n(h) > 8n(n-6), (by induction), n(h) > 2in(h-2i) ! Solving the base case we get: n(h) > 2 h/2-1 ! Taking logarithms: h < 2log n(h) +2 ! Thus the height of an AVL tree is O(log n) © 2014 Goodrich, Tamassia, Goldwasser AVL Trees 3 Insertion ! Insertion is as in a binary search tree ! Always done by expanding an external node. ! Example: 44 44 17 78 17 78 c=z a=y 32 50 48 88 62 32 50 88 48 w before insertion 62 b=x 54 after insertion © 2014 Goodrich, Tamassia, Goldwasser AVL Trees 4 2 AVL Trees 3/20/14 Trinode Restructuring Let (a,b,c) be the inorder listing of x, y, z Perform the rotations needed to make b the topmost node of the three ! ! Single rotation around b a=z Double rotation around c and a a=z c=y b=y T0 T0 b=x c=x T1 T3 b=y T2 T3 a=z T2 T1 T0 © 2014 Goodrich, Tamassia, .