Video 2-6: Splay Tree Analysis: Adaptive Properties

0:04 The true power of splay trees comes only to light when you look at different weights. And for a first non-trivial result, even though it matches something that move to root could do, so maybe we're also not so shocked that this works. Uh let's look at some some sequence of accesses and look at how often each key is is requested or each node is requested. So, I'm calling PI the relative frequency of this this ith node. Uh this this absolute value with subscript means count the occurrences of I. Um then I I can treat this as if it came from a distribution where I have access frequencies. So, I'm I'm in the realm of this IID model that we studied in move to root at the beginning of this unit. And it turns out if you just apply a splay tree and uh use this access sequence, the total cost can be bound in essentially the same with the essentially same upper bound, at least up to constant factors.

1:10 I'm paying M times and then this entropy plus one, where the entropy is defined via the probabilities from from this uh relative frequencies of this distribution.

1:22 And that is uh again, remember that this is essentially the result that move to root got. So, up to constant factors, that's optimal for this kind of um access sequence.

1:51 Move to root. >> Now, somewhat somewhat shockingly, all we have to do for this is set the weights to these probabilities. Now, let me just say weight of I uh to PI. These already sum to one because they're probabilities or relative frequencies. They're already scaled. Uh Capital W is again one. Now, um I don't think I have this copied anymore. This is the corollary we want to keep.

3:02 is big O of And what is this now? Log W again is one. And then I have as the size PI. Uh at least I can can upper bound it by this. And so that's uh the access probability of this element. If you sum this over This is for um the amortized cost to access element I.

3:43 Now, summing this up over the entire sequence will give you this contribution exactly XI uh prime times observing this access xi The way I chose these these probabilities, right? Um I'll make sure that this exactly matches. So, I can sum over the elements of the universe, say from one up to n. Then I'll have x i times as often as I get this access, this upper bound.

4:44 Yeah, I know. It's horrible. How can you build up tension? Technology gets in the way of the the fun. Big O of log 1 over the probability.

5:00 I'll have to pull out this big O because that's the the only thing we get from the lemma. I could have maybe put the factor three.

5:19 Now, a standard trick. I'm pulling out um a factor m. And then inside, I get this xi divided m, which is my pi. I'm summing i from one to n again. And and that thing is precisely the entropy. Okay?

5:47 Now again, what's missing is the potential difference. And Okay, I don't have that one here, but it's the same quantity as you'll remember. Is this log of big W divided the weight of this element. This is the same bound we've used for upper bounding this with one over PI. So, I get another contribution of n times the entropy.

6:21 Um get Yeah, for every node in the tree, we get this contribution. And here I'm using that uh my access sequence touches every node at least once. So, my uh my m here is at least n. That also makes these PIs well defined. But, it means here that uh I can upper bound this by my m times h.

7:41 Now, this is a a much stronger statement already. because like move to root we achieve this static optimality which is that's the cost that we get if the tree is fixed in advance but knowing the probabilities. Same as same as move to root where we discussed this a bit more. There's more. Um you can also have a theorem who now where the the cost depends on another choice that you can arbitrarily make. You can fix any node in in the tree called F here, the finger, and now you measure the cost of accessing something as the distance from from this finger. Precisely what this means is the total access sequence cost is some base terms that come from again the potential difference, but then the key term all of this if M is much much larger than N, this is not so big and this is linear. The key contribution comes from from this part.

8:47 And there the cost is log of the difference in rank between those two. Which means if there's one element that you may not access itself all the time, but all the accesses are close to that element in value then the total access time is also cheap. Okay. Uh again the proof is essentially to just pick the right weights. Uh this time we have to be a bit more clever. We have to somehow get the elements to cost that. Now it may seem tempting that we should just say uh the the weights is this difference to F. So that could be a first attempt.

9:50 >> Maybe plus one to not have zeros. Uh Sorry, one over this. One over this. We want the elements to be cheap if they're close and expensive uh if they're far away and for the ex- for being expensive you have to give something low weight. Uh Does anyone see a problem with this choice of weights?

10:20 It's not clear if it's if it can't be savage salvage somehow. Uh but one one nuisance is that if you sum these up um uh it's a bit unclear what this sum of weights would be. It's somehow some some harmonic number, so it would grow with n. And it turns out it's much more convenient to put instead as weights the same thing but squared.

10:58 So, 1 plus this difference squared. Uh let me put it as a fraction again. Crossed out the two. Uh Normally, what we do with weights is take logs. And so, this this power of two doesn't really make a difference. But now if I sum up all the weights uh this is actually also tricky because uh this is related to the Basel problem of summing up the one over n squareds, but you can upper bound it by some constant.

11:43 So, that's convenient. Um then we can still in within the big O keep W as one, even though it's it's a constant larger than one. And the amortized access for each uh query or for each splay again, um is log of total weight over the weight of the element we access. And now if you plug in this W is constant, this is a one over, so uh it we're left with log of one over the distance.

12:34 Ah, come on. What was Yeah, it's horrible. Good that it's loading so slowly. Ah, okay, now I went too far. And so uh here the the cost of an operation now depends on the distance to this specific magic item F that The thing is we could choose F and the splay tree doesn't know about this choice. It'll just have to deal with whatever we use. It's just a function of the analysis. So, you could immediately say I'm I'm getting the cost of this thing minimizing over all choices for F. Same thing. Uh I'll I'll skip the computation of uh this this offset is the same as before the the initial and final potential.

13:31 Now, this is uh this is the static finger theorem. There's a a version where F is not the current node, but the last one that you accessed. Uh just for where the name comes from.

13:58 The previous one you accessed. It turns out splay trees satisfy that as well. So, the same bound where uh you take the previous element instead of this fixed finger, splay trees satisfy this, but that is a much harder proof. And uh one of one of those papers that few people feel they understood.

14:20 This makes somehow it feels more intuitive, right? Yeah, in a way. That's true. You should be Yeah, this is much more intuitive. Uh but somehow much harder to prove. Or well, who knows? Maybe there is a simpler proof, but all we know, not so simple. Yeah, please find one. Uh this is the last one I think is um is the coolest. It's the most annoying proof, but is this close in a way to um close in spirit to dynamic finger. That's the working set theorem. So, you will need some um notation. Uh T of J for some item J or some some some access to a I think T uh the J serves as uh depending on where it's used, it serves as either the value or the index in the sequence of accesses. Here, it's the index in the sequence of accesses. And T of J is since you've previously touched the same element, how many other elements have you accessed?

15:22 That's called the working set because it's in a way how many things do you have to keep in your working memory until you need that thing again. Um if you think about it, this is connected to a cache, right? If you keep the least the least recently used element is evicted, you keep elements in cache in the hope that you use the same elements again. Then this T of J is precisely how likely is it that you're still keeping that something in cache? Well, how many things have you touched since it was last touched? Or in other words, um if you maintain a dynamic list with move to front, then T of J would be the position of the current access in that list. That's all all somehow uh connected. And the bound says, yeah, you get this up to this usual uh for long sequence sequences uh insignificant contribution in log of the number of things.

16:22 So, as if the splay tree optimally optimally makes use of the exponential fanout to keep the hot items near the root. Uh well, it kind of it does. I mean, the thing is as if it knew, but yeah. Now, this is more tricky. If you think about how do would how would we assign weights here?

16:50 We have to assign weights to use the previous theory. And we will assign weights. Um initially, we assign weights somewhat similar to um this we'll use a similar trick as before. We want something like one over TJ or so, but that may not sum to one. So, instead, we use the squared again.

17:21 So, we have weight one one Oh, two squared is one quarter. That's a four. One ninth and so on. in the order that they are first accessed. This is for the initial one.

17:59 the total the sum of weights is bounded by some constant. Or let me write it the computer science way. And what I By By first access, I mean the one that is accessed uh the soonest in the first access gets the one and so on. So, um I think this is what for for T of J uh the second part I never spoke about, right? The first um access is kind of at at time zero, you touch every element. So, from from that, you already get the right amortized cost for the first access. The element J is uh accessed when J minus one elements are touched before it, and it has weight one over J squared. So, log of that weight, log of one over the weight. So, first first access um has amortized cost order log W over the weight, which here is log one over T of J um one over one over T of J squared.

19:34 So, order log TJ. That's for the first access, but now we have to change the weights because this would not be the right thing to do for the second access.

20:00 >> [snorts] >> Still there. Didn't go too far. So, what we'll do is after each access, we uh redistribute weights a bit so that the element that was just accessed gets the weight one. Um And the elements that now have one element further that it was accessed are bumped up one position in that sequence. So, we always keep the items um permuted.

20:48 The the weights will always be a permutation of this same set of weights that we started with. So, we uh we can't exactly guarantee that the items have precisely this 1 over TJ squared. Um because there might be ties, etc. But we can we can bound it by that. So we we maintain the weights in by TJ. If the next access were for J, what is the number of things that we have seen in between? Uh sort the items by that and assign the weights based on that.

21:59 So in a way um the same same thing is the accessed items the accessed item gets one. And every item that previously had the Every item previously If you previously had a weight 1 over K squared, you're now put to 1 over uh K squared plus 1 if K is less than uh if if that weight is less than the old weight of um the accessed item. Uh I'm running out of notation for this, right?

22:59 So the old weight of this accessed item Anyway, if if you were on uh it's not the search path. Can't really say. So, if it pre- if an item had previously larger weight than the weight the element we now access, then its new weight is 1 over k + 1 squared.

23:39 So, we keep a permutation of the weights and you essentially maintain the invariant that it's sorted. And so, each subsequent access will also be bounded by log of TJ. And so, again, you get this uh this overall sum. And what's missing is the the change the drop in potential. Okay, let's let's leave it with that.

24:08 And let me finish the part on splay trees with a bit of a comment on why potentially splay is a good rule, but also maybe why it's not the only option that we have to do this. Uh this there's a a cool paper from a while ago um that has a different look at what splay does to the tree globally that I find is is very enlightening. Um first of all, let's uh fo- let's ignore the the right part for a second and think about move to root again. Remember move to root? It just single rotations to bring the current element to the root and uh it didn't care too much about the rest of the tree. Now, you can also interpret the same statement uh as saying that's this low lowest part here, we maintain a treap the overall tree is a treap and the priorities are the access times of elements or when I access an element again, when I access an element now, I'm bump up its priority to be the new maximum so that it becomes the root of the treap.

25:22 And that is it. This is all that move to root does. It doesn't meddle with any of the other priorities, which means if there's a search path down to some element S, what you're doing is shooting this element up in priorities, but all the other elements keep their respective priority order and will then in this case, the search path will always form these two inwards joining Well, at the time we called the those the spines of the tree. The inward spines. Now, this is what move to root does and that also kind of shows you why it doesn't work globally because it leaves too much of the tree unchanged. And you worked this out in the next exercise sheet, right? Uh or you will work this out in the next exercise sheet. Splay on top can be shown to do exactly this thing. I don't know if you've read the text by now. Uh whenever you have an even element on So, you you start numbering these with one as the first node above this uh above the the access node. Whenever you have a node that is even indexed from the bottom, where also the one smaller was on the same side, then splay decides that from this this inward thing here, I'm going to demote four to be lower than three so that it becomes the right child in this case or the left child on the other side.

26:59 So here again eight and six are such that they're even and the one smaller index is on the same side of the search path. So those are the guys that end up down here. This is of course the zig-zig case. Right? This was precisely what happens when I have from the parent up two edges in the same direction, then I do this special treatment which exactly was the difference from move to root. So all of this is kind of maybe not entirely surprising. Uh but I think the description makes this much more explicit and visible Now the real point of this paper was to ask the question, what can we do instead of the exact splay rules to get something that works for all the proofs that I've shown you? All of the proofs apart from choosing clever weights all that was needed is is this corollary or rather the access lemma all the way back.

27:57 So what do you need to have this access lemma? Well, we don't really know. There may be more options. Uh what they showed is that at least there's a class of algorithms um where there are some some necessary conditions and um sufficient conditions.

28:18 Uh if what you do to the search path in restructuring the tree satisfies some properties, then the access lemma holds and splay is only as one specific example of doing that and there is others that are maybe also possible. I don't think they're more natural, but they're also possible. Uh in particular, what what you need uh is these things. So uh first one means um if you uh Uh this is a bit short on the slides here. Uh what it means in the reconfigured picture here is uh on the right side, you can only go uh down to the right a constant number of steps. On the left side, you can only go to the left a constant number of steps. In this example, you have two on the right, that's the right depth, and you have three on the left, that's why you have this three here. What's What does splay get on this?

29:33 If you look at the picture here, we start with this, that's what what's left after the move to root, and then we do this the the simulation of the zigzag rule, which only ever creates one thing that hangs off. So, by depth, I mean only the nodes that were on the search path. They all have their subtrees hanging off them, but these are ignored. Uh depth only looks at the search path. So, here splay tree would have two for these left and right depth. Um and the second is that if you start out with something that has so many zigzags, so one, two, three, four in this case, that's the zigzags. Uh and the number of leaves that you form on the right-hand side, again only looking at what it was on the search path, then these together shouldn't be much more than the entire path is long. I'm not sure these uh rules are super intuitive, but that is sufficient to prove the access lemma and hence all the good statements we've seen today.

30:39 Okay, if you want to read more about this, then you have to check out the papers. Uh I thought this is just At least this part if you if you ever forget what splay tree does or want to see on a on a bigger picture, this is much more memorable than uh going through the rotations.