Computer Science II
Computer Science II COP 3503
University of Central Florida
Popular in Course
Popular in Computer Programming
This 13 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 3503 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 28 views. For similar materials see /class/227465/cop-3503-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Computer Science II
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/22/15
COP 3503 Computer Science 11 CLASS NOTES From Data Structures and Problem Solving using Java Mark Weiss void shellsort int a for int gap alength 2 gap gt 0gap gap 2 l int gap 2 forint i gap i lt alength i int tmp a i intj i f0r j gt gap ampamp tmp lt aj gap j gap aj aj gap aj tmp From Data Structures Algorithms and Applications in Java Sartaj Sahni public class ShellSort sort the elements a0 alength 1 using the shaker sort method public static void shellSortComparable a int incr alength 2 initial increment while incr gt 1 insertion sort all sequences spaced by incr for int i incr i lt alength i insert ai into ai incr ai 2incr Comparable insertElement ai int j for j i incr j gt 0 ampamp insertElementcompareToaU lt 0 j incr a incr a a incr insertElement reduce increment by a factor of 22 if incr 2 incr l last increment must be 1 else incr int incr 22 Day 181 As we have discussed within the context of the binary search tree the performance of the algorithms which utilize the BST are dependent upon the height of the tree We have looked at the DSW algorithm to balance a binary tree In this section of the notes we will look at binary trees which in addition to the ordering properties which ensure that the tree is a search tree there will be structure properties imposed on the tree which ensures that the tree is balanced So all of the binary search tree variants that are discussed in this section of the notes are selfbalancing search trees The AVL tree named after its discoverers Adelson Velskii and Landis but originally called an admissible tree was the first balanced binary search tree Any search tree which is selfbalancing must use balance conditions which are easy to maintain and ensure that the height of the tree is Olog n where n is the number of nodes in the tree The simplest idea is to require that the left and right subtrees have the same height Using the recursive definition of the binary search tree implies that this condition be applied to all the nodes in the tree since every node is considered the root of some subtree While this simple requirement will ensure that the height of the tree is logarithmic in terms of n it is too restrictive because inserting new key values while maintaining overall balance is too difficult ie too costly in terms of time Therefore the definition of the AVL tree uses a slightly different interpretation of balance one that is weaker than total balance between all left and right subtrees yet is still strong enough to ensure logarithmic height of the tree AVL Tree An AVL tree is a binary search tree with the additional balance property that for any node in the tree the height of the left and right subtrees can differ by at most one Notice that the DSW algorithm see Day 22 notes balances trees using the same balancing condition that is employed by the AVL tree However an AVL tree is not necessarily perfectly balanced All of the trees shown in the figure below are AVL trees Day 182 Examples of AVL Trees i In the example AVL trees above the values shown in the nodes are called balancing factors The balance factor of any node represents the difference between the heights of its left and right subtrees The balance factor is the height of the right subtree minus the height of the left subtree Thus for an AVL tree all of the balance factor should be 1 0 or 1 Considering the tree shown in the middle above the balance factor of the root is 1 since the height of the right subtree is 2 and the height of the left subtree is 1 and 2 1 1 The definition of an AVL tree indicates that the minimum number of nodes in an AVL tree is defined by the recurrence equation AVLh AVLh1 AVLh2 1 where AVLO 0 and AVL1 1 are the initial conditions Adel son Vel skii and Landis have proven that this produces the following bounds on the height of an AVL tree depending upon the number of nodes n logn 1 S h lt144logn 2 0328 Therefore the height of the tree is bounded by Olog n and the worst case search requires Olog n comparisons Notice that for a perfectly balanced tree of the same height h logn 1 l Therefore the search time in the worst case in an AVL tree is 44 worse it requires 44 more comparisons than in the best case tree configuration Donald Knuth has shown through empirical results that the average case number of comparisons is much closer to the best case than to the worst case and is equal to log n025 for large n This is why AVL trees are so important for searching applications they have a logarithmic time bound on the search and are selfbalancing Day 183 If the balance factor of any node in an AVL tree becomes less than 1 or greater than H then the tree must be balanced An AVL tree can become unbalanced in one of four ways two of which are symmetric to each other and thus we need to consider only two different situations These two cases are l The result of inserting a node in the right subtree of the right child of a node 2 The result of inserting a node in the left subtree of the right child The first case is the simpler of the two and we will consider it first The diagram below illustrates the technique h evx Ls gtw quot Ix 1 a y h39 if h If h if I h g h r39 h 1 h 1 3 39d b C In a a new node is inserted somewhere in the right subtree of node Q this causes an imbalance in the tree rooted at P since the balance factor in P is now greater than 1 The solution is to rotate node Q about its parent P which is shown in c HaVing done this the balance factor of both P and Q become 0 which is even better than the original tree The second case the result of inserting a new node in the left subtree of the right child is illustrated in the diagram below Day 184 In a a new node is inserted somewhere in the left subtree of Q which creates an imbalance in the tree at node P shown in b and in more detail in c The solution to this problem is a double rotation the first by rotating R about Q as shown in d and then by rotating R about P as shown in e Both of the cases illustrated use a standalone tree to illustrate the technique of the rotation however the tree rooted at P can be part of a larger AVL tree If P itself is the child of some node it is not the root of the entire tree the question arises will additional work be required to adjust the balance of P s predecessors The answer is no Considering the two examples above note that the heights of the two trees which result at the end of the rotations are the same as the heights of the trees before the insertion occurred This means that the balance factor of the parent of the new root Q in the first case and R in the second case remain the same as they were before the insertion and the changes which occur to subtree P are sufficient to restore the balance of the entire AVL tree The problem is in finding a node P for which the balance factor becomes unacceptable after a node has been inserted into the tree This node can be detected by moving up toward the root of the tree from the position in which the new node was inserted and updating all of the balance factors of the nodes which are encountered Then if a node with a i1 balance factor is encountered the balance factor is changed to i2 and the first node whose balance factor is changed in this manner becomes the root P of a subtree for which the balance has to be restored Note that the balance factors above this node will not require resetting using the argument we just presented Shown below are a couple of examples of AVL trees and the rotations which are required to rebalance the tree upon the insertion of a new node 1 An initial AVL tree Day 185 initial AVL tree 7 shown with data values initial AVL tree 7 shown with balance factors 2 An insertion occurs in the left subtree of the right child of node 26 case 2 Day 186 3 The subtree rooted at node 20 must be singly rotated to restore balance 6 nal AVL tree showing data values 636 00 nal AVL tree showing balance factors Day 187 1 An initial AVL tree initial AVL tree 7 shown with data values initial AVL tree 7 shown with balance factors 2 An insertion occurs in the right subtree of the right child of node 26 case 1 Day 188 3 The subtree rooted at node 20 must be singly rotated to restore balance nal AVL tree showing data values nal AVL tree showing balance factors Day 18 9 It is possible that the insertion of a new node into an AVL tree will not require a rotation as the new tree may remain balanced If the balance factors from the newly inserted node up to the root of the tree are all zero the balance factors will need to be updated from the insertion point up to the root of the tree but no rotation will need to be performed This situation is illustrated in the following example Initial A VL tree nodes along the indicated path must all have balance factors reset Day 18 10 nodes along the path with reset balance factors Deletion may be a more timeconsuming task that insertion in an AVL tree Typically an algorithm such as deletionviacopying or deletionviamerging is used to reduce the problem of deleting a node with two descendants to the problem of deleting a node with at most one descendant After a node has been deleted from the tree balance factors must be updated from the parent of the deleted node up to the root of the tree For each node in this path whose balance factor becomes i2 a single or double rotation must be performed to restore the balance of that subtree Notice that the rebalancing does not stop at the first node P for which the balance factor has become i2 as in the case with insertion This means that deletion has the potential for requiring at most Olog n rotations since in the worst case every node along the path from the parent of the deleted node to the root will require rebalancing Deletion of a node does not necessitate an immediate rotation because it may actually improve the balance factor of its parent by changing its parent s balancing factor from i1 to 0 However it may worsen the balancing factor of its grandparent by changing it from a i1 to a i2 For the sake of brevity we ll consider only those cases where the deletion requires an immediate rotation There are four such cases plus four symmetric ones These cases are all shown in the following diagram Day18 ll The rst case of deletion is represented in a which after the deletion which occurs in the le subtree of the right child of P turns into the tree in b The tree is rebalanced by rotating Q aboutP which gives the nal tree c for the first case The second case of deletion is represented in d in which node P has a balance factor of 1 and its right subtree Q has a balance factor equal to 0 A er the deletion of a node in the le subtree ofP shown in e the tree is rebalanced using exactly the same rotation as in the rst case to produce the tree shown in 0 Notice that cases 1 and 2 can be processed together in an implementation after checking that the balance factor on is 1 or 0 When Q is 71 the other two cases for deletion occur which are both more complicated than the rst two Day 18 12 In the third case the left subtree R of Q has a balance factor equal to l as shown in g To rebalance the tree first R is rotated about Q h and then about P i The fourth case differs from the third case only in that R s balance factor is H as in j in which case the same two rotations are performed in order to restore the balance factor of P shown in k and 1 As before cases three and four can be processed together based only upon a check of the balance factor associated with node R Einal Comments On AVL Trees Insertions and deletions in an AVL tree require at most 144 logn2 comparisons Insertion can require either one single rotation or one double rotation and deletion can require 144 logn2 rotations in the worst case However as mentioned earlier the average case requires logn 025 comparisons which reduces the number of rotations in the case of deletions to this number In the average case insertion may lead to one singleone double rotation Empirical results based primarily upon simulations have indicated that deletions in 78 of the cases will not require a rebalancing at all On the other hand only 53 of the insertions do not force the tree out of balance Therefore the more timeconsuming deletion operation occurs less frequently than the insertion operation which does not unduly limit the efficiency of rebalancing AVL trees AVL trees can be extended by allowing the differences in heights A of subtrees to be greater than 1 For example you can allow subtrees to become more and more unbalanced by allowing a greater height differential between the left and right subtrees Not unexpectedly the worstcase height increases as A increases Again empirical results indicate the following trend h 18110gn 071 ifA2 21510gn 113 ifA3 As the experimental evidence indicates the average number of visited nodes increases by onehalf in comparison to pure AVL trees A l but the amount of restructuring required can be decreased by a factor of 10 Day 18 13
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'