DOC PREVIEW
UCF COP 3502 - AVL Trees

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

AVL TreesIn order to have a worst case running time for insert and deleteoperations to be O(log n), we must make it impossible for thereto be a very long path in the binary search tree. The firstbalanced binary tree is the AVL tree, named after it'sinventors, Adelson-Velskii and Landis. A binary search tree isan AVL tree iff each node in the tree satisfies the followingproperty:The height of the left subtree can differ from the height of theright subtree by at most 1.Based on this property, we can show that the height of an AVLtree is logarithmic with respect to the number of nodes storedin the tree.In particular, for an AVL tree of height H, we find that it mustcontain at least FH+3 -1 nodes. (Fi is the ith Fibonacci number.)To prove this, notice that the number of nodes in an AVL tree isthe 1 plus the number of notes in the left subtree plus thenumber of nodes in the right subtree. If we let SH represent theminimum number of nodes in an AVL tree with height H, weget the following recurrence relation:SH = SH-1 + SH-2 + 1We also know that S0=1 and S1=2. Now we can prove the assertion above through induction.For those of you who haven't seen induction yet, I won't "test"on it in this class. I'll try to explain the major steps of inductionas best as I can, very briefly. Induction is used to prove thatsome statement or formula is true for all positive integers.Sometimes, it is difficult to prove a formula for all positiveintegers outright though.In these cases, it may be easier to prove that IF the formula istrue for an integer, say, 10 (we can call this k), then it MUSTBE true for the next integer 11 (this would be k+1).Finally, if we can prove that, AND we can show that theformula is true when you plug in 1 into it, it follows that theformula is true for all positive integers. Here's a simple example you can hopefully relate to (Iapologize to women who have small wardrobes!!!):Assumptions: A female's wardrobe increases by 15% a year. Amale's wardrobe increases by 10% a year. At the age of 20, afemale has 50 pieces of clothing, while a male has 45.We will prove: That for all years over 20 years of age, femalesown more pieces of clothing than males.It is true for age 20 based on the given information.Assume it's true for age k, where k  20.Now, under that assumption we will prove it for k+1. Let thenumber of clothes a female has at the age of k be F. Let thenumber of clothes a male has at the same age be M. At age k+1,a female must have 1.15F pieces of clothing. This is greaterthan 1.1F. Using the inductive hypothesis, this is greater than1.1M, which is the number of pieces of clothing a male owns atage k+1.Consider the following example:Given that the sum of the first k integers is k(k+1)/2, I willprove that the sum for the first k+1 integers is (k+1)(k+2)/2.1 + 2 + 3 + ... + (k+1) = (1 + 2 + 3 + .. + k) + (k+1) = )1(2)1(kkkbecause we are ASSUMING that the formula I have works forthe first k integers. Now, add this up with a common denominator:2)1(2)1( kkk2222kkk2)2)(1(2232kkkkNow, what I have written above is a "template proof" that youcan plug in any value for k. The problem being of course, wedon't know if the formula I have actually holds for any value ofk. BUT, I can simply check that it works for one by pluggingk=1 into the equation below and verifying its truth:2)1(1kkikiThe left hand side and right hand side both evaluate to 1, whenplugging in k=1. So, this formula above is true when k=1. But,based on our template proof, if it is true for 1, it is true for k=2.And if it's true for k=2, it's true for k=3, etc.Now, consider this example about binary trees:We will prove that an inorder traversal of a binary search treeof any height (positive integer) yields the elements in numericalorder. Certainly this is true for a binary tree of height 0, whichhas only one element in it.Now, assume this is true for a binary tree of height k or less.(This is a strong inductive hypothesis. For now, don't worryabout how it differs from a normal inductive hypothesis.)Consider proving it for a binary search tree of height k+1:The tree must look like this:Root / \Left RightSubtree SubtreeIt also follows that both the left and right subtrees have aheight of k or less. During an inorder traversal, all the nodes inthe left subtree are printed using an inorder traversal, then theroot node is printed, then all the values in the right subtree areprinted using an inorder traversal.Since the tree is a binary search tree, all the values in its leftsubtree are less than the root. These all print before the rootprints. Furthermore, because this left subtree has height k orless, these all print in the proper order. Then the root isprinted, which still maintains the proper order of nodes.Finally, all the values in the right subtree are printed. Sincethis subtree is of height k or less, these are ALSO printed in theright order, so that the WHOLE list is in the correct order,finishing the proof.Problem: Prove that SH = FH+3 -1.We will use induction on H, the height of the AVL tree.Base Cases H=0: LHS = 1, RHS = F3 - 1 = 2 - 1 = 1 H=1: LHS = 2, RHS = F4 - 1 = 3 - 1 = 2Inductive hypothesis: For an arbitrary integer k <= H, assumethat Sk = Fk+3 -1.Inductive step: Under the assumption above, prove for H=k+1that Sk+1 = Fk+1+3 -1.Sk+1 = Sk + Sk-1 + 1 (because to form an AVL tree with the min. number of nodes of height k+1, one side of the root must have height k and the other k-1. This is because we need the sides to be within one, but we want to minimize the number of nodes. The only other option would have been k and k, which would NOT minimize the desired value.) = (Fk+3 -1) + (Fk+2 -1) +1, using the I.H. twice = (Fk+3 + Fk+2) - 1 = Fk+4 -1, using the defn. of Fibonacci numbers, to complete proof.It can be shown through recurrence relations, that Fn  1/5 [(1 + 5)/2]nSo now, we have the following:Sn  1/5 [(1 +


View Full Document

UCF COP 3502 - AVL Trees

Download AVL Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view AVL Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view AVL Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?