LAB Data Structures
LAB Data Structures CS 230
Popular in Course
Popular in ComputerScienence
This 17 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 230 at Wellesley College taught by Staff in Fall. Since its upload, it has received 22 views. For similar materials see /class/230947/cs-230-wellesley-college in ComputerScienence at Wellesley College.
Reviews for LAB Data Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
CS23O Data Structures Handout 28 Prof Lyn Turbak Sunday December 8 2002 Wellesley College 23 Trees Balanced Search Trees Many data structures use binary search trees or generalizations thereof Operations on such search trees are often proportional to the height of the tree To guarantee that such operations are e icient7 it is necessary to ensure that the height of the tree is logarithmic in the number of nodes This is usually achieved by some sort of balancing mechanism that guarantees that subtrees of a node never differ too much in their heights There are many forms of balanced search tree Here we will study a particularly elegant form of balanced search tree known as a 23 tree There are many other forms of balanced search trees7 some of which you will encounter in 08231 These include red black trees7 AVL trees7 2 3 4 trees7 and B trees 23 Trees A 2 3 tree has three different kinds of nodes 1 A leaf7 written as 2 A 2 node7 written as AA X is called the value of the 2 node l is its left subtree and r is its right subtree Every 2 node must satisfy the following invariants a Every value 1 appearing in subtree I must be S X b Every value 1 appearing in subtree r must be 2 X c The length of the path from the root of the 2 node to every leaf in its subtrees must be the same 3 A 3 node7 written as AAA X is called the left value of the 3 node Y is called the right value of the 3 node l is its left subtree m is its middle subtree and r is its right subtree Every 3 node must satisfy the following invariants 1 Every value 1 appearing in subtree I must be S X 2 Every value 1 appearing in subtree m must be 2 X and S Y 3 Every value 1 appearing in subtree r must be 2 Y 4 The length of the path from the root of the 3 node to every leaf in its subtrees must be the same The path length invariant on 2 nodes and 3 nodes means that 2 3 trees are necessarily balanced the height of a 2 3 tree with n nodes cannot exceed log2n 1 Together the tree balance and the ordered nature of the nodes means that testing membership in inserting an element into and deleting an element from a 2 3 tree takes logarithmic time 23 Tree Examples Given a collection of three or more values there are several 2 3 trees containing those values For instance below are all four distinct 2 3 trees containing rst 7 positive integers t3 t4 We shall use the term terminal node to refer to a node that has leaves as its subtrees To save space we often will not explicitly show the leaves that are the childred of a terminal node For instance here is another depiction of the tree t2 above Without the explicit leaves 23 Tree Insertion Downward Phase When inserting an element 1 into a 2 3 tree care is required to maintain the invariants of 2 nodes and 3 nodes As shown in the rules below the order invariants are maintained much as in a binary search tree by comparing 1 to the node values encountered when descending the tree and moving in a direction that satis es the order invariants In the following rules the result of inserting an element 1 into a 2 3 tree is depicted as a circled 1 with an arrow pointing down toward the tree in which it is to be inserted X and Y are variables that stand for any elements While triangles labeled l m and r stand for Whole subtrees In the case of insertion such trees must be non empty The rules state that elements equal to a node value are always inserted to the left of the node This is completely arbitrary they could be inserted to the right as well 23 Tree Insertion Terminal Cases lf 1 reaches a terminal 2 node with value X the balance invariant can be maintained by ab sorbing the inserted value 1 in a newly constructed 3 node with values 1 and X as shown in the following cases o However if lf 1 reaches a terminal 3 node with values X and Y the value 1 cannot be absorbed But it is possible to split the three values 1 X and Y into two terminal 2 nodes and a third value that is kicked upstairs because there is no room downstairs In the following rules the value kicked upstairs is drawn in a circle with an arrow pointing up from it and with two subtrees that result from the split We will consider the height of such a con guration to be the height of the subtrees 7 ie the height does not include the circled element It is an invariant that the heights of the two subtrees of a kicked up node will be identical a 03X 0 Xltvgt 0 23 Tree Insertion Upward Phase If there is a 2 node upstairs the value kicked upward call it m can be absorbed by the 2 node If there is a 3 node upstairs it cannot simply be absorbed and another split takes place in which yet another value is kicked upstairs This process continues until either the kicked up value is absorbed or the root of the tree is reached In the latter case the kicked up value becomes the value of a brand new a new 2 node that increases the height of the tree by one This is the only way that the height of a 2 3 tree can increase You should convince yourself that path lengths and element order are unchanged by the down ward or upward phases of the insertion algorithm This means that the tree result from insertion is a valid 2 3 tree 23 Tree Insertion Example Here we show the letter by letter insertion of the letters A L G D R I T H M S into an initially empty 2 3 tree ingrt insert ingrt neroot A L a insert H insert new root H H insert 23 Tree Deletion Downward Phase The downward phase for deleting an element from a 2 3 tree is the same as the downward phase for inserting an element except for the case when the element to be deleted is equal to the value in a 2 node or a 3 node In this case7 if the value is not part of a terminal node7 the value is replaced by its in order predecessor or in order successor just as in binary search tree deletion This leaves a hole in a terminal node The goal of the rest of the deletion algorithm is to remove the hole Without violating the other invariants of the 2 3 tree 23 Tree Deletion Terminal Cases Handling the removal of a hole from a terminal 3node is easy just turn it into a 2 nodeI e e To deal with a hole in a terminal 2 node7 we consider it to be a special hole node that has a For the purposes of calculating heights7 such a hole node does contribute to the height of the tree This decision allows the the path length invariant to be preserved in trees with holes single subtree 23 Tree Deletion Upward Phase The goal of the upward phase of 2 3 tree deletion is to propagate the hole up the tree until it can be eliminated It is eliminated either 1 by being absorbed into the tree as in the cases 2 37 and 4 below or 2 by being propagated all the way to the root of the 2 3 tree by repeated applications of the case 1 If a hole node propagates all the way to the top of a tree7 it is simply removed7 decreasing the height of the 2 3 tree by one This is the only way that the height of a 2 3 node can decrease There are four cases for hole propagationremoval7 which are detailed below In the following rules7 triangles stand for subtrees7 which may possibly by empty You should convince yourself that each rule preserves both the element order and path length invariants 1 The hole has a 2n0de as a parent and a 2n0de as a sibling In this case7 the heights of the subtrees l7 m and r are the same 2 The hole has a 2n0de as a parent and a 3n0de as a sibling In this case7 the heights of the subtrees a7 b c and d are the same 3 The hole has a 3node as a parent and a 2node as a sibling There are two subcases a The rst subcase involves subtrees a b and 0 whose heights are one less than that of subtree d b The second subcase involves subtrees b c and d Whose heights are one less than that of subtree a When the hole is in the middle7 there may be ambiguity in terms of Whether to apply the right hand rule of the rst subcase or the left hand rule of the second subcase Either application is OK 4 The hole has a 3node as a parent and a 3node as a sibling Again there are two subcases a The rst subcase involves subtrees a b c and d Whose heights are one less than that of subtree e b The second subcase involves subtrees b c d and 6 whose heights are one less than that of subtree a When the hole is in the middle7 there may be ambiguity in terms of whether to apply the right hand rule of the rst subcase or the left hand rule of the second subcase Either application is OK 23 Tree Deletion Example Here we show the letter by letter deletion of the letters A L G D R I T H M S from the nal 2 3 tree of the insertion example delete Case 1 H H replace by pred ISIDOVS gt root hole saggt 1 ISIBVS del egtte del egtte root hol M S At the point where case 3b was applied7 it is also possible to apply case 4a instead This leads to the following alternative deletion sequence Case 4a replace a delete H H by pred saggt 1 ISIBVS del egtte del egtte root hol M S There are some other choices in the above sequences In each of the spots where a deleted value in a non terminal node was replaced by its in order predecessor it could have been replaced by its in order successor CS23O Data Structures Handout 29 Prof Lyn Turbak Tuesday December 9 2002 Wellesley College C8230 JEOPARDY THE HOME VERSION Asymptotics 1 Consider the function fn 3n 7 List all of the following sets that do not contain f 01 91 91 C71 901 901 003 nz 903 2 List the following eight asymptotic complexity classes in order from smallest to largest n 1 3 n logn 9009171 9012 9013 92 3 Give the asymptotic complexity class ie7 G notation for the best algorithm we have studied for each of the following problems a Inserting n elements one at a time7 into a sorted array b Popping the top element off of a stack of n elements c Searching for an element in a balanced binary tree c Sorting a list of n elements e Deleting an element from a balanced binary search tree 4 Match up each of the following algorithms with the recurrence equation that best characterizes 1t binary search T101 1 T1n 7 1 linear search T201 1 2 T201 7 1 merge sort T3n n T3n 7 1 selection sort T401 1 T4n2 towers of Hanoi T5n n 2 T5n2 5 List all of the following recurrence equations whose solution is T1 71 T2 71 12T2n71 E gt gt n n T3n2 nnT4nil gt gt gt a n n2T5n2 T7 77 12T7n2 Running Times ll Which of the following sorting algorithms have n logn running times in the worst case a selection sort b merge sort c quick sort 1 insertion sort e heap sort using a complete heap f tree sort ie7 build a EST and list elements in in order 2 List all of the following that can be done in linear time in the worst case a Determining if z is in a lengthn listi b Sorting a list of n elements c Building a BST from a list of n elements d Listing in sorted order all elements of an 77element BST 6 Building a complete heap from a Vector of n elements f Listing in sorted order all elements of an 77element complete heapi 3 List all of the following that can be done in logarithmic time in the worst case 3 Determining if z is in an array b Determining if z is in a sorted vector 3 Determining if z is in a balanced binary tree d Determining if z is in abalanced binary search tree e Inserting as into a complete heap f Deleting z from a leftist heap g Merging two complete heaps h Merging two leftist heaps 4 Consider the following method public static IntList in0rderList IntTree t if lTiiSLeaf return IL emptyO else return ILappendin0rderListITleftt IL prependlT valuet in0rderListlTrightt For each of the following assumptions write a recurrence equation describes the worst running time of the method and give the asymptotic solution of the equation 1 t is a balanced tree 2 t is an arbitrary tree 5 1 Write a recurrence equation for the worst case running time of the following method 2 give the asympotic solution of the equation and 3 describe a simple modi cation to the method that dramatically improves its asymptotic running time public static int f ObjectList L if ILisEmpty return 0 else return lLlengthLILlengthL fILtailL Gotchas 1 What is the bug in the following Java method public int sum Vector v 2 int s 0 for int i 0 i lt vsize i s s vgeti return s What is the bug in the following Java class public class Location private Point where public Location Point w Point where w public int x return wherex 3 What is the bug in the following Java method public static int toInt Object x if x instanceof Integer return xintValue else return 0 4 Draw a binary tree that is not a binary search tree but for which the following buggy isBST method returns true INCORRECT version of isBST public static boolean isBST IntTree t return IT isLeanquot II IT isLeanT left i ITivaluet gt ITivalueITileftt ampamp isBSTUT leftU J ampamp ITiisLeanTiright i ITivaluet lt ITivalueITirightt ampamp isBSTITirightt 5 What output is displayed by the following Java method when invoked on the following vector of strings a b c d e 7 public static void removeAndDisplay Vector v 39C for int i O i lt vsize igt 39C Systemoutprintlnvremovei Lists 1 Several data structure implementations we have studied have instance variables that are mutable lists with dummy header nodes What is the purpose of the dummy header node 2 What is wrong with the following method for testing if an integer list is sorted public static boolean isSorted IntList L return ILisEmptyL ILheadL lt ILheadILtailL ampamp isSortedILtailL 3 Describe 1 one advantage of a mutable list over an immutable list and 2 one advantage of an immutable list over a mutable list 3 Describe 1 one advantage of a mutable list over an immutable list and 2 one advantage of an immutable list over a mutable list 4 Flesh out the body of the following method for turning a nonempty noncyclic mutable list into a cyclic list ie7 a list whose last node s tail points to its rst node public static void cylcify DbjectMList L flesh this out 5 Answer both of the following 1 what is the running time of the following method on a list of length n 2 rewrite the body of the method so that it has the same behavior but has an asymptotically better running time public static IntList revDouble IntList L if ILisEmptyL return L else ILpostpendrevDoubleILtailL 2ILheadL Trees 1 List the values of all nodes in the following tree at which the heap condition is not satis ed 2 List the values of all nodes in the following tree at which the binary search tree condition is not satis ed 3 List the values of all nodes in the following tree at which the leftist condition is not satis ed 4 Draw the tree that results from dequeuing an element from the following complete heap 5 For every n is it possible that all the distinct integers in can be arranged into a single binary tree that is both a EST and a leftist heap Assume that larger numbers have higher priority Potpourri 1 List all of the following collections for which a balanced binary search tree is an ef cient representation 0 bag priority queue o queue 0 set stack table 2 For each of the following real life collections give the data structure that would most appropri ately model the situation cities visited during a trip bag dictionary entries priority queue emergency room waiting area queue pile of papers set shopping cart of grocery items stack supermarket checkout line table 3 Match up each of the following collections with the data structure that is most appropriate for representing it priority queue 2 3 tree queue cyclic linked list sequence leftist heap set non cyclic linked list stack vector 4 Answer both of the following 1 Is every complete heap a leftist heap 2 Is every leftist heap a complete heap 5 What is the largest n such that all the distinct integers in can be arranged into a single binary tree that is both a EST and max complete heap