Video 2-7: Biased Search Trees

0:02 So, in the next section we'll finally look at update operations, insertion solutions, and a few others that splay trees can support. And we'll see that much of that is is relatively easy following from the access lemma that we already have. So, much of the hard work is already done. Uh we before even starting with the analysis, we convinced ourselves that insert, delete, split, join are essentially all implemented as variants of splaying some nodes or maybe two splays. So, in a way analyzing the splay calls is all that's needed, but I want to explicitly state that result again so that you have the the precise cost. And in some cases uh there's a um a little interesting distinguishing uh the case distinction in the cost that I think it's good to be aware of, namely whether or not the key is in the tree. Okay. Uh The problem with our analysis so far is that the potential was fixed for a single tree whose node set is static. It doesn't change.

1:09 That doesn't really work if you want to do updates of the kind of adding new nodes. Like somehow I'm now creating potential from nowhere. And that turns out not to work with the analysis we've done. Maybe you can work through that in a different way. But the easier hack, if you like, is to say ah the potential is actually for a whole universe that contains many trees potentially. And I'm just tracking the entire state of all trees together over the lifetime of this data structure. So, in general we have a collection of trees. They are initially all empty. Also, uh the items never actually are created as from scratch, but they all exist in the ether from the beginning. And if you delete them again, if they are deleted from all from from their tree, then they go back to the ether. Uh but they've always been there and will always be there. So, anyway uh there's some some large universe where for any Remember, we do this for each application. So, whenever you use splay trees in a sequence of operations or a collection of splay trees, I should say, in a sequence of operations.

2:23 Uh you can track the entire lifespan of the first splay tree being used until the last splay tree dies. And over that's whole lifespan of all these trees, there's going to be some union of all items that ever occur. That's our universe. And it's convenient for the analysis to consider that fixed. And it's not really a is a without loss of generality. There's some somehow ordered. If two elements are never at the same time in any tree, then decide an arbitrary order.

2:56 That's the formal way to treat to treat that. And then the potential is still um a collection is is a a number for the current state of the world. And the world now consists of all the trees in the family of trees. And we sum essentially the old potential. So, we sum for each tree over all the nodes the rank of that node which is log of the size. Uh this was the notation of the rank will come up again, so let me write this again. That's just an abbreviation. Uh and we also keep um for the elements that are not in any tree we are kind of pretend they're a single tree of their own. Okay?

3:48 Now, another last piece of notation that we need is if an element is not in a tree then uh we need its I guess even if it is in the tree, it makes sense to talk about predecessor and successor. So, X minus and X plus are just the adjacent elements um that are in some tree T. And with that we can state what the update costs of a splay tree are. Uh it's going to be a bunch of cases, but the uh proof will be rather short because they're all following the same kind of pattern. If we do an access then if that element is in the tree, that's literally the access lemma from last time. Yes, we do a search for X and then we splay X up to the root. We've analyzed splay before. And we said the search path is essentially proportional to the cost of splay. The time to spend time spent looking down the search path is within a constant factor of the time we need for splaying. So, the splaying essentially quantifies the cost of this access.

4:53 Um that's not the formulation we had before. We had always three times the rank of X after the after this access minus the rank before. Um And many times in the the analysis yesterday, we've done the same estimate. This is now at the root because it got splayed up. So, this one is at most the is kind of always the same as the actual as the total weight of all the elements in the tree because it's at the root. And the rank of an element um is always at least log of its size log of its weight.

5:45 Where it was previously, we don't know. It might have been a leaf. That's the worst case, in which case it's its rank is just the log of its own weight. If it's higher up in the tree, then it was cheaper, but uh we're kind of ignoring this here.

6:02 That's the simple case that we've had literally last time. If X is not in the tree, then what happens in the search is we follow down some search path. At some point there was some element here. And then some element here, so X would have had to be here, but there is a leaf. So, we don't find X. Always in the in this case there's going to be the two adjacent elements, if you look up, are going to be the predecessor and successor.

6:42 Um And one of them has to be the parent of this leaf. So, in this case this one is X minus. If X would would be here.

6:58 So, we don't know where the search ends. It might end at X minus or it might end at X plus, but one of them is always the one where the search stops and where we detect that X is not in the tree. And then we would still splay that node up. That's I mean, that's my definition of what the search is supposed to do. Um we could in principle have treated the case that X is not in the tree differently, but that's a bad idea. So, uh whenever you do an access the last node you find, whether or not that's the key that you were really looking for, is going to be splayed up to the root. And then you just have the maximum of these of these two where uh you take the larger of of the two as a conservative estimate. All right. Uh join if you're taking two trees and you put them together uh that's how would we do that?

7:54 Um You have these two trees T1 and T2. Now, you're splaying for the maximum element here in T1. That's going to be splayed up to the root. So, after that this X is at the root of T1. There's a T1 prime here left, and this is empty always. Uh and then you can just make T2 take the space of this leaf.

8:38 And then you have joined the two trees. So, the uh the cost you get for that comes from the splay operation. Um What I want to point out is although the notation always says capital W, it actually means a different thing in some of these cases. In the first two cases, it's the weight of it's the total weight tree that we do our access in. Here W is the weight of the new tree, if you like, of the resulting tree. What else can we do? We can do split. Somewhat similar costs. I'm going to explain again where these come from in the proof anyway, so maybe I'm going over these a bit faster now. Uh and finally insert. Uh there X will never be in the tree, so you always have this um situation that you somehow splay at a an adjacent node. And insert in the insert and delete indeed need two steps. And similar for delete, you splay X up, but then you also have to do a join.

9:41 Okay? Uh let's prove these quickly. Uh Some of them already discussed and done much of the work. A was access where the element is in the tree.

10:14 And that is the easiest case literally from the access lemma. Uh so we're analyzing splay trees um for update operations or for the the general operation. I guess access isn't an update.

11:09 And we have this this upper bound I already uh sketched above that we can as last time upper bound this by the the worst possible for this uh previous rank uh the weight of X.

11:31 This picture is for later. Ignore it for now. That was part A when you have an access where X is in the tree then you directly splay at that. For part B when X is not in the tree I think we've already had the explanation in the picture there. I'll just borrow that.

12:04 It's almost the same except that uh splay is happening at one of the two surrounding nodes. And so the maximum of the two costs uh will be an upper bound for the cost of this access. Uh part C was join.

12:37 And we in in a way also discussed already. Um Uh let me copy the picture for that as well. So we have to do a splay on this node X which is the maximum of T1.

13:14 Now uh how much does that cost? Uh Need more space. Uh no. Wrong way around. Um By the access lemma again we can bound the cost of this splay by three times log of the weight of the entire tree T1 minus uh log of the weight of this element that we access X.

14:08 Did I somehow forget the plus one a couple of times? I think I might have. The the statement of the theorem had it. Uh after this we're in this situation that X is the root of this uh of what was formerly T1. So we have X and then T1 prime. Now we do the join which in actual cost is just bending one pointer around. But in terms of the amortized costs it's not for free because we change the potential. So at this point in time we have this T1 prime and empty and we have T2.

14:50 And joining the two trees changes the potential. Uh for those who who came a bit late let me briefly mention again we're working on a slightly different potential now uh because for updates it doesn't make sense to say there's a single tree. Uh we want to do splits and joins and we want to do insertions and deletions so we have to somehow say what the elements have as contribution to the potential. The easiest solution is to have at all times all elements somehow present and they only get added or removed from certain trees and trees can also be combined and split. And so the potential is always the sum over all trees uh plus all the elements that are in none of the trees. And what we sum up is the rank of the elements in the notation from last time. That hasn't really changed. It's just that uh you always have it as the sum over all all trees and elements.

15:52 So that's why that's why previously um what does the change in potential look like? We have previously the potential for these two trees. Let me sloppily write this a bit like this. It's the potential of this modified tree and potential of T2.

16:19 Uh that's the old potential. I should subtract that. And say the result is what we what we get. So this is more of a pictographically mnemonic. It's not a not super formally well defined. Um That's effectively what happens but most of the potentials are the same. All the nodes in T1 prime are still the same. All nodes in T2 are still the same. Their subtree doesn't change. Actually only subtree that changes is access. And so um all that really changes is that we now have the rank of X afterwards. And we have to subtract the rank of X before. And what is that?

17:22 The rank of X afterwards is the entire tree. Um that's what we defined W to be in this case. Um It's the weight of all of T1 plus the weight of all of T2. Whereas up here the weight the capital capital W was the weight of the single tree that we look at. Not the total weight of all the trees in our universe, right? This is important. Uh otherwise the bound would be worse. Uh and what we subtract here well before X was the weight of all of T1, right?

18:10 log The ranks are log. And of course that's at most three times that. And uh why do I do this this weird estimate? We want to combine it with the first cost of the splay. And that cost has the factor three in it. So for those to not nicely go together I'm being a bit more generous on the potential change.

18:54 So now all that's left is adding these two up and then you see that the weight of T1 cancels. All right. This thing plus this thing is going to look fun if you uh have page breaks. >> [snorts] >> And that's what was what was claimed basically.

19:27 If I'm also combining the logs then what is left is the log W. The jumping around get better but what isn't getting better is that sometimes it eats the cursor.

20:02 Okay. Uh that was that was join. The others are a bit less messy. Um and now depending on how we define splits, uh which tree contains X, I think we we cut this edge. I think it was that uh split means the left tree contains everything less or equal X. Uh either way, so the splay cost is precisely our three times log of the weight before the tree and then the weight of X as an upper bound. That's as before.

21:24 Uh we also change the potential, but this time we only decrease it because we make nothing in T2 different, nothing in T1 T1 and T2 different. And X loses some weight. That's negative change in potential, so that's for free.

21:47 Uh what I mean by that is after the splay, right? Splay already changes the potential as well, but that's priced in into this amortized cost.

21:58 So, technically all these operations consist of two steps. There's splay where we analyze the amortized cost actual cost and changing the potential combined. And then there's a second step that we haven't analyzed yet. Here it's the cutting of this one edge that costs us one or or nothing. Um I think this that's the reason why the statements here have big O of one instead of plus one because I'm doing some constant effort to change the pointers.

22:30 Uh now I I guess it it it becomes a question of what is your model of cost. Previously, we just counted rotations. Cutting an edge, I guess technically isn't a rotation. But, okay. So, you just have some actual constant cost, but the change in potential could have a larger contribution. In this case, it's non-negative non-positive. So, uh no contribution really.

22:55 Um this was the case when X is in the tree. We can also split at a value that's not in the tree. The algorithm is the same. We still call splay X. And that'll do whatever it does. Um I think here we want to break ties somewhat consistently, but that's maybe for the algorithm to deal with. I don't think we can we can necessarily choose if we use as a black box. So, what happens is that we will splay at X minus or at X plus. Not really for us to choose.

23:40 One more down for insert. Um that has the respective costs from before. So, uh I didn't even copy it here, but it's it's this cost, which is the same as for the axis when this is not in the tree.

24:02 To be complete, let's write it once. And I guess I could have saved writing log once. That's one. And the other option is the same with X plus.

24:32 And the infamous plus one. That's the cost for splay. Now, I also do this split. Uh but by the same argument, the potential change for that is is non-negative. So, the only thing that changes is that this plus one becomes a a big O of one if you want to count all changes of pointers.

24:52 That's for splits. Now, last bits are insert and delete. uh how does insert work? Well, here's my prepared picture from back then. Um we first splay at X. So, pretending that X is in the tree, this will have the same cost as before. This this a beautiful term. Uh So, let's say we have the cost for splaying at Y, then we can write this a bit more convenient. We we actually call splay X, but what we do has the same cost as splaying at Y if we had known what Y was before. And Y is either X plus or X minus.

25:55 Amortized cost uh after this proof, hopefully you all know this lemma by heart. Don't forget the plus one. Uh and then we have this situation. Now, we make a small change. We put this as the left subtree of X and this as the right subtree of X. The actual cost for this is constant. What is happening to the potential? Uh also, um capital W is defined to be the cost of the final tree. Um so, I have to subtract this.

26:48 Where this is T. Could have defined it either way. Uh here we say weight after the insertion. So, the first splay if you're strict if if W has a large if X has a large weight, this makes a difference. Um because X before was not in the tree, we subtract it. Uh that gives us gives us this tree. Now, we also have to change the potential.

27:18 So, what happens? Um Because it's deprived of its left subtree. Uh whereas X gains weight or um in it it was part of the universe before, but it wasn't part of the tree. So, it gains a lot of weight if you like. Um the new weight of X S prime of X is exactly W, the entire tree because it's the root. >> [snorts] >> Um and before the time X had some weight, which we don't know, but it's going to be I think insert assumes that things are not in a tree before. So, it will be exactly its own weight. Uh in the worst case could be different. So, this this loss of weight we just ignore.

28:34 And for X, we get this is the the sizes, but the potential is the ranks, so you take the log of that. This time um there's no use in upper bounding this with a factor three because the statement here also keeps them separate. The reason is that there's no cancellation. Um for the previous case in in join, we had this cancel, so there's no mention of the total weight of T1 anymore because that was the same positive and negative. Uh here we can't really cancel because all the weights involved are slightly different, so uh best we can do is leave it as is. Okay, final and last case, delete.

29:37 Tempted to bring a keyboard just to do that more efficiently. We splay at X at the usual cost. Not going to write it again. Um then we're left with X and its two subtrees.

30:02 To finish the deletion, we join T1 and T2. And that also has uh the appropriate cost. So, here we really have reduced it to two previous cases. Um What changes is also the the weight of X or the the cost the potential contribution of X. Um but X only loses subtrees, so that's again going to be a negative contribution.

30:38 And so, uh we get uh the cost of splaying X up to the root. And then we get the cost of join where this looks only different because we're just we're doing it after X has been deleted. So, the W here was the previous tree. Um then we X we subtract X when we call join, that's why the W is different. And here we know that the maximum of the left subtree will be X minus, so we inserted that. That's all that happened there.

31:20 Okay. That's the analysis of updates in splay trees. What we've shown now is um almost all that is behind biased search trees, which was the uh the title of the of this chapter. Um this idea indeed is older than splay trees, and splay trees happen to be the maybe most convenient implementation of these, but they're also independently interesting. Um And so, let me define it as if we didn't know what it is. And there's one thing that we still have to do. A biased search tree um is like a binary search tree. We have elements that are ordered, and we have a sorted dictionary operations, but also each element has a weight. And the costs in this in this search tree should always behave as in the access lemma. So, in particular search costs, what this means is search costs should be log of the total weight of the tree divided by the weight of the item that we access.

32:30 Now again, maybe it's worth spending a second on interpreting what that means. Uh we we get to choose the weights. I'll come to that in a second. Um if we set them so that W is one then again, we have this um can well one uh disappears, and we have to choose weights less than one, obviously. If the weights are all one over N uniform, then the N moves back up, and we have log N access times as in a standard binary search tree. Whereas if you have an element that has say half of the weight of the entire tree then this fraction is two. Right? One over a half. And log of two is basically nothing. So, maybe here you uh what you what you can really achieve as running times needs a a constant offset because you can't spend negative or zero time, no matter how big the weight of an element is.

33:28 Uh but the the point is you can get arbitrarily close to essentially uh nothing or constant cost if you have items that are uh taking up a proportional share of the overall weight.

33:45 Technically, you could even have items that have a weight less than one over N, which would mean they might have a higher access time than log N. In principle, that's tolerated. We can always avoid this. Um This is a such a cute standard trick that maybe is worth briefly mentioning even if it has nothing to do with uh what we'll use it for.

34:13 If the weights are much much less than one over N and note that any polynomial is still going to be log N as an upper bound just with a constant in front. But you could have that the weight of some element is exponentially small uh or worse. Like this at least gives a linear bound, which is clearly the worst that can happen in any search tree. You could have even smaller weights, but then the upper bound becomes meaningless. No tree has more than a linear depth.

34:50 Ah, come on. So, such a weight item could be stored at depth N. That's what I'm I wanted to write. Now in in this application of of using biased search trees, we get to choose the weights. We can explicitly set them.

35:18 Uh that's also the last bit that we still have to do with splay trees. This uh in this abstraction, the weights are part of the operations for the data structures. So, you can explicitly change the weight of an item and tell the data structure that from now on, you have to treat this element as an important one. Please keep it close to the root because I say so. Now of course, if you increase the weight of many items, the total W also reacts to that. So, you you can't cheat that way. But you can make the tree skewed or biased towards certain elements. If you can choose the weights, you can always avoid having a tree that's more than log N.

36:19 Namely the old weight and one over N and take the arithmetic mean. Uh then you can work out that the depth is at most log plus one. Uh but you also if an element had huge weight before it's still going to have huge weight afterwards divided by two, so it maybe moves one level down. But all levels are bounded by log N. So, you can even though it may look like this is potentially worse than the balanced search tree, you can always make it never worse but a plus one. All right.

37:02 As I mentioned, biased search tree, the idea of this of this of a data structure where you have elements that you maintain dynamically, insertions, deletions, and so on, and they also have weights that you can change. This predates splay trees, and there were other solutions uh in particular um a variant of height balanced trees that achieve this um via uh intricate invariants that are a pain to uh maintain, but uh you it's in principle doable. And then you even get all the times as a worst-case time, not just amortized. Splay trees, everything has to be amortized. It's always talking about a sequence of operations.

37:46 Uh this may be something we'll look at um in the exercises. Uh you can make some of our randomized data structures have this um guarantee for biased search times with relatively little effort as well.

38:05 So, what's left is to analyze the weight change operation because that didn't pop up in splay trees so far. And it sounds like it's potentially a problem because the splay trees don't know what to do with these weight changes. The thing is, you also just do nothing. The operation does zero actual cost. But it changes the potential. Okay? So, uh Let let's prove this this lemma is not much to do. Uh there's two cases um depending on whether the weight increases or not. If you decrease the weight then basically the uh uh weight of all the other items stays the same. Um we only allow weight changes at the root. This is crucial, so I should have stressed this more. Sorry. Um I'm only changing the weight of the item at the root, which means all the elements in further subtrees down don't change in their size. Now you may wonder, "Oh, but capital W changes, right?"

39:10 That's irrelevant though for the potential. This comes into the time for operations. So, um whenever you analyze operations in biased search trees, you have to think about the current total weight divided by the current weight of an item. And that's whatever it is. You get to decide what to put for weights. If you bump up the total weights, total W increases, and so your times may get worse. Um What we analyze is just one operation after the other. And in tree we're almost there. All the operations satisfy this even if you don't know the weights. Uh but if you want to have an explicit way to say I'm changing the weight now, then the analysis has to reflect that. And it can do that if you only change the weight of the root. If you decrease that, by definition the potential only goes down.

40:11 Uh it could be strictly less than zero actually. Uh so it's for free uh in that sense. And also the actual cost of the operation, again, this is the no-op, right? It does nothing. Um part A, we have to do a bit because the weight of the root changes. But how does it change? Well, I have the new rank of the root, which is log of W plus delta, and I subtract the old rank of the root, which is just log W. Uh and that is this if you rewrite it. That's all, right?

40:49 So it's this divided by this and you can cancel one W. If you want weight changes on arbitrary item as the biased search trees wanted it, it seems legitimate since we're doing a splay tree to first splay. And then it's at the root and then you can do these operations. So if you want a general operation for change weight, you just have to add the cost of splaying. Um but I think that's very fair game. Given that splay trees splay everything to the root, why not here as well?