Video 2-5: Splay Tree Analysis: Access Lemma

0:02 Where we left off last time was how to to analyze these operations because at first even with this vague intuition that somehow you tend to move up subtrees that you've touched, there's no clear reason why this should be any good. Unless you've proven it. Yes, [laughter] so let's do that. The cost model is rotations, what we established last time already. Um because we're essentially splaying all the way up to the root whenever we touch something, all the cost of all the operations are proportional to the number of rotations in these splay calls. So up to constant factors, that's the same. And counting rotations is a convenient simple discrete metric we can easily specify what happens. And also we convinced ourselves in the worst case I could create potentially very unbalanced trees even though I I have to uh try hard a bit, but we've seen we've played around with the animation a bit. And in this case there's no way to prevent a linear time for some operations if you're far down in the tree.

1:16 But it turns out if you do a lot of operations over time, the average cost for each operation can never be as high. And the way to prove that is amortized analysis, so um the general setup we've covered last time, not going to go over the calculation again. But I want to recap that we have a potential function that somehow maps the state of the data structure to a number such that when I take the actual cost of any operation and I add the change in potential, so the potential I have after minus the potential I had prior to the operation then this somehow should cancel out the key bad behavior of individual operations. So, I I find an upper bound for this amortized cost that somehow is how I want it to be. Say, in our case, it should at at least be logarithmic as the operations for a binary search tree. And in general, it's some function of n.

2:18 From there, um the usual way to rewrite this is so that the total cost of the operation sequence is m times this upper bound, m for the number of operations in the access sequence. And then I have this slightly annoying correction where um I'm potentially adding the initial potential. So, we can't completely forget about the potential. Uh but most of the time, this is something we can easily bound, and the key contribution comes from the amortized cost of each operation. Now, how does that apply to splay itself? Uh we've uh already covered the first part. The potential here is such that um whenever we do a splay operation that does k rotations, so it's roughly uh going down a path of length k or two times k, then the change in potential should eat up this k so that this upper bound, what I called b of n, uh should take this form. Now, here notice it's a bit more complicated. It's not just a function of n as the size of the data structure.

3:27 We'll look a bit closer at what this means. Uh here it's uh specifically about this node x. And I haven't told you what the ranks are, so this is kind of uh so far just some gibberish. The point is there's no k, right? Uh the change in potential somehow eats up what the number of rotations was and uh replaces it upper bounded by some mysterious thing.

4:05 The splay tree potential is uh a generic thing that if you just want log n time for operation, you could simplify, but we're going to do one proof that gives us several more general statements. And the proof is essentially the same calculation, so we'll start with the general version, which is a bit more general than what you would need for the simplest result. But bear with me for a sec. So, each node in the splay tree uh gets a weight, which is some some uh I guess non-negative function, some some non-negative number.

4:43 Then every node, which potentially sits uh somewhere in the tree as the root of some subtree, gets as its size s of x the sum of all the weights of nodes in its subtree, including itself. So, this uh in particular is always going to be at least the weight of x itself.

5:09 Now, uh the ranks that popped up earlier, these are the logarithm of the sizes. So, essentially proportional to this or well, not proportional. They're monotonically grow with the size. But we need to take the logs for technical reasons. I don't know. It's always a cheap excuse, but that's the way it works. Uh the potential overall then is the sum of the ranks over all the nodes in the tree. Okay?

5:39 Uh a bit of notation that we'll use in the analysis is that remember this this potential uh or clearly I mean it it depends on what the tree looks like because the size of a node depends on its subtree. So, when you change the tree shape, uh the sizes of some nodes might change, and hence also the potential. So, the whole potential is a function of the current shape of the tree. So, it'll change over time, and we'll use the phi, r, s, etc. for before an operation, and the version with a prime for the new version of the same quantity after some operation.

6:23 And with that, we're going to prove uh the key lemma that all the analysis of splay trees to follow builds on. That's the access lemma. That's just a reminder of what splay was because we will have to deal separately with the three cases, unfortunately. That's the annoying bit. But, the rest of the proof is relatively clean. That's the potential, just as a reminder. In each of the cases, um I guess I'm I'm uh misquoting a bit. My access lemma is a a single rotation. I'll do an another step. Um if I'm at some point in the process of splaying, I'm in one of these three cases, and I do a single rotation, a single step. It might be this double rotation, but uh uh we do a single step, and the amortized cost of that step is always upper bounded by this three times the difference in ranks. So, there's a node x at which we do I think I should state somewhere in the lemma that we rotate at at x, right? So, there's a But, that's what I mean. Um here in the code, you see there's always some current node x, and then I'm in one of these three cases. That's what's meant.

7:45 And the amortized cost for that is upper bounded as given here. Um Before I go to the proof, uh note that from this you almost directly get a bound of the entire splay operation. The lemma itself said a single step in splay has this and that cost. And because the uh the bound is such a telescoping sum where I'm always adding the new rank of that of the single node that I'm moving up. Right? The upper bound here doesn't involve anything else about the tree. We will we'll have to see in the proof where this comes from. So, I'm always adding the new rank and subtracting the old one. If I do this over a sequence of operation, the current new will become the next old. So, you always add and subtract these. So, in the end you're left with the uh the rank of the previous root of the tree and the new on the node where you start splaying.

8:57 And you just get the the total distance the rank difference between those nodes that are initially far apart. And you can upper bound this um by inserting what the ranks are and using the log ones. These are the the second equation is just inserting what ranks were defined like. The first part is uh is the interesting statement. Okay. But let's first prove this one rotation at a time.

9:32 Uh the first case um is the the zig case where already at the root, one step below the root, and we do a single rotation. Right? So, the actual costs are one. That's the single rotation we do.

9:52 And we do uh we get an update in the potential. New potential minus old potential. Now, remember the potential technically is the sum over all these nodes in the entire tree. However, most of the nodes in the tree don't change. In particular, any node, say somewhere down here in T2, any node set here, its subtree is not changed. So, its weight is not changed, its size is not is not changed, and its rank is not changed. So, it will contribute the same quantity to both of these terms, and so they just cancel each other out. The only nodes where the rank really changes are those that are outside of these subtrees T1, T2, T3.

10:48 And this is the entire tree. Remember, we only do this case if we're if Y is the root. So, specifically, what do we have? Um there's and the new rank of Y minus the old ranks.

11:32 Now, the old rank of Y and the new rank of A, these are the same because they're the entire tree. So, uh new rank of A is the same as old rank of Y. So, these two cancel out.

11:54 And the new rank of Should have changed notation with the thing. can't be more than the entire tree, so we can upper bound it by rank of A.

12:47 And in my picture um A is the node that is accessed. So, I used the notation from the pictures, but here it's called X. All right, this is uh the element that's moved up. Um Let's just say these are these are the same nodes. Uh luckily, X doesn't occur in the picture. Uh in this case anyways. Uh and so, um that's of course upper bounded by three times that difference. We've actually shown something stronger or tighter, but that doesn't matter.

13:29 Now for the next one, we have to work a little harder. The 6A case was this one. Uh less confusing. So, the 6A case was the case where parents are sloped in the same direction.

13:42 And let's pretend that uh they're called XYZ this way up. So, what what is what is the actual cost? Um we're counting the double rotation as two single rotations because you have to rotate two edges. And of course again, we have the same uh new potential minus old potential. But by the same argument as before, any node that is in any of these four subtrees is unchanged in its subtree, hence its size, hence its rank. So, the only ranks that that can possibly change are the nodes that are on this on this uh rotated path. So, the three that we have there. Also note, this time we're not at the top of the tree. There's more rotations coming up. Uh but any nodes that are further up, this may continue, their subtree size also doesn't change. So, also their ranks are unaffected. Right?

14:46 Okay. Then we have new ranks for X, Y, and Z. Minus the old ones. Uh luckily, a few things will simplify. For example, um what was previously Z is now X, and they cancel. So, the new X and the old Z, these are equal and so cancel out or equal apart from the minus. Um then we use the subtree and the new rank of X is greater equal the new rank of Y.

15:48 And similarly, the old rank of Y is larger than the old rank of X because it's higher up in the tree. So, I've used this one here to get an upper bound and replace the new rank of Y by the new rank of X.

16:28 And now we'd like to have that this is at most the three times this rank difference. Which is the same as that minus R prime of Z. That's why it didn't make sense.

16:57 Is greater equal to then this claims it follows. >> [snorts] >> Um that I can take the two here, upper bound that with this part, then the two R prime and the R prime of X combine into the three R prime of X. I have one R prime and two Sorry, two R of X and two and one R of X that combined into the minus three R of X. And the R prime of Z then cancels. Okay? So, that that part works. Now, uh since log is a convex function, if you take log of X and log of Y, where the two are summing to most one, at 1/2. And then this is uh less than minus two.

18:22 What I mean uh and that is is equal minus two and it's always less than minus two. >> [snorts] >> Now, if you um if you look at this here, the negative of this thing is R of X plus R prime of Z minus two R prime of X. Now, we can rewrite log of S of X divided one of those two plus log of S prime of Z divided S prime of X.

19:09 And no matter what values these take, we know this is at most minus two. Because here Note that these are two fractions with the same denominator. And now we need the picture again. I'm looking in S of S prime of X X is the root afterwards. So that's the size of the entire tree. Does that fit here? Yep.

19:44 S prime of X is the entire tree. The entire subtree. S of X the previous one are these two subtrees. And S prime of Z are the other two subtrees. So these are These are disjoint. Right? Here X and this These two subtrees are here and These are here.

20:21 I think I don't have a notation for the subtree before and after. Uh-uh. Subtree of X before and Z after are disjoint. Which means that these two quantities add up to at most S prime of X.

20:51 Okay. With that we're actually done. If you take this inequality this part up to the minus two, multiply by minus two, you have this inequality. And from that inequality we follow this one.

21:26 Okay. So, all it all it took was uh observing um relations between subtrees and this one crucial trick with the concavity of log. Um then you get this upper bound. Um the third case is the the zigzag case, uh which is um sim- similar in in spirit. So, again, the total cost the actual cost is two. The change in potential is what we add. Only the top nodes can change.

22:11 Amortized cost is two plus the ranks of the nodes after. Uh as before, um I'll get the picture with the proper notation if this time that works.

22:42 No, okay. So, both the sources I took it from and my own notes are inconsistent. Let me try to work it out by changing the picture instead.

22:57 So, um access the root afterwards. Previously, X was here. And we have, say, Y and Z on the path here. And we rotate it to have X here, Z here, Y here.

23:30 So, the previous rank of Z is the new rank of X. These two cancel out. Same Same as before. And also the rank of X is at most the rank of Y because it's in a subtree.

24:16 So, what was left? These two are the same. Here, I have uh replaced R of Y R of X. Subtracting something smaller. Now, the claim is this is at most two times the rank difference.

24:48 And so, again, similar kind of approach. Uh We try to show this lovely quantity minus R prime of Z is greater or equal to And this is essentially the same trick as above. Um What we need again is that in the new tree X R prime of X is the entire tree. Whereas um Z and Y in the new tree have disjoint subtrees.

25:56 So S prime of Y S prime of Z are less or equal S prime of X. So we apply the the same trick as above, right? Um plus S prime of Z divided S prime of X This will again be less than -2 from the same reasoning as above. And that's the negative of what's on this side. Uh so the same same trick as above uh gives the result again. Now of course uh two is less than three, so you can upper bound this by the same quantity three times the rank difference. Which also shows in terms of the amortized cost, the the tight case is always this zig-zig case. The other two, you could have obtained a better upper bound.

27:06 Um but it's in how we use this lemma further on uh not really helpful. Okay. Sorry for the notation mess. What we learn from this, again, let me reproduce the theorem maybe on the next slide so that this corollary is a bit clearer.

27:35 No. Uh let's fix it that way. So, you can do an individual rotation and upper bound it by three times the rank difference, maybe plus one for the last one. But over a sequence over one entire splay operation, you're only going to have this part A uh at most once at the end. And so the majority is is zig-zig and zig-zag cases where you can always upper bound things by three times the rank difference. And so uh if you start somewhere deep in the tree with your node X, and initially this was the root of the tree, then all one one thing is that afterwards X is at the root and the rest of the tree looks whatever, a bit hard to say. We will have worked X all the way up. And each time the cost for that is just bounded by the new rank of X minus the old rank of X, irrespective of any other nodes' ranks.

28:38 And over the sequence of a whole of such rotations, uh you're eventually getting um the uh new rank of X, which was is the rank of the previous root in terms of the old tree minus the old rank of X, which the first one you started with that doesn't cancel is the very first in X's original position. So, another way to say this this here is is also the new rank of X, right?

29:16 Because X is at the end of the whole procedure is the root. But, if you want to express it in terms of the original tree, uh you need you need the original tree's root, uh whichever one it is. All right.

29:38 So, with that we have this slightly awkward corollary of a cost of a single splay operation. Uh maybe it's not super intuitive what that means or if that is a good bound to have.

29:54 Um one technical requirement in the whole analysis was that any kind of sequence of operations has to deal with this change in potential between before the entire operation and then the potential at the end. And so, you can once for all upper bound this by simply observing two things. Uh the potential is never more than n times, where n the number of nodes, times the the rank of the root, which is log of W, where W is the sum of all the weights in the tree. That's just a an upper bound for the potential that is never even achieved. You can never have this. But, every node contributes the rank of its subtree, and that's never going to be more than the entire tree. That's all that this balance says.

30:51 On the other hand, every node also has at least its own weight as its subtree size. So, summing up the log of the weight of a single node, that's a lower bound for the potential function.

31:04 And so, just applying these to before and after gives you this upper bound for the change in potential. Namely, summing over all nodes in the tree W the capital W divided by the the weight of a single node.

31:23 This again, how you use this depends on what the weights are. So, the following sequence of theorems shows by cleverly choosing the weights in this analysis in the potential, you get different interesting statements.

31:43 And for the first one, um we choose essentially a uniform weight. So, the total weight summing up all all the weights gives exactly one.

32:15 Probably good to keep that. Uh The amortized cost of any splay operation, and remember that means the amortized cost of any operation up to constant factors, is big O of log of this thing. But, what is that?

32:51 >> Now, uh S of T, the weight of the root, that's total W, that's one. And the weight of a an individual node was one over N.

33:21 Now, you might be tempted to say, "Ah, great. Then the sequence of M operations always takes M log N." Which is kind of right. Uh you just need to add this contribution from the potential difference. Right? So, this is the cost per operation in the sequence. But the the actual overall cost for the sequence is always the sum of these two things, the the total cost of sequence of operations.

33:57 Is M times this amortized cost plus the change in potential. The potential at the end minus potential at the beginning. So, we always need this this second lemma to upper bound this this uh difference. And here again, W is one, this is one over N. So, uh that is bounded by N log N.

34:28 With that, we get this the balance theorem. Okay. So, straight trees are just as good as any uh normal balanced search tree. Never worse, I would say.