Harvard University · 1:26:46 · https://www.youtube.com/watch?v=LbX51mey3vo
0:00 describe is it okay so uh I think I'm gonna get started today we're going to talk about spllay trees is going to be another example of amortized analysis again for a data structure so display trees I I think I asked this before but I can't remember how many people have seen display trees before okay some number okay so display trees Uh these are due to Slater and Targen.
0:36 I think it's 85. Okay. Um and this problem we have so it's comparison based data structure and we support two operations. We support insert. Okay. So insert a key K as well as uh find. So let's say I mean uh insert a insert an item which is a key together with a value and find with a key uh returns the associated value.
1:35 You could also imagine delete. So it deletes uh deletes item with key K. And this uh inserts a new item with uh key K and value V. Okay. Right. So, you know, if we weren't a comparison based data structure, how would we solve this problem? Yeah, this is the dictionary problem.
2:22 So, we could use hash tables. But here we're giving a um a comparisonbased solution to the problem um which could also be used to solve things like predecessor for example. Okay. uh and uh you might be wondering you know in this class we see some pretty hefty data structures like fusion trees does anyone actually care in real life right so uh this data structure for this data there's this award called the Paris Konolus theory and practice
2:52 award and display trees won it in 99 for uh creating one of the most widely used data structures invented in the last 20 years okay so the authors won it for display tree. So uh apparently this is something that is not just uh in theory land. Okay. So uh so okay so what are trees?
3:13 So people have seen I hope some form of balanced binary search tree like maybe a red black tree AVL tree something like that. So a tree is again some binary search tree. So display trees are binary search trees. Okay. Um but after every operation we do some amount of rebalancing.
3:43 So after each operation uh the tree adjusts itself no so it's re some rebalancing okay actually I think the title of this paper is uh self adjusting something or other okay um okay good So what do I mean by um adjusting itself?
4:17 So this data structure operates in a model called the the BST model. So BST stands for binary search tree. How does the BST model work? So um uh at the beginning of each operation we have a pointer to the root of the tree. Okay.
4:52 And what can you do at each step? At each step you can either walk to some child. Okay. or um walk to a child or to a parent. Okay? Or do a rotation. I'll say what that means. At each step, we can follow a child or parent pointer or do a rotation.
5:23 Rotations are used uh to to to to rebalance the data structure. Okay. So what's a rotation? So we have this big tree. So rotation uh I'll just say describe what it is by a picture. So somewhere in this tree we have a node X. We have a node Y which is its parent.
5:56 So this is going to be rotate X. X might have some sub trees hanging off it. Why also this could be the empty tree. A, B and C could be empty trees. But this is, you know, in general what the picture looks like. And if we do a rotate on X, the rest of the tree stays looking how it was. But this picture turns into X now being the root.
6:30 Y is now right child of X and then B and C now live here and A lives here. Okay, so that's what I mean by rotation and X could be the right child of Y in which case uh you do there's a symmetric looking picture. Okay, so the point is that X now becomes the parent of its parent. Okay, and then these trees go wherever they need to go to keep the uh binary search tree ordering valid.
7:08 Okay, so I'll get right to it and tell you how trees work. So to do a find, how do you implement find? Search for X as you would in a BST. I mean tree is a BST, right? So you start at the rooe and you just keep going down the correct child to get to where X is. Then after reaching X, spllay X.
7:54 So spllay is a subruine that I will describe soon. Okay, it it's going to do some number of rotations to bring X to the root of the tree. So whenever you search for X after all the rebalancing is done, X is the new root. It's not just going to be rotate X over and over again until it's the root. It's going to be something just slightly more involved than that, but not much more.
8:19 And insert X. So, insert as in any BST. So, you find where it should go and put it there. Then, play X. Okay. and delete. Um there are several ways you can do delete. One way is uh spllay x then remove x from tree. Okay.
9:08 Well, when you spllay a node and it's the root and now you remove it, if it had things in both its sub trees, now you have like uh two different trees and you want to make sure that you have one tree at the end of the day, right? One balance, one binary search tree. So, what do you do? Um, if X had two children, uh, display the largest element in the left subree and make it the new route.
9:55 Okay. So what does that mean? Just to draw a little picture. So uh you have a tree. X was somewhere. You split X. Now X is the root. And then you deleted X. And then now you find the largest element in this tree. Uh let's uh colors and you bring that to the top and then now you add that so it becomes a new root.
10:35 Okay, so that's how you do deletes. Okay, so you know at the minimum we know we know that with B with bal with binary search trees you can get login uh time per operation using say red black trees AVL trees so trees we you know we'll show that you can you get that with spllay trees as well but one of the fascinating things about spllay trees is that they have all these other properties okay so for example um I think I mentioned this last time they have the uh static optimality property.
11:18 This was shown in the original paper by Slater and Targen. Let me just say Slater and Targen 85. Okay. So for any sequence of operations and any fixed binary tree t um say the time to perform all ops with display tree is big O of the time to perform all operations with t.
12:20 Okay, so if you knew the entire sequence of operations ahead of time um let me say uh let's say any sequence of yeah say find operations. So let's say that the end items are fixed. Okay. And you know what all the finds in the future are going to be. You know what they are and what what the order is. Okay. And now you want to build a binary tree, a binary search tree which services that sequence of finds as fast as possible.
12:53 So you can do this. I think I mentioned at the end of last class with dynamic programming, you can find such a tree. Um if you're not familiar with that, I think it's in CLRS. It's definitely in the lecture notes from CS124 last semester.
13:07 Um, but display trees don't know the future, right? I I showed you exactly how find works. It doesn't know what the future operations are going to be. Yet, the time that a display tree takes to perform all these operations is within a constant of the best tree, right?
13:23 It's within a constant of any tree, in particular, the best tree for that sequence. So, that's static optimality. There are other properties that display trees have. Um, one other one is called the uh working set property. This is also in Slater and Targen.
13:52 Okay. So I need to give you some one piece of notation, one definition. Let TJ be the number of items accessed since the last time we saw the J item in the sequence in the sequence of operations. So again let's say we have a bunch of finds. Okay. So we have find on you know some x i1 x i2 x i3 xim.
14:39 So we have m operations a bunch of finds and um let's say here we have the item that we searched for is [Music] seven and you know five steps ago we all we searched for seven in the past then what I'm saying is uh tj will be
15:02 five okay how many items were there in between the last access to this item so that implies that display trees achieve um O of M + N log N plus the sum J from 1 to M of TJ time log of
15:35 TJ okay so it's not just log in the number of nodes it's log in how many nodes there since the last access. And it's called the working set property because if there is a stretch of time where you keep searching for the same 10 nodes over and over again, then you're going to start spending constant time log of 10. Okay? So like those 10 nodes will be your working set.
16:04 There are a bunch of other properties it satisfies. Um I think I'll just name I'll just name a couple more and then I'll state a conjecture regarding slay trees which hasn't been proven yet. U another one is the static finger property also in the original paper.
16:32 Okay, it says let f be any fixed item. Okay, and I said there so there are n items in this data structure. Let's just assume that the keys are actually one two three up to n. Okay, since it's a comparisonbased data structure, all that matters is relative ordering. So let's just um assume that they're all ordered like this. So I is actually the you know the the rank of the E item but just assume it's the E item the E key. Let F be any fixed item.
17:10 Then the amortized cost of find uh I in a display tree is um O of log f minus i + one. Uh let's say F minus I. Okay. So this is true for all f. So you can pick f you know like uh for any given access sequence. Um the advertised cost per operation is this for a fixed f. So it's true in particular for the min overall f. Okay. That's the static finger property. Question. People look puzzled by this property.
18:17 So if you're spending a lot of time searching for keys that are near F, I mean you can search for anything, but if most of your searches are near F, then you're serving you're servicing this uh access sequence cheaply. Yeah. So what does that mean when I Yeah. So F minus I is zero.
18:35 So okay so plus one so I mean it's this part is always going to be uh at least zero but then there's a one so your your time is always going to be at least constant but uh in general it's log the distance to
18:53 f yeah I didn't mean to put log of zero I guess okay so there's also the dynamic finger this is actually not due to slater and taren Um, and let me see who this is due to. Cole is one of them. Cole, Mishra, Schmidt, and Seagull.
19:19 So, there are two papers, Cole, Mishra, Schmidt, and Seagull, as well as Cole by himself. They're both from two symp 2000. What does this say? Um suppose XS sequence is you know again X1 X2 XM then amvertised cost of the E operation is bigo of log of X I - X I - one + one.
20:26 So it's the reason it's called dynamic finger is here your finger always stays on F and you're measuring distance to F. Here your finger always moves to the the item you last searched for. Okay. And the proof is I think at least more than 100 pages. Okay.
20:46 So, um yeah, we're not doing it in class. Don't worry. Yeah. So, this this Yeah. So, um I don't know. This is very like uh well this paper is not by Taran but I feel like this is very taran style that the data structures and the algorithms themselves are often very simple. I didn't define spllay yet. It's going to be something simple. But then the analysis is the thing that uh takes all the hard work which is great for a programmer, right?
21:18 If you actually want to implement a data structure, who cares how long the proof is? Uh it only has to be proven once. Whereas with the with the implementation, you know, you might have to implement it in different languages or change the implementation a little to have some other property or something. You don't want to implement really complicated data structures that you then can't you can't later debug, etc. Well, okay. So, I guess it's it is nice to have short proofs too because people can check it then and also people can build on it.
21:47 But yeah, it's uh anyway, so that's dynamic finger. Um I think I want to say there's also something called a unified bound which tries to unify I think dynamic uh the finger property with the working set property which says that um like so instead of paying log of you basically pay log of the sum of these two things.
22:16 So there's the unified This was introduced by Iakono in 2001. We want the cost of uh operation J the amortized cost to be sort of to the min over all I less than J of log of uh let's say XI I - XJ plus I guess uh J minus I.
23:16 Okay, so it's sort of it's called unified bound because it unifies um the working set property and the uh finger property. So there should be some item beforehand which you are close to and didn't happen too far in the past. So it un tries to unify those two things. Unfortunately, it's not known that um it's not known that display trees achieve the unified property.
23:44 Okay, it's um it's not known that any BST satisfies the unified property, but Eono then gives a data structure which does achieve the unified property, but it's not a it's not a binary search tree. Some other it doesn't operate in the BST model. Okay, but it's it's an open problem. Um, the closest thing is we have uh I think Dairberry and um Slater Wad09. Okay.
24:28 services m operations in time o of m log log n plus the unified bound. This is the unified bound on on the sequence. So to really get to really uh with with some BST not with display trees they give a different uh data structure which achieves this bound.
24:56 So what you really want here is m not m log log n. Um, but okay, that's what's the best that's known. And before I so I still haven't told you what slay is, but uh before I tell you what slay is, I will state the granddaddy of them all or something.
25:33 So I defined for you what the BST model is, right? So at each so the beginning of every step your finger's at the root, you can follow pointers, you can do a rotates, okay, you can rotate the node you're currently you currently have your pointer set to. So then there's something called the uh dynamic optimality conjecture.
25:59 This is this was in I think in the original paper itself and it's been open ever since uh which I guess is almost 30 years now. So what does it say? Okay, so with static optimality I guess I static static optimality is right here. We just have um we're just comparing to a fixed tree. Okay, dynamic optimality lets the tree change.
26:32 Okay, so the tree that we're so there's a set of like BST uh algorithms, right? At every step you can choose am I going to move this pointer? Am I going to move down or up? Am I going to rotate? So um the dynamic optimality conjecture says that display trees basically do the best that anything could do. Okay. So, um uh let opt be the let's say opt of uh opt of sigma be the optimal cost of servicing access sequence sigma.
27:23 uh in the BST model. Okay. So pretend you know sigma, you know the entire sequence. Okay. And given that entire sequence, you're going to give you're going to spit out to me what you do at every step. So at every step, you're going to tell me either up point, go up, go down to some child, or do a rotate. Okay? But you need to make sure that you touch every correct you touch all the nodes in this access sequence. Okay, in the order in sigma the conjecture is that for all sigma the cost display tree cost of serving sigma is bigo of optive sigma.
28:10 So there's there's a fixed constant independent of n or m uh such that for all access sequences servicing that access sequence with a display tree is at most a constant factor larger than the true optimal way to do it. Okay. So are people happy with the difference between dynamic optimality and static optimality? Okay. Yeah.
28:42 So right. All right. So, the BST model says that um you know, you have you have one pointer that's always at a node somewhere and at every step uh you're allowed to either follow one of the children pointers, go to a parent pointer or do a rotate on the node you're currently pointing to. And every time there's a an access request, you need to make sure that your finger moves to where that node is.
29:10 Okay. So rotations are exact are the picture I drew. Yeah, that's a rotation. That's what rotation is. Okay. Um, so so let me let me write this like at most C times C times OP sigma. So for some fixed constant C. So question for you.
29:48 Suppose that I didn't insist that this C were a constant. I allowed it to be a function of let's say N, the number of items. What's one small value of C that you know is already known? Huh? Wait, what did you Yeah, login. Yes, any balanced binary search tree will get you at most opts login. Why? Because for each operation, for each uh uh element in this access sequence, you need at least constant time just to touch that node.
30:26 And a balanced BST is spending at most o of login. So it's at most login times opt. Okay. Um there was a data structure. So tango trees this is due to uh I think domain Harmono and Petrosku. This is in uh 2004. achieve C being O of log login log N.
31:11 Okay, so these are not display trees actually these trees these trees are not uh dynamically optimal. Okay, they're they were purely designed to see how low can we make this C, right? because we know that login is just follows from really old results in binary search trees. So can we get something closer to constant? So they showed that there is a BST model data structure that gets log in. And later there was also another paper by Wang uh Dairy Berry and Slater in soda 2006 that also got bigo of log login while simultaneously having login worst case or login amortised time per operation and log squared n worst case.
31:59 So this this doesn't have any good guarantees on worst case uh or amortized bounds at least not as good as the multiplay trees by uh Wang and the and the others. Yeah, that's right. Yeah. So, okay. Okay, so finally I should I should actually tell you what the data structure is by defining.
32:34 Okay, so I said that the purpose of spllay is to bring a node to the root. Okay, so um you know the um just rotating x over and over again until it's the root is going to you can create examples where that's not good. So for example suppose that you have a tree that's that looks like so I mean this this rotation is supposed to gradually keep the tree balanced somehow right if we want amvertised login per operation that's sort of it means on average the tree looks balanced so suppose that we just kept rotating things up to the root so let's say we have something that looks like six five
33:16 4 3 2 1 let's say that it's completely out of balance and let's suppose that our our fake play operation was just keep rotating till it's the root. So um keep rotating six. So suppose that we did a find on six and now we have to rotate it to be the root.
33:42 Then the picture is going to look like um six is up there and then I think it's going to be one here and then two three four five if I didn't mess up. That's I believe what it should look like.
34:04 Um so in other words, the depth used to be n and it's still n. Okay, so that's not good. Okay. So, how does play work? So, I'll just I'll just define it and it'll look like magic. And um you know with Fibonacci heaps at least I could say I could sort of say where they came from if you started off with binomial heaps with with spllay trees. Uh, I never, you know, I I've met both Slater and Targen.
34:39 I've never actually asked either of them uh why they did this, but a friend of mine who went to CMU where Slater is, he he apparently asked Slater several times. And Slater uh apparently gives different answers depending on when you ask him, and one of the answers was just the math works. So, um, so yeah, it's uh it's it is somewhat magical, but it's a simple thing.
35:02 It just seems to come out of nowhere. Uh, and even in hindsight, it's not obvious why it's so great. So, so how does how does play work? So, this is so so this is not a good idea. So, how does how does spllaying work? So they're going to be so splx repeatedly do the following to x. Okay.
35:42 So there are going to be three cases. So okay before I say the three cases suppose that Y is the parent of X and Z is the parent of Y. Okay. Now there may be I mean so we're done when X is the root. So what X definitely has at least a parent. It might not have a grandparent because um maybe maybe the the parent of X is the root itself. Okay.
36:17 So there are three cases. So case one uh y is the root and I'll say what to do in that case. Case two is that um X is the left child of Y and Y is the left child of Z or X is the right child of Y and Y is the right child of Z.
36:58 So X and Y are these child pointers are both going in the same direction. left left or right right and then case three is everything else. So or so x is left of y and y is right of z or x is the right child of y and y is the left child of z. So those are the three cases and what we do in the three cases is going to be different.
37:53 Yeah. Okay. That's what I thought. So case one. So y is the root. We'll just do rotate x. And now now x is the root. Case two. We have left left or right right. We'll do rotate Y then rotate X.
38:29 And then we have case three. We'll do rotate X then rotate X. Okay. So that's that's play. So we'll keep doing we'll keep looking at X. We're in one of the three cases. We'll do the corresponding thing and then we'll iterate this until X is finally the root. So maybe I'll draw a picture.
39:03 We already said what rotate looks like. So there's not really much to show you for case one. For case two, case two is like say left So pictures case two looks like Z goes to Y goes to X and then X has A and B down here C D.
39:35 So when we rotate, let's say we rotate Y, that's going to look like Y, Z, D, C, X, AB. And then now we rotate X. And that's going to look like xyz and then a b cd. So that's case two. So case two will bring us from this picture to this picture. Whereas case one or case three, sorry.
40:32 Case three, right? So this was we went left and left. There's an analogous picture for going right and right. I'm not going to draw it. Case three, things go in different directions. So we have Z up here. We go left to Y. Then we go right to to X.
40:52 Um so here we have a b c d so I said the first thing we do is we rotate x we rotate x twice. So the first rotate x looks like z uh x um y is less than x. So here and then this is AB C D and then we rotate X again and then that brings it to look like this.
41:33 X Z Y D C A. Okay. And sort of I mean this is not going to be a proof of anything but it's at least a hint that something is good. We could ask ourselves what does doing a play on the leaf of a path do right so I drew a picture before that said if you just keep rotating x it doesn't look that great so at le whatever we're doing now hopefully it at least fixes that problem so let's just look at spllay on one of these things so suppose I have Um, six, five, four, three, two, one.
42:37 And then I spllay on six. Actually, in my notes, I don't know why I did this to myself. I just made it one different. I don't want to have to think on the fly and draw a wrong picture. Okay. So, um, so what is there?
42:53 There's stuff hanging off at the bottom here. I'm not going to label everything. Otherwise, this is H. So, if you spllay on six, what does that look like? I'll draw it for you. Wait a second. Can someone tell me something that's wrong with this picture? Yeah.
43:18 So, so these are all negative numbers. Whoops. Now this picture is at least sensible. Uh I don't want to keep writing negative numbers but alas. Okay. So so six minus 6 has to be on the top. We know. Um and then we have minus one hanging off and zero.
43:59 Oh, really? Oh. Ah, you're right. So, I really I really messed up myself. So, this should really be um minus one should be off to the right. Um and then now uh -2 -3 -4 - 5 Okay, good. So, what this looks like. There should be one thing left. These trees are still around.
45:13 Okay. So, so yeah, please in the lecture notes I guess please don't have minus signs. Yeah, those okay. So um the main idea is if you do spllay on a path basically half the path gets put here and then each one has a node hanging off. Okay. So the depth decreased by about a factor of two. So that's at least promising. It's not a proof of anything really but uh so promising that we're in the heading in the right direction.
45:56 So let's actually prove something. So claim the amortized cost of an operation is uh you know what do we want it to be login. So we're going to use the potential function method. Okay. So before Oh is that from outside? Okay. Oh yeah, it's someone in the hallway. Okay. So before when we were dealing with Fibonacci heaps and binomial heaps
46:59 um things were easy to picture in your head because we had this uh you know adding money to a to this bank account and taking it out later when we needed to spend it. Uh now the potential function is going to look a little more complicated and we're going to have to um use uh one inequality at some point.
47:19 Okay, namely AMGM arith geometric mean is at most arithmetic mean. You'll see where that's going to come up. But okay, so the strategy is going to be the potential function method. Okay, so we're going to give every item X a weight wx.
47:59 We're going to define s of x as being the sum over z in x's subree of the weight of z. So this includes x itself. So the sum of all the weights in its subree. and r of x is going to be log of s of x.
48:35 Okay. And then now we can define our potential function. The potential at any given state is the sum i from 1 to n of r of i. Okay, it's the sum of all of these. I don't know what to call this. I think some people call this the rank of x.
49:04 It's a sum of all the ranks in the data structure. Okay. So, that seems like it's out of thin air. Sort of is. So, yeah. I'm sorry. That's uh Sometimes things are magical. What can you say? So, um we wanted we so what we want to do now is bound um so first of all, let's look at find right.
49:36 So the cost of find is basically the cost of the slay operation, right? Because we walk down and then we spllay back up. And the cost of splaying back up is the actual cost, not the amortized cost. The actual cost of slaying back up is proportional to the height of the tree or to the height, not the height of the tree, but the length of the path down to X. So we can charge going back down, we can charge going down to X to the which brings it back up.
50:02 So the advertised cost of of a of a find for example is just bigo of the cost of splaying. So let's figure out what is the advertised cost of a slay operation. Okay. So question so uh so the
50:24 amortized cost so the uh the cost of a find is bigo of of of a find on X is big O of the cost advertised cost ah the cost display X. So what is the amortized cost of spllay X? Okay.
51:17 So let's figure this out. So remember how spllay works. We just keeping we just keep doing uh one of Uhhuh. You know what? I do not want to erase this. So I will erase this. Okay, so spllay has a number of like mini spplay operations inside where we're either in case one, two, or three over and over again, right? So let's figure out the amortized cost of let's say a case 2 operation and then we can just sum up everything as we display all the way to the top. Okay.
52:19 So I'm only going to do the amortized cost of two like everything else is very case too. I mean everything else is kind of similar. So otherwise you have to look at okay what if it were right right? What if it were left right right left. It's just uh pointless to do this in class. Okay. So I'll just do one. So let's look at case two going left.
52:50 So that picture up there I mean uh y is left of z of z and x is left of y. Now remember advertised cost the definition we gave is the actual cost plus um the difference in potential. Okay. So the actual cost we do two rotations. So it's a constant.
53:33 Let's say a let's say a rotation costs one following a pointer costs one. So this is let's say cost of two. You can put I mean whatever constant it actually is on your machine put that there. You can make this proof work. Okay. It's not a big deal. Now how about this thing? This thing um we will show is at most uh 3 times RP prime of X - RX minus 2. Now what's RP prime of X?
54:15 This is the new rank of X after uh we do the two rotations. So I mean here here it has some rank RX and finally after we do the two rotations it has some new rank R prime of X.
54:45 Okay, so notice this two is going to cancel that two. And when we sum over all of the uh these case operations going to the root, it's going to telescope and we're going to be left with um r of the root minus r of x to begin with.
55:12 Okay, remember it doesn't matter who the root is. R of the root is always the same because you sum over everyone in the whole tree. So okay. Um in fact advertised cost of cases 2 and three are both at most 3 r prime of x - rx.
55:51 For case one, it's at most 3 RP prime of X minus RX + one. Okay, so this is the thing I'm going to show. We'll show this for case two, but just take my word that you also get the same thing for case three, and you get an additive one for case one. So that implies minus two.
56:38 So the am so the Yeah. Go ahead. Oh. Oh yeah. Yeah. Yeah. I see what you mean. No. Oh, so the advertised I'm the advertised cost is defined to be the sum the actual cost plus the change in potential. So, right. So, um yeah.
57:03 So um let's see that implies that uh the cost the advertised cost of spllay x is at most um o of one plus so 1 plus um 3 * r of the root minus r of X which if you remember R of X is the log of the sum of weights in the sub tree.
57:44 Um, that's going to be at most of 1 + log of w over s of x. W is the sum over all e over all weights, right? S of the root is just the sum of everything. So now let's actually show this for case two. Okay.
58:34 So change in potential that's the thing we're trying to bound. So let's look at this picture. If you look at all the nodes in the in the trees A, B, C, and D, none of their F values actually ch none of their R values actually changed, right? Nothing like the set of descendants in their sub trees all stayed the same. Um, so the only people who did change are X, Y, and Z, right?
59:00 Their Rs changed because the people in their sub trees changed. So uh so case two the difference in potential is uh r prime of x plus r prime of y plus r prime of z minus r of x plus r of y plus r of z.
59:32 Right? Okay. Now, RP prime of X equals R of Z, right? Because the set of items in its subree, the set of the set of items in X is a sub tree here is the same as the set of items in Z subree there. So, let me write some facts as we observe them.
59:57 Uh, so this is equal to so what got cancelled? R prime of X will cancel R of Z. So this is equal to R prime of Y plus R prime of Z minus R of X minus R of Y. This is because R prime of X is equal to is this visible?
1:00:20 I don't think this blue is very visible. R prime of X is equal to R of Z. What else do we know? We know that um RP prime of Y is less than or equal to R prime of X. Right?
1:00:49 Let me make sure I'm not using bogus inequalities here. So we'll also we're also going to use the fact that uh let's see yeah how did I seem to have confused myself. So this is at most I want to say I know that r of y is bigger than or equal to r of x.
1:01:34 So r of y is bigger than equal to rx. So this is at most r prime of y plus r prime of z minus 2 rx. And then I know RP prime of Y is less than or equal to R prime of X. And then this is less than or equal to R prime of X plus R prime of Z minus 2 RX. This is because R prime of X is greater than equal to R of Y.
1:02:12 Uh RP prime of Y. Yeah. Okay. So now let's do a little more. Now I want to bound this this business here. Uh so let's look at this thing. RP prime of X plus RP prime of Z. Let's bound it.
1:03:07 Let's divide by two. Okay. What is this thing? This is log of S prime of X. uh plus log of S prime of Z over two, which is the same thing as log of the square root of S prime of X S prime of Z, right?
1:03:39 And then now we use the fact that the geometric mean is at most the arithmetic mean. This is at most uh log of s prime of x plus s prime of z over two. Did I? Huh? Why am I feeling not so happy?
1:04:21 This is not what I So, let's actually Yeah, I know why. I actually want to bound this. Okay, so this is not exactly this, but we're going to see that this thing is going to pop out. Okay, what we actually what we actually want to do is we're going to bound R prime of Z. So this work that I'm doing here is to eventually bound R prime of Z.
1:04:47 Okay, I'm sorry. Why can't we bound R prime of Z with R prime of X? Uh, what do you mean? You mean right now? So, at the end of the day, remember the bound that I want I wanted just to I want everything in terms of X.
1:05:25 Um, right. So yeah, I see that actually seems to make a lot of sense. I'm sorry. So yeah, I think Okay. So yeah, what you're saying? Okay. So yeah, I think I now I uh Okay, so I'll do it this way and and show you this won't matter that much for getting the login, but when I want to show like one of the other properties such as for example um uh uh working set or uh static optimality, I'm going to fudge my definition of like this potential fee a little and allow fee to be negative.
1:06:21 Okay. And and then we'll go back and see what that means in terms of like bounding real cost in terms of advertised cost. But once I do that, I'm going to allow these like RP primes to be uh negative numbers. So like I'm going to allow I'm going to allow um I'm gonna allow Yeah. So things that are above you in the tree could be even more negative potentially.
1:06:50 Oh, I see. Oh, yeah. That's a good So, yeah, this is a very good point. Now, I'm uh um frime of z is at most frime of x. Yeah, actually what you're saying makes a lot of sense. So I don't know why um I read this proof.
1:07:32 No, no, no, that's not important. Um but yeah, this makes sense. So, so the point you're saying is this thing here we can replace by so this is RP prime of X plus R prime of X minus 2 RX. Uh, I need the minus two.
1:07:53 Yes. Whoa. Yes. Okay. Thank you. Okay. Now I know why I need to do this. Okay. I need to kill that two over there. Okay. Does that Okay. Okay. So, I completely forgot about that two. So let's go back to business. So I want to bound good. So I don't just want to bound I don't just want to bound R prime of Z by R prime of X and get two. I I don't just want to get big O of R prime of X minus RX.
1:08:17 I also want to get this minus two to kill the to kill that two. Yeah, that was the key. Sorry about that. Okay, so let's go let's go back there. and I want to bound RP prime of Z. So this is equal to that is equal to that I applied AMGM. Okay.
1:08:41 And now um so I actually even with this even what I said with negative numbers I am going to maintain the property that um as you go up in the tree are ranks are only going to be non-deasing. Okay. Um so now let's look at S of X plus S prime of Z. S of X has all these nodes.
1:09:12 S prime of Z has all these nodes. Okay. So if you take the sum of them, you have this you have everything except for Y. Whereas y is contained whereas everything is sr prime of x. So this thing here is at most s prime of x.
1:09:44 So this is at most log of sr prime of x over 2 which equals rp prime of x - 1. And then now you multiply by two and you subtract off rx. So now I can get rid of this picture finally. Are people happy with with me? Uh are people happy with this inequality? Okay.
1:10:30 So multiplying by two and bringing over the r of x, this all implies that r prime of z is at most um 2 rprime of x - rx - 2. Now we plug that in for r prime of z. Here we get 3 RP prime of X - 3 RX - 2. So this all implies that delta V is at most 3 RP prime of X minus RX minus 2 which as I said before implies that the amortized cost of
1:11:15 spllay in in case in case two anyway and it's also going to be true for case three is at most 3 * R prime of X - RX Okay. Yeah. Uh I mean of just one I mean just doing uh yeah sorry. So average cost advertised cost of case two is what I really meant to say. Okay.
1:11:49 But if you did the same exact thing for case three or a similar thing, you would get the same bound. If you did it for case one, you would get an extra plus one here. So you only pay that plus one once in the entire display, namely in the last step, potentially the last step. Yeah.
1:12:15 Sorry, say it again. Oh, so delta V will be Um, so I mean at the end of the day, this telescope's all the way up to the root and you pay r you pay r of the root minus uh r x. So um I don't know if I maybe I misunderstood your question. So I guess oh when you when you when you're in case one, where does the plus one come from?
1:12:50 Um, well, I see. Uh, if delta V had a minus term. Uh, maybe I'm not sure what you mean by that. Oh, I see. Um, I see. Uh, right. You're saying, uh, right. So I guess so the point is at the root you don't get to subtract stuff at the very last time. I don't know if I'm answering your question.
1:13:27 Okay. The cost of an operation is not negative. If that's what that's Oh, yeah. Um, okay. So, okay. So yeah, that's your that's a good question and it's going to bring me to now proving the actual claim which is that um so so what so okay so once you do it for all the cases and do the telescoping thing I said above what do we have we have that okay so we said that the advertised
1:14:03 cost of X is O of 1 plus log the sum of the weights over S of Okay, so to answer your question, why did we deal with all this like arbitrary weightings, right? It's because we want to prove different properties of display trees, for example, having the working set property or whatever. If we just want to prove an amortized bound of login, okay, then how would you define the weights?
1:14:36 Yeah, if you make all the weights one, this implies amortized cost of spllay x is o of login n y. Make the weight of x one for all x. Then the sum of all the weights is n and then you're dividing by something which is at least one. So you have login here.
1:15:07 Okay. But what if you want to prove these other amazing properties of display trees? So what about So I'll just do one before the end of class. What about static optimality? How'd you define the weights there? So the items let's say are one up to n. Okay.
1:15:57 Let's say some tree T puts item I at level L subi. I I should mention um the way that I'm going to do the analysis now um is a way that I saw done by David Epstein. So um the the way static optimality is originally phrased in the Slater Targent paper is they show how many people know what entropy is entropy like Shannon entropy. Okay. So the thing about this static optimality. So the way I phrase static optimality at the beginning of the class is I said for any tree T for any fixed tree T you do your split trees do as well as as T does okay on the access sequence.
1:16:54 But for a given access sequence, it's understood how well um the optimal tree does. This is Huffman coding. Okay. And what it does is uh it gets you a bound a running time bound which is proportional to the entropy of of uh like if you look at the pro if you look at the fraction of times you search for I as the probability of I the Shannon entropy of that quantity is uh is the bound that the optimal tree achieves. and Slater and Taran showed that display trees get the entropy bound. So yeah.
1:17:28 So does the sequence of accesses only right? So here yeah there's a fixed tree. So um so I'm assuming yeah this you have the set of and items given to you um and like the items are one there no insertions there's just like finds over and over again. Okay, so Slater and Taran actually show that display trees achieve the entropy bound.
1:17:57 But I don't want to talk I don't want to have to define entropy and then show you that proof. Um I think it's more natural to just say look for any tree trees uh do at least as good as t. Okay. And that was uh so the proof I'm going to show you not avoiding mentioning entropy uh is a proof I saw by David Epstein.
1:18:18 I think he just put it in his live journal at some point. I don't think it was even a p written in a paper anywhere. Okay. So the weight and also I'm I'm not going to prove exact you'll see what we prove. Okay. I'm not going to prove the strongest thing possible but uh just to give you an idea of uh the flexibility of these weights. I'm gonna define the weight of I as being 1 over 3 to the li.
1:18:59 Okay. So before I analyze play trees um say I is accessed is uh say find I is called Ni times or MI times what's the cost of serving this access sequence using the fixed tree P. I mean what's the time to do a find on I
1:19:45 li right so this implies that cost with t is o of m plus the sum i from 1 to n m i li i right so that's the that's the bound we want to say spllay trees also achieve So we'll show trees get O of M + N 2 plus the sum over I from 1 to N MI li.
1:20:31 So as long as the sequence of operations is long enough. So no matter what initial configuration your display tree was in. So your display tree in the beginning is an arbitrary binary search tree on these items. No matter how you start it off after m operations, this is what the b the running time will be. So as long as the number of operations is big enough, it'll start like behaving as the optimal tree. Okay.
1:20:58 So with a very slight change of this weight it's possible to make this n squ be n login log n and in the actual slater charge paper where they just deal directly with entropy this term disappears alto together and they really show that it's up to a constant what it should be okay but just to give you an idea I just wanted to show you uh something more intuitive okay so so good so remember remember that advertised uh time.
1:21:30 Well, the amis time for an operation is the actual time plus the difference in potential. So the advertised time of everything of the whole sequence is the actual time plus the uh the final potential minus the initial potential. Remember we're not starting with the empty tree, right? The tree started in some configuration and then we kept running fines according to this access sequence. So this implies that the actual time is equal to the amortized time plus v initial minus f final.
1:22:26 Okay, now I just want to say that this thing is bounded by n^ squ and then this is going to be bounded by m plus this thing. So why is this bounded by n^ squ? I'm just going to say something very silly.
1:22:43 If you look at any so if you look at any node and ask what its rank is the worst case is that the rank is uh well this optimal tree t could be a path for all I know right in which case some node can have depth n and then um log of 1 over 3 to the li is like basically minus n.
1:23:11 Okay, so log of a of a weight in the worst case is minus n for a node and in the best case the depth could be at the root and then this will give you you know log of that log of one will be zero or something. So contributions of nodes are anywhere from minus n to zero. So for the whole tree it goes anywhere from minus n^ squ to zero. So the potential is a number between 0 and - n^ 2.
1:23:37 So it definitely can't change by more than n squ. So this is at most n squ. Um you can do better I mentioned but then the proof just becomes very slightly more complicated. Not much. How about the amortized time?
1:23:54 Well let's look at the amortized time of searching for i.vertise time of find i. is equal to well I erased the but it's log the sum of the weights well it's sum of the weights over s of x s of i plus one
1:24:28 it's up there oh it is up there okay good thank you is up there and in the last 30 seconds what's the sum of weights. So weights are 1 over 3 to the 3 to the li. How many different nodes can have a weight of 1 over 3 to the li?
1:24:51 2 to the li, right? Weight is sum over li uh 1 over 3 to the li times number l number of nodes. Yeah. Yeah. Like in 30 seconds at height L. But this is at most two to the L. So this is at most some over L 2/3 to the L which converges. It's a constant.
1:25:24 So you get basically log of 1 over 3 to the L. So this thing is going to be O of 1 + LI, which is exactly what we wanted. Okay, so sorry I did a little rush at the very end, but uh this is just one property the static optimality, but there are lots of properties and you can prove many of them by just choosing your weight function appropriately. Yeah, compression schemes.
1:25:54 Um yeah I mean so the reason that the static bound the static optimal bound is entropy is related exactly to compression right right uh yeah I guess I mean you can say that but uh I I think I see maybe what you're saying, but I I haven't really thought about like a a coding application where you would want to use play trees to change your encoding. Uh yeah, I don't know.
1:26:39 Oh, yeah. Problem sets up front. Yeah.