Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT open courseware at ocw.mit.edu all right welcome back to 6046 today we continue our theme of data structures uh but this time instead of doing a fancy data structure we're going to look at fancy cool analysis techniques for data structures and these are useful for tons of different data structures especially in the context when you're using a data structure to solve to implement an algorithm uh for example in dyra uh when you learned Dyer's algorithm you had lots of different Heap structures you could use for for the priority que uh in dyra and they give different running times of dyra uh but the key thing in that context is that you cared about the total running time of the algorithm uh less than you cared about the individual running time of each operation and that's what amortization is about it's I guess a technique from financial analysis but uh We've appropriated it in computer science as an analysis technique to say well let's not worry about every single operation cost worst case cost let's just worry about the total operation the sum of all the operations cost that's the whole idea of amortization but there's a lot of different ways to do it we're going to cover four different methods for doing it and three is examples of doing it today and you've seen some essentially in recitation last time uh and you've seen a little bit in 66 so let me first remind you of the example of table doubling from 6046 sorry 66 this came up in the context of hash tables uh as you may call if you store n items uh in a hash table of size M they're M slots in the table let's say using chaining hashing with chaining then we got uh an expected cost of uh constant plus the load Factor size of the table divided by the number of items so we wanted to get constant expected and so we wanted this to always be uh at most a constant I guess we could handle a larger table size although then we are unhappy about our space but we definitely want M to be at least around n so that this works out to order one and the solution for doing that was table doubling whenever the table is too big double it or sorry whenever the table's too small when you have too many items double the size of the table uh so if n n is the thing that we can't control that's the number of items somebody's inserting into the table if n grows to the value uh to match M then uh double m so M Prime = 2 m and uh to double the table you have to allocate a new array of double the size and copy over all the items and that involves hashing but uh overall this will take uh order size of the table work doesn't matter whether I using M or M Prime here because within a constant factor of each other uh and that's bad linear time to do an insertion is clearly bad this is all during one insertion operation that this would happen but overall it's not going to be bad because you only double login times and if you look at the uh total cost so maybe you think oh is it log n per operation but it's not so bad because uh total cost for n insertions from an starting from an empty structure uh is something like 2 to the 0o the big Theta outside 2 to the 1 2 to the two we're only doing insertions this is great 2 to the log n this is a geometric series and so this is order n Theta N I guess so uh to do n insertions cost Theta n so we'd like to say the amortized cost per operation is constant because uh I mean we did n operations total cost was n so sort of on average per operation that was only constant so this is uh the sense in which hash tables are constant expected amortized um and we'll get back to hashing in a future lecture probably I think lecture eight uh but for now we're just going to think about this as a general thing where you need table doubling uh then this gives you a fast way to insert into a table later we'll think about deleting from a table and keeping the space not too big but that's a starting point and this is an example of a general technique called the aggregate method which is probably the weakest way the weakest method for doing amortization but maybe the most intuitive one the aggregate method says well uh what we C we we do some sequence of operations let's say in general there are K operations measure the total cost of those operations divide by K that's the amortized cost per operation you can think of this as a definition but it's not actually going to be our definition of amortise cost we're going to use a more flexible definition but for simple examples like this it's a fine definition uh and it gives you what you want when you have when your sequence of operations is very clear like here there's only one thing you can do at each step which is insert that's my definition of the problem then great we get a very simple sum as soon as you mix inserts and delet Le the sum is not so clear but uh in some situations the sum is really clean so you just compute the sum divide by number operations you get a cost and that that could be the amortized cost and that's the aggregate method works great for simple sums uh here's another example where it uh no sorry let me now give you the general definition of amortized bounds uh which becomes important once you're dealing with different types of operations I want to say an insert costs one bound amortised and maybe a delete cost some other bound so what you get to do is assign a cost uh for each operation I should call it an amortised cost uh such that you preserve the sum of those costs so what I mean is that if I look at the sum over all operations of the amortise cost of that operation and I compare that with the sum of all the actual cost of the operations that amorti should always be bigger because I always want an upper bound on my actual cost so if I can prove that the amortise costs are at most say constant per operation then I get that the sum of the actual cost is at most constant per operation I don't learn anything about the individual costs but I learned about the total cost and in the context of an algorithm like dexra algorithm you only care about the total cost because you're just you don't care about the shortest paths at time T you only care about the shortest paths when the algorithm's completely finished and so in a lot of situations uh maybe not a real-time system but almost everything else you just care about the sum of the costs as long as that's small you can afford the occasional expensive operation uh so this is a more flexible definition um one option would be to assign the average cost to each operation but we have a whole bunch more operations we could say inserts cost more than deletes or things like that in fact let me do such an example uh a couple weeks ago you learned about two three trees uh this would work for any structure though um so I claim uh I'm going to look at three operations on Two Three Trees one is uh create an empty tree so I need to think about how we're getting started in amortization let's say you always start with an empty tree it takes constant time to make one uh I pay log n time I'm going to tweak that a little bit uh for an insertion and I pay zero time per delete in an advertised sense you can write Big O of zero if you like same thing um so deletion you can think of as a free operation why this is a bit counterintuitive because of course in reality the actual cost of a deletion is going to be log in yeah you can never delete more elements than you you can never delete more elements than you've already inserted good count the yeah so uh I can bound the deletion cost by the insertion cost and in the context of just the aggregate method you could look at the total cost of all the operations uh I guess we're not exactly dividing here but uh if we look at the the total cost uh let's say that we do uh C Creations I insertions and D deletions then the total cost becomes uh C + I * log n uh plus d * log n and the point is D is less than or equal to I because you can never delete an item that wasn't already inserted if you're starting from an empty structure and so uh this is I + D * log n uh but that's just at most twice I Times log n so we get C+ I log n and so we can think of that as having a d times zero there zero cost per dele and so this is the sum of the actual costs over here this is the sum of the amortised costs where we say zero for the deletion and we just showed that um this is an upper bound on that so we're we're happy now there's a slight catch here and that's why I wrote Star on every n which is not every operation has the same cost right when you start from an empty structure insertion cost constant time because n is zero uh when N is a constant insertion is constant time when n grows to n it costs log n time at different time N is a different value and N I'm going to use to mean the current size of the structure uh for this argument to work at the moment I need that n is not the current value because this kind of charging Works some insertions are for large structure some are for small structur some deletions are for small some are for large gets confusing to think about we will fix that in a moment but for now I'm just going to Define n star to be the maximum size over all time okay if we just Define it that way then this is this is true that's that will let me pay for any deletion uh but we'll remove that star later on once we get better analysis methods but so far so good uh two very simple examples table doubling two three trees with free deletion of course that would work for any structure with logarithmic insertion and deletion uh but we're going to be using two three trees in a more analyzing them in a more interesting way uh later on so let's go to the next method which is the accounting method it's like the uh the bank tellers analysis if you will um these are all just different ways to compute these sums or to think about the sums and usually one method is a lot easier either for you personally or for each problem more typically each problem usually one or more of these methods is going to be more intuitive than the others they're all kind of equivalent but it's good to have them all in your mind so you can just think about the problem in different ways so uh with the accounting method what we're going to do is Define uh a bank account and an operation uh can store credit in that bank account uh credit's may be not the best word because you're not allowed for the bank account to go negative okay the bank account must always be non- negative balance uh because otherwise your summations won't work out um so when you store credit in the bank account you pay for for it it's as if you're consuming time now in order to pay for it in the future if you and think of operations costing money so whenever I uh do a deletion I spend actual time log in time but if I had log in dollars in the bank and I can pull those out of the bank I can use those dollars to pay for the work and then the deletion itself becomes free in an advertised sense so um this is on the one hand operation and when I do an insertion I'm going to physically take some coins out of myself uh that will cost something in the sense that the amortised cost of insertion goes up in order to put those coins in the bank but then I'll be able to use them for deletion so this is what insertion is going to do I can store credit in the bank and then separately we allow an operation to take coins out of the bank and you can pay for time using the credit that's been stored in the bank okay as long as the balance bank balance remains non- negative at all times this will be good uh the bank balance is a sort of unused time we're paying for it to store things in there if we don't use it well we just have an upper bound on time as long as we go non- negative then we're never uh then the summation will always be uh in the right direction this this inequality will hold Let's do an example uh well maybe this is a a first example so when I do an Insertion I can put uh let's say one coin a value log and star into the bank and so the total cost of that Insertion I pay log and star real cost in order to do the insertion then I also pay log and star for those coins to put them in the bank when I do a deletion the real cost is log NSTAR but I'm going to extract out of it log NSTAR coins and then so the total cost is actually free the total amortise cost is free but um yeah and and the reason that works the reason the balance is always non negative is because for every deletion there was an insertion before okay so it's maybe not it's maybe a less intuitive way to think about this problem but you could think about it that way um and more generally what so what we'd like to say is that we only pay log n without the star the current value of n per insert and uh zero per delete uh advertised uh so we'd like to say okay um let me put uh one coin worth log n uh for each delete for each insertion uh and when I delete I consume the coin and in general the formula here is that the amortized cost of an operation is the actual cost uh plus the deposits minus the uh withdrawals okay so insertion we just double the cost because we pay log in to do the real thing we pay log in to store the coin um that's the plus deposit part so insertion remains log in and then deletion we pay login to do the deletion but then we subtract off the coin uh a value log n so that hopefully works out to zero but again we have this issue that uh coins actually have different amounts depending on what the current value of n was uh you can actually get this to work um if you say well uh there are coins of varying values here and I think the invariant is if you have a current structure of size n you will have one coin of size log one log two log three log four up to log n um each coin corresponds to the item that made and that value and so when you delete an item at size n you'll be removing the log nth coin the coin of value log n okay so you can actually get this to work if you're careful um I guess the invariant is one coin uh value uh log I for I = 1 to n and you can check that in variant holds when I do a new Insertion I increase n by one and I make a new coin of blog that value uh when I do a deletion I'm going to remove that that last coin of login uh so this does work out so we got rid of the N star okay let's use the same method to analyze table doubling we already know why table doubling works but good to think of it from different perspectives and it's particularly fun to think of the coins as being physical objects in the data structure I always thought it would be fun to put this in a programming language but I don't think there is one programming language that has coins in it in this sense um yet maybe you can fix that so uh let's go back to table doubling uh let's say uh when we insert an item into a table and here I'm just going to do insertions uh we'll worry about deletions in a moment uh whenever I do an insertion I'm going to put a coin on that item and the value of the coin uh is going to be constant I'm going to give the constant a name so we can be a little more precise in a moment uh see so uh here's kind of the typical Well here here's an array we start with an array of size one and we insert a single item here and we put a coin on it maybe I'll draw the coin the coin in a color I've lost here so uh I insert some item uh X and I put a coin on that item uh when I do a next insertion let's say I have to double the table to size two I'm going to use up that coin so erase it put a new coin on the item that I just put down call it Y and in general uh okay so the next time I double which is immediately I'm going to go to size four um I erase this coin uh then I um put a coin here when I insert item of course letter after w z is W uh then I put another coin when I have to double again so here I'm going to use these coins to charge for the doubling and then in the next round I'm going to be inserting here here here and here and I'll be putting a coin here here here and here in general you you start to see the pattern so I used up these guys uh that by the time I have to double again half of the items have coins the other half don't because I already used them you have to be careful not to use a coin twice because you only get to use it once it's uh you can't divide money double money unless you're doing stocks I guess so um as soon as I get to a place where the array is completely full when n equals m the last half of the items will have coins I'm going to use them in order to pay for the doubling so the number of coins here will be uh n/2 so this is why I wanted to make this constant a little explicit um because it has to be bigger than two in some sense however much work let's say it takes uh a * n work in order to do doubling then this constant should be something like 2 * a because I need to do the work to double uh but I only have n/2 coins to pay for it uh I don't get coins over here okay so uh when we double the last n / two items have coins and so uh the amorti cost uh of the doubling operation is going to be uh the real cost which is some Theta n minus the number of coins I can remove and their value so it's going to be minus C * n /2 and the point is this is zero if we set C large only has to be a constant it needs to be bigger than two times that constant okay and usually when you're working with coins you want to make the constants explicit just to make sure there's no circular dependence on constants make sure there is a valid Choice C uh that annihilates whatever cost you want to get rid of okay so this is the um the accounting method view of table doubling any questions so far so far so good pretty simple example uh let's get to more interesting examples I guess you also think about the advertised cost of an insert it costs constant real time actual cost is constant you have to also deposit one coin which cost constant time so the advertised cost of an insert is still constant so that's good still we don't know how to deal with deletions uh but let me give you a kind of reverse perspective on uh the accounting method it's again equivalent in a certain sense but in another sense maybe more intuitive some of the time for some people U it's actually not in the textbook but it's the one I use the most so figure it's worth teaching uh it's called the charging method it's also a little bit more um time Trav if you will so if you like time travel this method is for you uh uh or maybe a more pessimistic view is uh blaming the past for your mistakes um so what we're going to do is allow uh there's no bank balance anymore although I mean it's essentially there we're going to allow operations to charge um the some of their cost retroactively to the Past okay not the future uh I actually have a data structures paper which proves that while time travel to the past is plausible time travel to the Future Is Not computationally So you you're not allowed to travel to the Future only allowed to go to the past and say Hey you know give me five bucks okay but I mean you've got to be a little bit conservative in how you do it you can't just keep charging the same operation a million times uh because then the cost of that operation is going up at the end of the day every operation had to have paid for its total charge so there's the actual cost which it starts with and then there's whatever it's being charged by the future so from an analysis perspective you're thinking about the future what could potentially charge me okay um again you can Define the amortise cost of an operation is going to be the actual cost uh minus uh the total charge to the past so when we charge to the past we get free dollars in the present um but we have to pay for whatever the future is going to do so we have to imagine how many times could I get charged in the future I'm GNA have to pay for that now in a consistent timeline uh you will have to have paid for things that come in the future all right so let's do an example actually it sounds crazy and weird but I actually find this a lot more intuitive to think about uh even these very examples so uh let's start with table doubling so uh we have this kind of picture already it's going to be pretty much the same after I doubled the table uh my array is half full and again insertion only although we'll do insertion and deletion in a moment um in order to get from half full to completely full I have to do uh an over two insertions it's looking very similar uh but what I'm going to say is that when I double the array next time I'm going to charge that doubling to those operations okay in general uh this is you can actually say this quite concisely whenever I do a doubling operation I'm going to charge it uh to all the insertions since the last doubling that's a very clear set of items doublings happen and then they don't happen for a while I just all those insertions that happened since the last doubling charge to them um and how many are there well as we've argued there are n over two of them and the cost of in order to make this doubling free I need to charge Theta n so uh you know this doubling cos Theta n but there's n over things to charge to I'm going to uniformly distribute my charge to them uh which means I I'm charging a constant amount to each and the key fact here is that I only charge an uh an item I only charge an insert once because of this since Clause I never will charge an item twice as long as I'm only inserting for now okay if you look over all time you will only charge an insert once that's good because the inserts have to pay for their total charge in the future there's only one charge and it's only a constant amount then advertised cost of insert is still constant advertised cost of doubling is zero because we charge the entire cost to the pest okay so same example but slightly different perspective let's do a more interesting example inserts and deletes and a table uh let's say I want to maintain that the size of the table is always within a constant factor of the number of items currently in the table if I just want an upper bound then I only need to double but if I want also a lower bound if I don't want the table to be too empty then I need to add table having so what I'm going to do is when the table is 100% full I double its size uh when the table is 50% full should I have it in size that work nope because after you insert it and then L again right uh at the it's I can basically do insert delete insert delete insert delete and every single operation costs linear time because maybe I'm a little bit less than half full uh sorry yeah if I'm a little bit less than half full then I'm going to shrink the array into half get rid of this part uh then if I immediately insert it becomes 100% full again I have to double in size and then if I delete it becomes less than half full and and I have to have in size every operation would cost linear time so advertise cost is linear time that's not good uh so what I'll do is uh just separate those constants a little bit when I'm 100% full I will double that seems pretty clear but let's say uh when I'm a quarter full then I will have any value less than 50 would work here but uh have like that uh this will actually work this will be constant amorti per operation but it's all of uh especially the initial analysis we did of table doubling isn't going to work here because it's complicated that thing's going to shrink and grow over time um you know just summing that is not easy it depends on the sequence of operations but with charging and also with coins we could do it in a pretty clean way I'm going to do it with charging uh so this is um this particular choice of con is nice because when I double a full array it's half full and also when I have an array that's a quarter full like this and then I divide it and then I shrink it I get rid of this part it's also half full so whenever I do a double or a half the new array is half full 50% that's nice uh that's nice because 50% is far away from both 25% and 100 okay so our kind of our nice state is right after a doubling or a half then we know that our structure is 50% full in order to get to an underflow state where we have to have have to delete at least a quarter of the items right a quarter of M in order to get to overflowing where I have to double I have to insert at least M over two items okay either way a constant fraction time M that's what I'm going to charge to now to be clear um when I'm 50% full I might do I might insert delete insert delete many different inserts and deletes at some point one of these two things is going to happen though in order to get here I have to do at least M over4 deletions I might also do more insertions and deletions but I have to do at least that many and those are the ones I'm going to charge to so um I'm going a charge uh having operation to the at least uh M over4 deletions since the last resize of either type doubling or having okay and I'm going to charge the doubling to the at least m/2 insertions uh since the last resize okay and that's it because I having cost Theta M time doubling cost Theta M time I have Theta M operations to charge too so I'm only charging constant for each of the operations and because of this since last resize Clause it's clear that you're never charging an item never charging an operation more than once um because you can divide time by when the resizes happen grows or shrinks halves or doubles um and each resize is only charging to the Past window of time so it's like you have epics of time you separate them you only charge within your epic okay so that's cool and so you only get constant number of charges per item of a constant amount therefore insertions and deletions are constant amortised having a doubling is free amortised clear this is where amortization starts to get interesting right uh you can also think of this example in terms of uh coins but uh with putting coins on the items but it's then you have to think about the invariance of where the coins are which I find to be more work we actually had to do it up here always claiming the last half of the items had coins you have to prove that really uh with this method you don't I mean the what you have to prove is that there are enough things to charge to we had to prove here that there were n over two items to charge to kind of the same thing but it was very clear that you weren't charging to the same thing more than once you're never trying to use a coin that wasn't there because of the since Clause so uh to each their own anything either way would work all right I think I will skip this example but uh for I'll just mention it so for Two Three Trees we said deletions were free um and we did that with the coin in that there was one coin of size log I for each I you could instead say uh when I delete an item I'm going to charge it to the insert that made n this current value uh because that insert paid log n actual cost so it can afford to pay another login to to pay for the deletion of some other item uh the one we're currently deleting and that works that you don't double charge to an insert because uh you're decreasing n right now so for to get up to that value again you would have had to do another insert so uh same thing different slightly different perspective let's go to something even more interesting and some sense more powerful the last method on the list which is potential method this is a good exercise in how many ways can you skin a cat so uh potential method I like to call it uh defining karma in a formal way um is more like the accounting strategy we're going to think about there being a bank count with some balance but we're going to Define that balance as a function of the data structure state so and it's called the potential potential function but you can think of it as a bank balance you can think of it as kinetic potential I guess potential energy just like the bank account uh we want uh this function to always be non- negative we'll also make it an integer that will be convenient um okay uh and the potential function is basically trying to measure how bad is the data structure right now it's again like saving up for a rainy day we want that whenever we have to do an expensive operation like a double or a have uh that this potential has grown large enough that we can charge that cost to a decrease in the potential so it's like this is storing up energy and whenever you know whenever we have some free time we'll give some of that time to the potential function uh it's just like the accounting method in a certain sense but we're defining things differently over here we explicitly said hey look I'm going to store some credit right now uh so we're basically specifying the Delta and here we're saying I'm going to consume some credit right now over here we're going to Define this magical function of the current state from that you can compute the Deltas but also from here you can inte and compute the potential function so they're interchangeable but usually it's easier to think about one perspective or the other really often you can think of you can just look at what's going on with the data structure and say Hey you know these this prop this uh aspect of the data structure makes it bad makes makes costly operations and you can just Define the potential function and then just check that it works uh but it's a little bit of black magic to come up with these functions so depends how you like to think about things um so uh as before we can define an advertise cost it's going to be the actual Cost Plus the change in the potential uh so change of potential is just uh the potential uh after the operation the potential before the operation okay um I highlight that and it's kind of obvious from the way we set things up but what I care about is the sum of the amortized costs I care about that because because it's supposed to be an upper bound on the sum of the actual costs and if you just look at what that sum is I have on the right hand side I have amortise Cost Plus this the the fee after the operation minus the fee before the operation if I add all those up this part telescopes right you get cancellation from each term with the previous term so the sum of the amortized costs is equal to the sum of the actual costs uh plus v of the at the end minus V at the beginning so uh slight catch with the potential method when you define things this way uh you also have to pay for fee at the beginning because we want the actual cost to be at most amortised cost okay so we need to take this part and put it over here so it's at most amort sum of amortised Cost Plus fee of the beginning okay this part becomes negative so we usually just ignore it um can only help us so when you define a potential function you'd really like it to be zero at the beginning this funny but you pay fee of the beginning State at the beginning of time and when you've done zero operations you really like the cost to be zero so uh you and you don't you don't want to have to have stored stuff in the bank so this should be uh constant would probably be okay or whatever the cost of your first operation is but should be constant or zero and usually we do this by saying let let's start with an empty structure and work from there usually Fe of an empty structure is zero and all as well so when you're defining things with potential function you have to be careful about your initial State you have to make sure it's non- negative just like you did over here but uh you didn't have to worry about this part over there okay all this infrastructure what's it good for let's do some examples these are going to be the most interesting examples so a kind of classic example of amortization is incrementing a binary counter so when you have some binary value like this one and you increment it many bits change but only constant number are going to change in an amortized sense if I start with a zero Vector zero bit vector and I increment well the very first increment cost one next increment cost two next incr costs one next increment costs three then one then two then one then four then it's a fractal uh but instead of thinking about that fractal and you know working hard to prove that summation is linear for n operations let's use the potential method and the intuition here is actually pretty easy uh because an increment has a very clear cost uh it's just the number of trailing ones plus one okay that's what it is in actual cost we'd like that to be constant so intuitively what is making an increment bad if you had to name one thing if I just look at a configuration is this bad is this bad how bad is the configuration Yeah the more triling ones you have the worse the state is the more trailing ones the worse the state is so that's one natural definition turns out it won't work uh let's see why um I think uh here's an example so near the end of our increment stage we have a whole bunch of ones but no no trailing ones number of trailing ones is zero if I do a single increment now the number of trailing ones is n so if you look at the amortise cost it's the actual Cost Plus the change in fee and so I actually pay n for that operation in an adverti sense and that's no good we won't only want to pay constant but it's on the right track so number of triling ones it's it's it is the natural thing to try but it doesn't quite work for our definition of fee other ideas yeah the total number of s bits the total number of ones yeah let's define Fe to be the number of one bits that will work uh but you get both get a frisbee sorry good thing I missed um okay number one bits intuitively ones are bad and uh this is a good definition because when I increment I only create one one so I'm not going to have this issue that Delta Fe goes up by a lot sorry that Fe goes up by a lot the Delta Fe is really large uh because even in this scenario if I increment I only add one one in this scenario I destroy three ones and add one okay in general if they're are let's say um T trailing bits then an increment destroys uh T1 bits and it creates one one bit that's always what happens T could be zero and then I have a net positive of one but most of the time actually I destroy one bits well more than half the time I destroy one bits I just create a single one bit in terms of the total number of ones and so the amorti cost uh is the uh actual cost which is this uh 1 plus T um I'm actually G to remove the well yeah I'd like to remove the Big O if I could um I'm going to count I want to be a little bit precise about my counting because I have to do a minus sign here if I just wrote minus t uh that doesn't quite work out because there's a constant here that I have to annihilate if I count the number of bits that change then that's exactly 1 plus T in an increment um and now the change of potential is that I decrease by t i increase by one I get zero that seems a little bit too small zero time per operation uh you're adding a one you're not subtracting or you're not subtracting subtracting your eyes oh right sorry that's two thank you I just can't do the arithmetic I wrote everything correct uh but this is a plus one and a plus one T minus t is the key part that cancels now if you were measuring running time instead of uh instead of the number of changed bits this you'd have to have a big O here and in that case you'd have to Define Fe to be some constant times the number one bits so you can still set that constant large enough so that this part which is multiplied by C uh would annihilate this part which would have a big O okay I guess I'll write it in Just for kicks but that's why you've seen both versions this would be minus C * t + 1 * C okay so that would still work out if you set C to the right value you will still get two um so binary counters constant advertised PR operation so I think this is very clean much easier than analyzing the fractal of the costs uh now binary counter with increment and decrements that doesn't work uh there's there are other data structures to do it but that's for another class um Let's do let's go back to two three trees because I have more interesting things to say about them any questions about binary counters okay as you saw it wasn't totally easy to define a potential function but uh we're going to see you see enough examples you get some intuition for them but it's it is probably the hardest method to use but also kind of the most powerful I would say all hard amortizations use a potential function that's just life uh finding Lim is tough that's the that's reality I want to analyze insertions only in Two Three Trees then we'll do insertions and deletions and uh I want to count how many splits in a 23 tree uh when I do an insertion so remember when you uh insert into a 23 tree say you started a leaf you insert a key there if it's too big you split that node into two parts which causes an insert of a key into the parent then that might be too big and you split and so on so total number of splits per insert upper bound log n okay it's definitely log n in the worst case that's sort of the actual cost but as you may be guessing I claim the amortized number of splits is only constant and first we'll prove this with insertion only uh with insertion and deletion in a 23 tree is actually not true but for insertion only this is true so let's prove it um 233 we have two types of nodes two nodes and three nodes I'm counting the number of children not the number of keys is one smaller than the number of children sorry no no vertical line there this is just some key X some key X and Y okay um so uh when I insert a key into a node it momentarily becomes a four node you might say uh with which has three keys X Y and Z it's a four node it has four children hence the four and we split it into uh x and z there's the four children same number uh but now they're distributed between x and z and then y gets promoted to the next level up and which allows us to have two pointers to x and z that's how two three trees work that's how split works now um I want to say that splitting I want to charge the splitting to something intuitively uh let me also let's say y was the key that inserted so we started with x z which was a three node when we did an insert it became a four node and then uh we did a split which left us with two two nodes and something uh so what can you say overall about this process what what seems like what's making this example bad what's making the split happen in some sense I mean the insert is one thing but there's another thing we can charge to inserts not enough because we're going to do log and splits and we can only charge to insert once if we want constant advertisement found yeah number of three number of three notes exactly that's a good potential function because on the left side of this picture we had one three node on the right side of the picture we had two two noes now there's what's happening to the parent we'll have to worry about that in a moment but you got the intuition number of three notes if you look I looked at just a single operation here but if you look more generally about an expensive insert and that it does many splits the only reason that can the only way that can happen is if you had a chain of three nodes all connected to each other um and you do an insert down here this one splits then this one splits then this one splits so there were all these three nodes just hanging around and after you do the split uh the parent of the very last node that splits that might become a three node so that would be up here here somewhere you might have made one new three node but then this one uh is a couple of two nodes this becomes a couple of two nodes and this becomes a couple of two nodes so if you had uh K three nodes before afterwards you have one sound familiar this is actually exactly what's going on with the binary counter so this may have seem like a toy example but we create uh over here we created at most one one bit down here uh we create at most one three note which is when the split stops when the split stops that's the only time we actually insert a key into a node and and it doesn't split right because otherwise you split when you split you're always making two nodes and that's good at the very end when you stop splitting you might have made one three node so uh in an insert uh let's say the number of splits equals k then the change of potential for that operation is uh minus k + one because every for every split there was a three node to charge to or for every split there was a three node that became two nodes two two noes so the potential went down by one because you used to have one three node then you had zero at the very end you might create one three node that's the plus one okay and so the amortized cost is just the sum of these two things and we get one it's K minus k + 1 is one cool huh this is where potential method becomes powerful I would say you can can view this as a kind of charging argument but it gets very confusing maybe with coins is is the most plausible you essentially the invariant you'd want is you have a coin on every three node it's same thing of course but it's I think easier to think about it this way you say well three nodes seem to be the bad thing let's just count them let's just see what happens it's more like you say I want to have this invariant that there's a coin on every three nodee how can I achieve that and it just works magically because a it helps it was true and B we had to come up with the right potential function those are tricky and in general thematization unless you're told on a pet prove order te amortized uh you don't always know what the right running time is and you just have to experiment all right our final example most impressive uh let's go over here it's a surprise I guess it's not even on the list list I want to do um this was great for inserts but what about deletes I want to do inserts and deletes I'd like to do two three trees uh but two three trees don't work if I want to get a constant amortised Bound for inserts and deletes I got a constant amortised here for inserts uh I should be clear I'm ignoring the cost of searching let's just say searching is cheap for some reason maybe you already know where your key is and you just want to insert there uh then insert only cost constant advertised in a 23 tree insert and delete is not that good it can be log in for every operation if I do inserts and deletes uh essentially for the same reason that a binary counter can be n for every operation if I do uh increments and decrements I could be here you know increment a couple times and then I change a huge number of bits if I immediately decrement then all the bits go back and increment all the bits go back decrement all the bits go back so I'm changing n Bits in every operation in the same way if you if you just think of one path of your tree and you think of the zero bits as two nodes and the one bits as three nodes when I increment by inserting at the bottom all those threes turn to one except the top I make a three that's just like a binary counter went from all ones to 1 z um and then if I decrement if I delete from that very same Leaf then I'm going to have to do merges all the way back up and turn those all back into three nodes again and so every operation is going to pay log n Now log n's not so bad but I really want constant so I'm going to introduce something new called two five trees and all it's going to be exactly like B trees that you learned except now uh the number of children of every node should be between two and five okay all the operations are defined the same uh we've already talked about insert now insert when you have six children then you're overflowing and then you're going to split in half and so on so actually I should draw that picture because we're going to need it um so if I started with a five node which means it has four keys and then I insert into it I get a six node that's to many six children okay that's too much so I'm going to split it in half which is going to leave uh a three node and a single item which gets promoted to the parent and another uh three node okay so we started with a five node and the result was two three nodes okay that's split and we also contaminate the parent a little bit but that may lead to another split which will look like this again so if we're just doing insertions fine we just count the number of five notes no no different right but I want to do simultaneously insert and delete so uh let's remember what happens with a delete so if you just delete a key and a leaf uh the issue is it may become too empty so uh what's too empty well the minimum number of children we're allowed to have is two so two empty would be that I have one child so maybe initially I have two children and I have a single key X then maybe I delete X and so now I have U zero keys this is a one node it has a single child okay weird um and in that case we uh there's sort of two situations May maybe your sibling has enough uh Keys you can just steal one then you then that was really cheap um but the other case is that you um yeah I'm also going to have to involve my parent so maybe I'm going to take a key uh from X and merge all these things together that's y uh then what I get is X Y I have add two children here three children here okay I also messed up my parent a little bit but that's going to be the recursive case so I'm going to this is a sort of merge operation in general I merge with my sibling and then potentially split again or you can think of it is stealing from your sibling as you may be experienced with doing I didn't have siblings so I didn't get to do that but uh I stole from my parent so whatever however you want to think about it um that is merging in a be tree we started with a tun note here we ended up with a three Noe H that's good it's different at least so the Bad Case here is a five node Bad Case here is a two node what should I use a potential function yeah number of nodes with two or five children yeah so that's it just combine with the sum it's going to be a number of nodes with two children plus the number of nodes with five children this is measuring Karma this is how bad could is my tree going to be uh because if I have two nodes I'm really close to underf flowing and that's potentially bad if I happen to delete there uh bad things are going to happen if I have a bunch of five nodes splits could happen there and I don't know whether it's going to be an answer or delete next so I'm just going to keep track of both of them and luckily neither of them output fives or twos if they did like if we did two three trees this is a total nightmare because you can't count the number of two nodes plus the number of three nodes that's all the nodes potential NE only changes by one in each step that would never help you okay but here we have enough of a gap between the lower bound and the upper bound and in general any constants here will work and these are usually called AB trees generalization of B trees where you get to specify the lower bound and the upper bound as long as a uh what's the way as long as a is strictly less than b over2 then this argument will work as long as there's a at least one gap between A and B over2 then uh this argument will work because the small in the small case you start with with the wor with the minimum number of children you can have you'll get one more in the end um and in the other situation you have too many things you divide by two you don't want dividing by two to end up with the bad case over here that's what would happen even with two four trees two three four trees um but with two five trees there's enough of a gap that when we split five and half we get threes only no twos and when we merge twos we get threes no fives okay so uh in either case if we do a split let's if we do an insert uh with K splits uh the change in potential is uh minus k + 1 again we might make a single uh five child node at at the top when we stop splitting but every other time we split we uh or every time we split we've taken a five node and destroyed it left it with two three nodes so that decreases by K and so this K cost gets canceled out by this negative K and change potential so the amortized cost is one just like before uh but now also with delete with K merge operations where I'm treating all of this as as one operation um again the change of potential is minus k + 1 potentially we we stop merging because we stole one key from our parent it may now be a two node whereas before it wasn't if it was already a two node then there would be another merge and that's actually a good case for us but when the merges stop uh they stop because we hit a node that's at least a three node then we delete a key from it so potentially it's a two node so potentially the potential goes up by one we make one new bad node but every time we do a merge we destroy bad nodes because we started with a two node we turned it into a three node so again the amortised cost is the actual cost which is K plus the change of potential which is minus k + 1 and so the amorti cost is just one constant number of splits or merges per insert or delete and so this is actually really nice um if you're in a model where changing your data structure is more expensive than searching your data structure for example you have a lot of threads in parallel accessing your thing you're on a multi-thread multi core machine or something you have a shared data structure you really don't want to be changing things very often um because you you have to take a lock and then that slows down all the other threads uh if searches are really fast but splits and merges are expensive then this is a reason why you should use two five trees instead of two three trees because two three trees they'll be splitting and merging all the time log n it's not a huge difference log n versus constant but with data structures that's usually the Gap right last class we were super excited because we went from log to log log here we're excited we go from log to constant it's a little better but they're all small numbers uh but still we we like we like to go fast as fast as possible and in a real system actually it's even more important because splitting the root is probably the worst because you're always everyone's always touching the root in a 25 tree you almost never touch the root almost always splitting and merging at the leaves whereas in a two3 tree you could be going all the way to the root every single time so uh that's my examples any questions four free minutes cool that's amortization