AVLTrees/Slide6AVL TreeAn AVL (Adelson-Velskii and Landis 1962)tree is a binary search tree in whichfor every node in the tree, the height of the left andright subtrees differ by at most 1AVLtreeAVLpropertyviolatedhere
AVL Trees / Slide 6 AVL Tree An AVL (Adelson-Velskii and Landis 1962) tree is a binary search tree in which for every node in the tree, the height of the left and right subtrees differ by at most 1. AVL property violated here AVL tree
AVLTrees/Slide7AVL Tree withMinimum Number of NodesN3=Ni+N2+1=7N。=1Ni=N2
AVL Trees / Slide 7 AVL Tree with Minimum Number of Nodes N0 = 1 N1 = 2 N2 =4 N3 = N1+N2+1=7
AVLTrees/Slide8SmallestAVLtreeofheight7SmallestAVLtreeofheight8SmallestAVLtree of height9
AVL Trees / Slide 8 Smallest AVL tree of height 9 Smallest AVL tree of height 7 Smallest AVL tree of height 8
AVLTrees/Slide9Height of AVL TreeDenote N,the minimum number of nodes in an AVLtree of height hNo=0, Ni =2 (base)N,= Nn-1 + Nn-2 +i (recursive relation)N > N= Nn-1 + Nn-2 +1>2 Nn-2 >4Nn-4>..>2i N-2iIf h is even, let i=h/2-1. The equation becomes N>2h/2-1N2=N>2h/2-1x4=h=0(1ogN)If h is odd, let i=(h-1)/2. The equationbecomes N>2(h-1)/2N1=N>2(h-1)/2x2=h=O(1ogN)Thus,many operations (i.e.searching) on an AVL treewill take O(log N) time
AVL Trees / Slide 9 Height of AVL Tree Denote Nh the minimum number of nodes in an AVL tree of height h N0=0, N1 =2 (base) Nh= Nh-1 + Nh-2 +1 (recursive relation) N > Nh= Nh-1 + Nh-2 +1 >2 Nh-2 >4 Nh-4 >.>2i Nh-2i If h is even, let i=h/2–1. The equation becomes N>2h/2-1N2 N>2h/2-1x4 h=O(logN) If h is odd, let i=(h-1)/2. The equation becomes N>2(h-1)/2N1 N>2(h-1)/2x2 h=O(logN) Thus, many operations (i.e. searching) on an AVL tree will take O(log N) time