Video 2-10: Dynamic Optimality II: Properties of BSTs

0:03 So let's see what we can say about the display spray display tree conjecture that play is constant competitive. Um first let me remark that it doesn't matter so much what the initial tree looks like. Uh it doesn't feature in this statement at all but indeed the original statement includes that that um if the axis sequence is long enough it doesn't matter what tree you started with. But this is not completely uh obvious or given. It it is true in this case because um you can always get from one binary search tree to any other with a linear number of rotations. Or uh in other words um you could after um as an offline algorithm, you could always pay the cost of n uh rotations up front to get the tree into the shape you would like it to [clears throat] be. And if the access sequence is long enough, you can amortize this initial cost over the sequence of accesses. And because that's that's the statement to make. For online algorithms, it's not super obvious whether the initial tree cannot have some influence. And we'll see some cases where indeed at least the behavior in the details is different. Uh but let me quickly prove um this statement as it's given there. Uh I'm not going to prove the slightly stronger bound below it. Um the fact that matters is that this is a linear number of rotations and you'll see from the construction it's even local and you could do it with some finger moving around the tree and do local rotations. That would suffice. Uh you can slightly lower the number of rotations and that's tight but that's not so important or exciting.

1:58 The idea is to um describe some sequence of rotations. And let me just do um small example tree to illustrate this. That could be your binary search tree as the input. Now I'm not going to solve the problem of going from any tree to any other tree. Instead uh I'm going to show you how to get from this tree to a canonical tree. And because the num the rotations are an invertible operation, you can always go back the same way. Um if you can go from any tree in few rotations, namely n minus one to this canonical tree, then you can also go from the canonical tree back to any other tree, right?

3:30 And the canonical tree is even an easy one. It's just uh the completely right leaning path. There's probably many ways to do this. Uh one option is that you take the current trees right spine.

3:49 So what you get if you follow right edges only that's the part that's already in the shape we wanted for this canonical tree. There's going to be a first sub tree that hangs off from this right spine and I'm going to rotate that edge and that turns this left leaning edge into a right leaning edge to do the rotation bit more space. So, what does the rotation do? It flips this um this edge. And there's the sub trees that hang down from uh sorry, these two sub trees and this sub tree. And now, uh maybe I should have copied only those.

4:47 I'm reattaching these to the changed part of the tree. So, uh, the root chair is not changed. But then instead of having this edge slope that way, I'm going to rotate it. So, this is the blue edge. And now I have to reattach the three sub trees in the same symmetric order. So, these two go here again. Uh the two nodes that participated here are are these two. Let me draw those blue. So this sub tree becomes the left child of that. That becomes the left child of this. And this other larger subree becomes the right child of this blue node like this. And now you see um we've made this right spine one edge longer. It was one, two, three, four before and now it's one, two, three, four, five. Well, because I turned one left leaning edge into one on the spine. So, if I repeat that step for at most n minus one times, I'm always in this completely right leaning uh situation.

6:04 I don't know if you feel like uh it's useful to have another example, we can do one more, but that's basically the idea. So, let's get rid of the green stuff. Also, this is no longer the blue edge. So, the next blue edge would be this one, right?

6:58 then we have this edge from the root as before. Then the new blue edge. In this case, there's not even much hanging down from it. So this this node doesn't have sub trees. So this is as it is and all the rest is just uh the same as before.

7:22 And so you already visually see how it gets turned into this shape. Um it's a bit non constructive in the sense that if you want to compute the exact rotations kind of have to plan ahead because I'm I'm using this in reverse. But for the statement, let's ignore that. We're basically just interested in this existence and there is some algorithm to compute it. Um I'll talk a bit more about the computational model uh in a second actually on the next slide.

7:52 Uh so far I've I've stated um maybe let's go back briefly to bring that to memory. Uh I've stated this model of computation for binary search trees. Remember when we talk about online algorithms and we want to do competitive analysis we have to say what is an offline algorithm allowed to do so that I can compare against all of them the optimal offline and here the model was that we have a tree at any point in time the data structure has to be a binary search tree and I have to keep a finger in the data structure that I can move around with one of those five operations I can move it left child right child or parent I can uh do a rotation which means rotate the parent edge and when I'm sitting at a node that I'm requested to find I can say find then that's reported and I jump back to the root.

8:44 Um that's all uh the optimal offline algorithm can do and the the goal is to find the shortest such sequence of rotations that serves all the axises.

9:01 It turns out you can reformulate the problem a little bit or the the kind of algorithms you allow uh to do uh so that it's a bit more pleasant to work with in particular for designing algorithms that work online and that we compare than uh with optimal offline algorithms. [snorts] And the first the first um simplification again I think is much clearer with a short example. So let me again draw a little tree and so that we have a little bit of material to move around. Needs to be a tiny bit bigger.

9:42 Not sure if that's too big to illustrate the concept. Should be fine. That could be your binary search tree. Uh now suppose I'm accessing some uh note say this one. Now to serve this request I have to move there. So I have to start at the root. Find always restarts my finger at the root. So the search path to this element I have to touch. There's no way around. I may if I want to in principle also go somewhere else off the path and visit some other nodes. Whether that's a useful idea or not is actually open. Uh we don't really know.

10:55 Now one option would be to say we can now as an online algorithm take any of these touch nodes that I'm visiting and rotate uh but in light of this this lema from here the number of rotations uh is or say say the other way around whatever I can do with rotations is rearrange the notes I visited that I touched by touch I mean I've ever had my finger on them. Um, all I can do with rotations is rearrange this top part of the tree, what's colored in here, into a different binary search tree with all the other things um, hanging off. So, I might transform that a bit smaller. Maybe I'll have to leave all these sub trees that hang off from this touched part.

11:52 These I have to leave unchanged. That was a weird sub tree. But the uh touch nodes I can rearrange into any kind of other binary search tree. Okay, I need this.

12:07 It's about to take this guy. And now um these are six nodes that I touched here. The order will have to stay the same, but I can rearrange them into some different binary search tree. Maybe um I want to put them like this.

12:38 And this is just for illustration. It really doesn't matter what what I put them like. Uh let me draw it a bit cleaner so that it better matches it. I have to reattach these trees in some sensible order.

13:04 So this will connect to these. This will connect to these. Let's stay here and 1 2 3 4 five six but this is not a binary search tree okay I've uh changed slightly the example doesn't matter though the point is where the linear number number of rotations I can rearrange this top part of the tree and up to a constant factor it doesn't matter what tree I produce there or how exactly I do this with what rotations uh what counts is how many nodes have I touched and so um it's a bit easier to work with this cost function where we just count how many nodes have I touched from the top part then I can rearrange those uh here this one kind of I didn't H I changed the sub trees. Um but this is incorrect, right? 1 2 3 4 5 six. I'm I'm missing a sub tree. No. Okay, this guy has an empty sub tree. I should have circled that. So this even if it doesn't have a a subree here, there's a sub tree here. So I messed up the the connections. There's another subree here. So how who who belongs to whom?

14:40 This one owns two sub trees. Then this one should own the next two. Let me draw it a bit closer to the side. Then maybe I can squeeze it in. And these can move a bit.

14:58 These two. And this one owns these two where one is empty and the rest stays. Okay. So even um empty sub trees are included in this game doesn't change the rest. Okay. And again crucially we used here that the this number of rotations to go from one sub tree to the other is linear in its size. There was another part in the original model. Uh this was in the original display tree paper. They allowed rotation somewhere in the tree at some disconnected location. The point is you can't really do those in our model. But also they don't help you at all. Like if if you rotate something down there in the tree and you don't look at it, it's as if you hadn't done it. And indeed you can uh with bookkeeping outside of the binary search tree. Suppose that's allowed. you can delay such rotations until you eventually touch that part of the tree again and only apply them then and this doesn't really change the cost of the overall algorithm.

16:03 uh as I mentioned it's an open research problem whether restricting the online algorithm to only touch the search path to the nodes that we actually request if that is somehow less restrict is if that's more restrictive if that's less powerful we don't know uh all the conjectured algorithms like play uh they only do that they follow a search path and slay up but they don't spontaneous continously visit some other part of the tree in the hope that this helps uh future queries. They don't do that, but we don't know if that's uh um too strict or if that's hopeless. Say second restriction. Um, the access sequence in principle requests items and uh, I could surf the access and then leave the item there. But spllay doesn't do that. It always brings the item to the root. And it turns out this is again kind of without loss of generality. At least for an offline algorithm, you can always pretend that the axis magically happens to to be when the item is at the root. So the access sequence still consists of some sequence of nodes or keys but we require that a valid algorithm brings that element to the root when it calls access.

17:30 Okay again does exactly that. Um and for for an offline algorithm we can always do that. Uh for online algorithm I think again we don't know if insisting that it brings things to the root is without loss of generality. The point is that um you can you can bring it up to the root in the time proportional to the time to find it but it's not clear if you would have been able to simulate bringing it back down because the next axis might not use the same path. So it's not clear whereas the optimal offline algorithm uh if it profits from having the element down there it's just a constant factor to bring it up and down and come back up. So in a way um it can't hurt much if you're doing it offline uh for the online model is unclear but we're still assuming this because it doesn't seem to be a restriction for all the algorithms we care about. So if an access hack happens to an element that element has to be at the root at that point in time.

18:40 The main part is this top part of the tree which you'll see in the next section is extremely natural. Uh what can we say about opt the offline optimal way to rotate or change the tree? Uh you'll see in the exercises you can in principle compute the optimal sequence even though uh it's fairly slow. Um I won't go into much detail on the second point. We don't really know if it's NP hard for this precise problem but a related problem is NP hard and so it it feels like it might be uh a proper reduction has not been found. So this is another open problem even if I didn't state it in this case. Uh even even good approximations for opt are hard to come by. So it's a very mysterious thing. The other thing you might be interested, it's actually more interesting than the precise value of OP might be good lower bounds for OPT where we can compare our online algorithms against that.

19:48 Um and a simple counting argument shows you that most access sequences are hard in the sense that they require a lot of uh a lot of cost in our let's let's stick with this touching top part of the tree. Um, intuitively you can say most most of the time most of the elements in a binary search tree are down at the leaves and so there must be an access that's expensive that's of cost at least login whatever you do. Uh, but that's not quite strong enough because we're talking about access sequences and we know the whole thing in advance. So there might might be a sneaky way for opt to somehow get all the accesses that it ever needs close to the root. uh the formal argument says fine let's try to encode the access sequence and the execution of the binary search tree algorithm whatever it does is an encoding for this sequence because whenever it says find I know where I am and I know the value so that I can reconstruct the access sequence from following the movement of the finger the number of overall axis sequences is n to the m I have n options and I choose m times uh but the step of a binary search tree algorithm is only one out of five choices that means um I didn't write this down further so the number of different so uh the number of different sequences is n to the m which means I need log of that many bits of binary decisions to encode code an arbitrary sequence of these. That's of course m * log n.

21:45 On the other hand, a single step in the binary search tree sequence only gives me a constant number of uh of bits or one out of five is not even that much, right? So, uh, if that math is going is supposed to work out. I have to take m log n divided this constant many steps. Usually uh formally you can say you count the number of different axis sequences you can encode with up to t steps.

23:03 And for that thing to be n to the m you need to pick t at least order m login. So in a way uh you can't even get that much from dynamic optimality in the in the average case. If you pick a sequence at random, you're likely going to need login per axis. But that's uh that's not withstanding that some access sequences or or many interesting classes of access sequences allow you to work faster. It just means uh you shouldn't expect opt to be much better than the worst case if you pick a random sequence.

23:43 Now this is cute kind of uh knowledge to um manage expectations. It doesn't help at all to design an algorithm because such arguments are non-constructive. They don't tell you any specific if you're given a specific access sequence, you can't tell if that's a hard or an easy one because this is just uh comparing the number of different things you can do and what kind of sequences are easy to encode with BST algorithms or not is is not clear from that. Uh there is um one one famous paper that worked in this re in this direction trying to find specific more instance specific lower bounds for the optimal number of operations you need. Um there's more in there that I'm I'm not going to uh go into detail but I want to present one particular result which is one concrete specific axis sequence. You can write it down. It's parametric so that it can be of arbitrary size. Uh but here's a specific one and that one that specific one is is m login cost or login per access no matter what you do. Uh that's maybe more surprising because you would think somehow opt knowing that this is the access sequence will somehow make make it happen that the elements are always close to the root but it can't.

25:10 Uh this is called the bit reversal sequence because it's defined by taking the reverse of the binary representation of a number and it has this this funny feature that it maximally jumps between smaller and and larger numbers. If you see uh zero and eight are kind of the opposite of uh of extremes. So it often has large jumps and intuitively this is what makes it hard for the search tree to keep up with because the the search tree has to be sorted and so if you constantly jump between smaller and larger halves then you always have to go down find the tree but you have to do it in such a such a mean way that even putting somehow knowing in advance what accesses come is not going to help you much. So we won't go into the proof. Um I just want to state this uh as a result. So if you're looking for some concrete example to test out some algorithm, this is often an interesting one. But even for opt it's hard. So it's not going to answer our dynamic optimality question in any way.

26:26 There's another result I only want to site. So this this paper by Wilbur has um more specific lower bounds where you're given an axis sequence and then the lower bound tells you up needs at least that many steps and one of these led to uh still one of the best binary search tree algorithms in terms of the competitive ratio.

26:49 These are called tango trees. Uh again I'm not going to say much about the details. In a way, they're designed to closely mimic what one of the lower bounds does and stay as close to it as possible. It messes up badly in in the worst case. So, it's not even a balanced tree, like not a log and height tree. Uh, and it's also complicated in that it it needs um it needs a way to essentially represent in one binary search tree several a constant number of binary search trees that independently operate. And there's a clever na way to do that. Uh but it's rather technical. I don't want to um go into detail into this. Uh but the result shows you can in principle have something better than this login competitive ratio. here really like the data structure is probably utterly useless outside of this context but it's specifically designed to be good at competitive ratio and gets it down to log login.

27:54 We also know it can't be better than that. So this is not a dynamically optimal data structure. It messes up on some simple instances. Uh that's how it is. Um but it shows you some progress on on the problem can be made.

28:22 Yeah, not not more on this. Um the last piece I want to mention about the general problem is an algorithm that seems if if you know a bit of the future like a reasonable guess for for something close to opt it's going to be a simple uristic and we have the suspicion that op might be np hard so it's not going to be precisely opt but if you think about uh what spllay trees do and what you could potenti potentially do? If you knew a bit of the future, what would you do? And at least uh two people working in this area independently came up with the same idea and it was it it pops up in a different context that you'll see uh soon. So I think it's it's kind of natural. That's this this idea of uh the greedy future algorithm. Um suppose you you have to find this element you walk down your search path.

29:17 Uh nothing else possible. Let me again do with my uh can I steal the picture from before? Maybe ah the messed with one. Okay, I'll see. Uh to make it more concrete, we touch some search path.

29:45 Ignore the colors. at least this one. So suppose again we we touch this this element here and now uh all I can really do sensibly is rearrange this search path. All this this going off of the path. Nah, I I don't think there's good justification why that would help. But I can look at the things that hang off the search path now. So this sub tree and these little guys, well the empty one is not going to make much difference. And this one, wouldn't it be smart to look at if I know the future anyways, the next access time to any of these elements on the path as well as the sub trees. If I know I'm going to touch some node in this sub tree soon, I want to stick it closer to the root. Whereas if I know I'm not going to need this guy anytime soon, it might as well stay down there. And the quantitative way to do that is to build a tree uh where we need where we use the next access times to these elements and uh let that guide our the height.

31:05 So specifically um I basically ask all of these uh these nodes and their sub trees that hang from them when are you attached next? And I'll take the the largest of these say um you can nicely write it as a trip when you first move all of the red red elements above all the other ones. in terms of their priority and then rearrange them looking at the future access to this element or it's the sub trees between it and then maybe this is boyed up maybe then there comes this whatever whatever the order is you're going to find some tree over these five elements uh okay That's not a binary search tree like this. And then the sub trees are again going to attach to these in the unique way that they can.

32:47 Even though it looks a bit messy, I think it's is still roughly correct. And that gives you a new tree. Now, of course, we can't really do this online. We need need to know the future for this. But it seems that this is the maximal use of the future we can make because we exploit it for precisely what we can namely rearranging this top part of the tree. And indeed the conjecture um the conjecture at the time was that it's not optimal but it's pays at most one at most one extra access over top over opt. And the idea why this so one per per uh axis one one extra touched node per uh query and where does this plus one come from? Well maybe opt improves somehow on this picture by going off of the search path and bringing some other subp part further up. Then you can essentially delay that going off the path and there's not that much you're going to change. There's only this weird this annoying configuration where um uh here you may be stuck with a sub tree at this depth whereas opt would have had the chance for paying one extra in the last step.

34:15 This is maybe what we have done. Um there were these three things. This is part of the green sub tree. Now, up could have paid one extra to visit this guy now and make it the root. And then it's one level higher than in our case. And there's no way with rearranging the red tree. We can't get built the tree into this shape. And then now, of course, I should have split this. And these go here. Now, if my next access is to this orange guy, I pay one here and one extra here. But I have to go two steps down here. I pay zero here to I pay one, but here I pay three. So, this is one more expensive for this greedy future algorithm compared to opt. And uh for a while, people at least say lack the creativity to make make this algorithm suffer more than that. Uh but meanwhile we know it can be much worse. Uh this is still relatively recent. Uh that it's at best a two approximation and also there are sequences where it's way more than m away from opt even though here in this case opt is also high. So it's as a relative factor compared to opt is not so bad but uh it's an additive much bigger than m. So this intuition that the only thing that opt does better than our greedy future would be this kind of getting a a sub tree higher up is not is not the case.

35:56 There's more complicated things going on. Still it seems like a reasonable thing to do if you knew the future. Um and it could still be you could say maybe it's an approximation as an offline algorithm. It can't be competitive because it's not offline, but it can still be close to the optimal offline solution, but much cheaper to compute if you know the future. And again, it's one of those questions where we don't really know anything. Even we can again login approximation is not interesting. Even a balance tree gets that done. Uh but little o of login is already un unknown as far as I know unknown to me whether it's not unknown.