Video 2-4: Splay Tree Analysis prelude

0:01 So, next next step is to analyze this and show what we've observed in the tiny example, that things seem to do well and the [clears throat] tree seems to be balanced. Uh let's try to prove that and actually something much stronger. Not just balanced. Uh all the operations we've seen insert and deletions, split, join, find, they all follow a search path through the tree and then splay up some node. It may be the one that we search or the inserted the new node or it may be the predecessor or successor of that node. But it will always be a single uh identified key that we then splay up to the root. Uh okay, fair enough. For delete, we need to do it twice. Delete is a bit more expensive in that sense. Uh so, splay um is here technically just the part where I'm I'm giving a pointer to some arbitrary node in the tree and then I'm I'm walking back up.

1:02 Uh I think here I'm pretending that we have parent pointers. Of course, if you implement this, you don't need parent pointers. You will always do a a recursive descent down the search path. So, you could just the the recursive ascent could be used to do the splay. Uh of course, you can also do this this trick that you can only really do with void pointers in C or so that you reverse the pointers. Uh instead of having parent pointers point down, you twist them so that it points up. Uh >> [snorts] >> um or you keep a an explicit stack. So, the main the main cost is the length of the search path or specifically for splay, the number of rotations that we do. They're within a constant factor of each other. Splay is doing one rotation every two levels. Uh so, um the key thing is how deep do you have to search down or how many rotations do you have to do on a pons playing upwards?

2:06 Uh so, it's convenient to say our cost is essentially the number of rotations. That's what we'll do. Um you've also seen in the example, at least if I'm inserting elements in sorted order, then the tree could be completely degenerate, and a single operation could be linear cost. So, all we can possibly hope for is an amortized bound where over a sequence of many accesses or many operations, many splays, uh the average cost per splay is cheap. And nothing else is even thinkable. Um but, we'll get this. Uh and for that, um we'll we'll do uh a potential function approach. Um okay, this this needs notation that um I'm going to introduce next time. Uh essentially, the the goal of potential analysis, mm let me maybe write this here.

3:17 Uh has everyone seen some amortized analysis of some data structures or algorithms? Should I briefly recap this? That's maybe um just about doable in the 5 minutes. Um so, the idea is always that we have a sequence of operations.

3:45 And we only analyze the total cost of the sequence. Then what we claim, what we say amortized cost is is the average per operation if you take the total cost for a sequence and divide by the length of the sequence. But that's a fictitious quantity. It's It's just some average. Uh the analysis really always has operations. So, say operation one, operation two, operation three, and so on up to operation M. I'm doing M operations. I reserve N for the size of the data structure. These could be different. Now, uh the actual cost of operation, This is the quantity I really uh care about in a way, but they can be large and small over the course of the operations. So, let's say this is a bit chaotic.

4:53 But what we care about is the sum from one to M of these actual costs. That's what we care about. Now, this is hard to analyze. So, instead um we try to bound the amortized costs An amortized, that's just a definition. I assume Okay, I'll I'll come say that in a bit.

5:37 That's the actual cost plus some change in a potential. And this potential is just some function that that maps the state of the data structure to some number. The In principle, it can be even negative. That's fine. And so the idea is um that hopefully we can find some upper bound.

6:29 Maybe uh depending on the size of the data structure, but not the number of operations. That's the hope. That's why I put it in exclamation mark. We have to find a way so that this potential makes this magically happen. So in a way when an operation is expensive, I have to compensate that with a drop in potential for the overall bound to hold. Uh what what's the point of of this setup? Well, that's a telescoping sum at the end. So if I sum up all these amortized costs, uh the change in potential, I think I should rewrite as it's the potential after um Need another line here.

7:28 is the potential, say, after operation i. Uh phi zero is the initial potential. Then this delta phi i, the change in potential is phi i minus phi i minus one. I have I have some potential after this operation. I had a potential before this operation. I'm taking the difference.

7:55 That's the that's the part I'm inserting into this sum. So, i from one to m the actual cost plus the potential afterwards minus the potential before.

8:18 Now, this is a telescoping sum, right? I have phi i, then in the next step I'm subtracting it again. So, what's left is the actual cost of all the operations.

8:33 Plus then the last potential phi m is never subtracted. That's left. And the the zero potential potential is never added. That's left negative. And from that, I'm rearranging. What I actually cared about is the actual cost of all the operations. And so, this is the total of the amortized costs >> [snorts] >> Now, so far I've just rearranged terms and not gained anything. But, the point is that we assume that every every ai is individually bounded by some upper bound b of n.

9:28 So, this one is less than b of n. So, this overall quantity is less than m times b of n. Uh but, I have this initial and final potential to deal with.

9:43 And this last fact is why I wanted to write this down again because that's what we need next time. If you look at this, the total cost of all the operations is m times some upper bound. So, the average cost per operation is just this b of n. If I can somehow make these initial and final potential be small, go way upper bound them somehow. Uh, this is this depends on what the potential is. So, we have to insert the actual numbers to make sense of that part. But, that's the the general template that we always follow in in amortized analysis if you're using a potential function. Uh, and that's what we'll we'll use for splay trees as well.

10:29 Okay. And then, uh, if you want to think about this already, you can try to come up with something. We need something so that when splay uses k rotations, the difference in potential bef- uh, after minus before should essentially eat up this this number of rotations. That's weird. And then, be upper bounded by some something we'll come to.