Video 2-2: Move-to-Root Analysis

0:03 In the next section, let's look at how well move to root does as a heuristic in at least one specific case. It's actually quite successful. Uh and the the model this is also from the original publication of the heuristic. Uh maybe I should say all all that's following is is from this paper. They've done it all. They've analyzed the heuristic and they also pointed out its flaws. They were extremely honest about this. But nobody knew at that time, this is almost 10 years prior to the splay trees, nobody knew a better solution. So, this was uh as far as people got at the time.

0:45 So, the precise model here is that we assume we access these uh a fixed set of elements. For now, there's no insertions and deletions. Not because they're hard to deal with, but um it makes the analysis easier or cleaner. So, a fixed set of uh keys, so we might as well call them one up to n, even though in in reality they can be any objects. But let's say these are just the ranks of the of the keys and then it's it's easier to call them just the with the integers. Uh and the uh accesses for these elements are drawn according to the some fixed distribution. So, each of the elements has a probability to come up. And every access is independent of the past. This is still a maybe a fairly tame model because uh there's a lot of randomness in it. And in a way, it's not completely separate from what we've looked at for random binary search trees.

1:37 But if you skew these probabilities heavily, these could be exponentially decaying or so. Which would mean half of the time you touch, say, key one. And a quarter of the time you touch key two. So, these can be very extreme. Right? You the um the best move to front lists, for example, if you have keys that exponentially decay would have a constant expected search time. Right? Because uh So, extreme case just to point out uh how things can go. Um you say that's two to the minus I. And I'm going to ignore that this doesn't sum to one. Okay? So, the last the last one has to have two to the n minus one. Minus >> [snorts] >> Uh then it sums to one. So, they all are regular. They're just decaying as powers of two. The last one is the same as the second to last. Clear? Uh then what's the um even if you had a linked list with the elements just in sorted order, right? One, two three, four.

3:00 What's the expected cost? Just to motivate why this model is still similar to random BSTs in the sense that there's independence, but also can be very very different. Well, the expected cost uh is the sum over the values that we access, something between one and n. And I have PI and then oops, the cost in this list of accessing element I is following I or I minus one pointers, depending how you count. Okay. Uh let's say I then is a Hm, let's say I minus one. I think it it indeed works out even nicer. So, if we insert what we have there um and let me be a bit lazy and just pretend we keep doing this until infinity. So, um I don't have to deal with this uh extra case here. Then that's two to the I times I minus one.

4:11 Uh and this is this converges to a constant. Uh one way to remember this um you can of course go to the TCS cheat sheet that everyone knows, right? Uh I have this open because I was showing the undergrads. Uh there is some formula for this. Uh for the finite case, but here uh the the unbounded series is even easier and you see it's a constant. There's no n in there because uh it just converges.

4:46 You're counting the amount of pointers, so do we Yeah, here I'm counting the number of pointers I have to follow in expectation. That's right. Uh there's a cute trick to remember this formula. I don't know if you if you know or if you care. Uh if you have this I greater equals zero C to the I, this is one over one minus C. The mother of all series, this one you probably want to remember by heart or you there's also a derivation for that. Uh but you can take the derivative with respect to Z on both sides. And then um so, on both sides you do D DC. Uh then what happens on this side is that you get a a factor I in front.

5:39 And here you take the derivative of that. Well, that's annoying. Uh that's one minus Z to the power negative one. So, you get a minus one in front. Uh that's the the outer uh derivative and then the Sorry. Minus one times one minus Z to the minus two and then you have the inner derivative which is uh negative one. So, you have this one over one minus Z squared.

6:13 Come on. Uh and then you can you can insert Now, here you see this um slight mismatch. There's I and I minus one. That's why the cheat sheet had this correction factor. You multiply both sides by Z. Uh we would have to multiply by two Z Z squared. Either way, this is going to be some constant, right?

6:41 And I don't really care about the exact number in this case. My point here was only to make the case that this model is indeed potentially very different from uh having a uniform uh access probability as in the previous case. Remember random binary search trees, this model corresponds to this this IID model if you have uniform distributions. That's the same. Um I'll say more about this uh in a bit. Okay. That's for lists. If lists can do constant expected access time, surely trees can do constant. Because any list is also a tree, even though it's a kind of stupid one. So, the trees will be even better.

7:31 Uh precisely, if you're given some tree, you can easily specify what the expected cost is. Again, um I I I guess I delegate what depth means. I think depth for me is always counting edges. So, I'm counting following pointers. You could also say it's a plus one for doing comparisons. Uh they only differ by this plus one. Um Got to be careful if it matches the splay tree part. Uh but say here um we count the depth. Then it's just this expected value. Now, if you know all these probabilities up front, you can once and for all find the best possible binary search tree that minimizes this quantity. And in general, this is there's no simple heuristic or greedy heuristic that gets the optimal tree. So, the only uh solution with an asterisk, the in most cases only solution we have is is use dynamic programming. Where you fix the root and then the left and right subtree are done as an optimal solution of the subproblem.

8:40 And dynamic programming just essentially uh brute forces the possible choices there. But you always find this static optimal tree that way. That's one option how you could serve these keys. If you know the probabilities up front, you can use that. And um maybe move to root is similar to that, maybe not. The thing is that move to root is um has more power, right? It changes the tree over time. Whereas this static optimal tree uh it's only optimal among all the static trees. If you have to fix one specific tree and not change it ever, then that's what you can find with dynamic programming. Uh there's a little bit known about the cost of this optimal tree compared to um what you can get from these probabilities or as a function of these probabilities. Uh specifically, if you say uh C opt is this cost of the optimal static BST.

9:45 I wonder if this is this must be comparisons. So, I guess here it should be a plus one. Of course, um this is just a a plus one outside. This doesn't really affect anything. But to make make that formula true, I think you need the plus one. So, you can sandwich the optimal cost of this optimal static tree between essentially the entropy plus one and the entropy minus a little bit. And where H is is the entropy of this random distribution. The amount of surprise that you get when you see one of those keys. Uh or if if you don't get any intuition from what I'm saying, there's the formula and you just plug it in. So, in particular for the extreme case of the probabilities we've looked at before, uh right, the um exponential decaying ones, the entropy is also a constant. And funnily enough, it's essentially the same formula, right? Uh because log of one over PI is two to the is log of two to the I, that's I.

10:56 So, the same series for our case of PI is two to the minus I. H is essentially the same same series. And is again a constant. Whereas in general, um the entropy, as you may know, can grow up to log n. So, it can grow with the number of different options you have. For this very skewed probability distribution, it's constant even if you have an infinite number of outcomes. Um that's the range that it can be in. So, H can be up to nothing.

11:39 Or it can go up to log n. Okay. So, we roughly know how well this optimal the static optimal tree is. It's always at most log n. So, we're never doing worse if we use this optimal static tree than using a balanced tree. Well, that's good, but also kind of obvious because the completely balanced tree would have been one choice, and the static optimal tree has to be at least that good. All right.

12:18 What can we say about our um move to root in this model? Um I skipped over this this slide with this uh comment. Uh for for people who have seen some of these optimal binary search tree things, uh and also the um this heuristics that give you not the optimal tree, but um a tree that's close to optimum, but is much cheaper to compute than this dynamic programming. Uh same what's behind power sort. Uh here I'm uh taking the depth of the internal nodes of the binary search tree. You get a much simpler bound in terms of this uh entropy if you look at the depth of the leaves, the external nodes. So, if I'm accessing the the leaves of the gaps between keys with certain probabilities QJ, uh then the expected depth of these leaves is sandwiched between H and H plus two, and that's it. There's no weird minus log H and these slightly awkward terms where you wonder where these come from.

13:26 Uh it's just an artifact of the analysis. I think this is um not very intuitive. That's the kind of cleaner bound, but it doesn't match our case. We want the searches the accesses here are going to the keys, not the gaps. So, this is this is the bound uh we should compare with if if we care about the details. So, back to move to root. Uh Move to root, if your accesses are coming from such a distribution, so fixed distribution over the keys and all drawn independently, then um the following happens. Uh if we let this run for a while, and uh call this this after some time, we stop the heuristic and look at the resulting tree. And we look at two nodes I and J, and say uh for now that I is is smaller than J, then this the Okay.

14:37 This node I is an ancestor of J. So, there's some path down. I is to the left. If and only if we can precisely characterize when this happens, if uh the most recent access to this node I came after the most recent access to anything here in between from I up to J including.

15:03 And something similar happens uh if um I want J to be the ancestor of I, then J has to be touched after any of these keys up and until J excluding. Why is that the case? Um Let's uh sketch this at least. Uh we basically just show the two implications. Um if I If I is an ancestor of J, I'm I'm going to focus on the first part only. So, I ancestor of J.

15:46 What does that mean? Um I'm I'm running the tree in the move to root heuristic. So, for that element I to be moved up, it has to have been accessed. And uh if by assumption and by contradiction, any of the other uh keys would have been accessed after I, well, it would still be higher up because they would have been rotated past I.

16:36 Well, and then the other direction, um if we had some accesses to all of these elements, but then the access to I came last, then at upon this access to I, we move it to the root, and so it moves past all of these and ends up somewhere uh as an ancestor of J.

17:38 I wonder if this if and only if needs an extra strength thing. What if uh so, it's it's clearly the case that I is above all of these. Um But could it be that some element in between is higher than J? And so, well, okay, still still I is an ancestor of J. So, the way I've drawn this here, it may look like all the elements from I plus one up to J are on this path. That's of course not true. They can be down in in some subtrees here. So, we don't really know without looking closer which elements are on this path from I to J. Uh but clearly there's some path to J. And uh it may go back and forth a bit. Uh and some elements might maybe hanging down, but they're all descendants of I. Okay.

18:32 That's convenient because that means we can really precisely say how this tree looks like, at least after this move to root has been running for a while. And by running for a while to make that precise, we need to assume that every key has been accessed at least once. The initial tree could be arbitrary. There's no a priori we don't know uh what tree we should start with or what tree we uh we initially get. But after every element has been touched once, the past about this tree is essentially lost. It's a it's completely forgotten. And the reason is is this theorem. For any element, you have one of these cases, and that tells you the ancestor relations. Um Let's recycle the notation we used in the previous chapter, this AIJ is this indicator random variable for the fact that internal node I is an ancestor of internal node J. Um then from the fact here from this lemma and from the probabilities of the accesses, we can uh evaluate what the probability for this event is.

19:42 Uh let's focus on on just this case. The other is symmetric. I have conditional on the access being chosen among the elements I to J I have probability PI divided the sum of these probabilities as the probability that I is one singled out of these axes. In the random BST case, this was insertions and it was all in reverse, right? The one that got inserted first was the one that ended up as an ancestor. Now here it's the opposite, the one that got touched last because then it's moved up is the one that ends up as the ancestor. But it's independent, so this ordering, this reversal is not reflected in the probability, it's the same.

20:34 So the the only thing that changes here is the that if J is smaller than the sum summation here goes the other way around. Okay? But it's it's a very simple fact. Um the ancestor relationship depends on just the slice of keys from I to J or from J to I and which one was touched last. Okay.

21:05 Uh with that we can precisely specify the expected cost of move to root. And you'll see it's uh it's kind of surprisingly similar as surprisingly simple. So C MTR MTR for move to root, right? Um let that be the expected search cost. Again, after this has been running for a while, so I'm assuming every uh key has been accessed once. I think um always this is our assumption here.

21:50 Otherwise, it's just not clear what uh what the tree should look like. Um and we maintain this tree under the move to root heuristic, well then uh we can write the expected cost as as this beautiful double sum. And in a moment it will make a lot of sense why this is the right thing and not obvious, but you can upper bound this sum in terms of our entropy of the distribution.

22:17 H was just this uh which was tightly connected to the optimal static tree. And that's why um from this this last part you get this this uh summary statement. Apart from this factor two times log natural log of two and this is our famous 1.39 that we've seen a gazillion times. Uh apart from this constant factor forget about the plus one uh the cost of our move to root heuristic if it's been running for a while is the same as the best static tree. By the way, this says a lot and nothing because we're comparing against a static tree which is weaker because it's not changing the tree, but is also stronger because it knows the probabilities and is expensive to compute. But that's what we get. Uh but I want to prove this before we move on because I think the the derivative the derivation is insightful um also for what follows. So again, we write um this depth and let's pretend this counts the number of comparisons.

23:41 So in my earlier notation, I think it's plus one. But again, this might just be the plus one out there. So uh we can rewrite the depth of a node and here really it is um the number of nodes uh at the plus one. Uh so this yeah. It's number of comparisons. Sorry about it being inconsistent with what depth means. You can count vertices or you can count edges and different people do different things. Um it would be cool to be consistent. >> [snorts] >> Here we count count comparisons, so vertices. How many uh elements are there that I compare I with? There's some some root then I'm following some path down to this guy and there may be a few vertices on this path that I have to compare I with.

24:44 How many are there? Well, they all the ancestors of our node I. So it's all the J's that are not I that are an ancestor of J of I. Remember this AIJ was a proper ancestor, so I itself is not counted. That's why we have the plus one because if I search for this I in a binary search tree, I have another comparison for ah, I found it. The kind of it final equality comparison. And these guys we know from the previous lemma, we know what the probability in move to root is for these. That was precisely this uh PJ over the sum of these.

25:28 Okay, uh I'm splitting the sum first. Easy peasy. Now we insert. And here um this this alone, right? It's from the previous lemma. I said it verbally, but let me write it down.

25:47 Is this part? And now um by pulling the PI into the sum, you see this nice symmetry. You have now the numerator PI times PJ and the denominator is the sum of everything up in between including these two. Um and you sum this up over all combinations of I and J not being I. Now you're double counting every combination of I and J. Um so we have a factor two pulled out if you only go over the pairs where I is less than J. That also means I don't have to do this case distinction from above here. Here I needed to distinguish whether I or J is larger or smaller.

26:35 And that proves the first part. I think it's a fairly simple and clean calculation. And it's in a way we shouldn't have expected necessarily to find a precise and such simple formula for the exact search cost of this slightly weird model. I always find this um kind of it's not clear we deserve this. But here the universe is nice enough. Um the second part this is kind of um more an exercise in creative uh inequalities and analysis. But I think it's so cool and elegant that I want to show you. But that part you can maybe if you forget is is not as bad. It's a trick uh a trick due to Kurt Mehlhorn, famous German algorithms researcher. Um and uh without much motivation, let's define this abbreviation for essentially our probabilities with only one uh in the numerator, but then the reciprocals. So delta IJ is just this thing, the fraction on top I have PI up to PJ summed up and I divide by PI.

27:47 Then I observe just from the formula that uh delta one delta II I have only PI on top and PI at the bottom, that cancels to be exactly one. When I um make J bigger, I'm including more and more things in this sum here while leaving the denominator the same. So these things will get bigger. Um how big? Well, the last one sums up up to PN. But still the numerator is part of all the probabilities, so it's at most one. It's exactly one if I is also one, but in general, this is at most one. So I get this upper bound, easy. So why is that useful? Uh now comes the the creative rewriting trick. That's the formula from above. Uh the only thing that happened is that I wrote written this as uh two nested sums again and pulled out the one um PI that doesn't depend on J. Now this looks eerily similar to this with a bit of shift in indices.

28:56 Uh but we're going to rewrite it in a very funny way. Namely as as this. So dividing by delta IJ that essentially gives gives this thing. Um Let me let me recalculate if that works out to the Ah, it does, but it's I think it's hard to justify forward why it's correct. But if you insert, you just find it is correct.

29:34 So what do we have? Uh On the top, I'm taking the diff difference between two um adjacent Let's just do it. I mean So I have this PI up to PJ.

29:51 And I'm subtracting the same thing stopping one early. So, here we might as well split one. Okay. Getting a bit too um messy. To make it extra clear, let's split one more off. That's the top part and then the denominator is the same as this.

30:27 Now, I can pull these on one fraction, right? And then, of course, all that's left from the numerator here is this PJ. This and this cancels. So, I'm left with PJ / PI. And here I'm PI to PJ / PI. So, this also cancels. Uh which means I'm left with precisely where I started. Amazing. We've run in circles, but um that's uh proving that these two things are the same. Now, why on earth do we do this? What is the point with these deltas? Um now comes the the real trick. Whenever you have uh two numbers A less than B, you can cleverly rewrite this thing, which is in other words, B - A / B, right? If you put this as B and this is A. Uh that's a bit like an integral over a constant. Precisely is this integral over a constant 1 over B. Well, and uh because 1 over B, that's the smallest uh value of the function 1 over X if you take a go from A to B, you can upper bound this by the integral over this function 1 over X.

31:51 Right? So, this is uh I mean, maybe in pictures, right? If you have A to B, your integral will be this if that is 1 over B. Now, if you take this function uh 1 over X, uh maybe I should say 1 over B on this side. The function 1 over X will look something like this. So, your integral is this part including this extra little triangle on top.

32:21 Uh that's the part the integral of 1 over X DX from A to B. Uh that's certainly more because here I'm just using the smallest of the function values. Again, a lot of true statements, but it's not clear why this is helpful. The point is if I'm upper bounding this part with this integral, look what I've done. Um this sum now sums up chunks or your slices of an integral where each one starts where the previous one ended. I'm going from delta I J - 1 to delta I J and then the next one goes from delta I J to delta I J + 1 and so on. So, I can combine these all in one big integral, which goes from well, smallest value is delta I I. If I put in this, I can + 1. And the last one is delta I N.

33:21 Now, this is an integral that's actually not hard to compute. The antiderivative of 1 over X is the natural log of N, natural log of X. So, here's the the definite integral you can rewrite as this. And all that's left is inserting. So, uh this is rewriting the integral. And then I'm using our bounds from above here.

33:49 And it it magically pops out to be precisely the formula for the entropy. There's one of those cases again uh coming up with this derivation uh not so easy. Mm. Following through the fact that it works is not too hard to check. Clever clever little trick. Okay. Maybe you found this enjoyable. I kind of enjoy it. So, what have we learned? We can uh upper bound the cost of the move to root heuristic as a constant times the entropy. And that is essentially the cost of the optimal static tree. So, move to root is not doing so badly.

34:37 Now, let me give you an argument why we maybe shouldn't be so impressed. Um the fact is if you take a good old unbalanced binary search tree that does nothing, so our uh plain vanilla model from from the last section, uh and we uh build it under this IID model as opposed to a random permutation, we get essentially the same result. Now, I should I should uh say what I mean by this because normally if we have a binary search tree, we assume that there's no duplicate insertions. And indeed, what we do here is uh when an element is already in the tree, I'm just ignoring that I'm trying to insert it again. This is This is a reasonable uh practical choice as well. If you're building a dictionary with a binary search tree, you would also say there's only one key or one one node with for any key. And if you're inserting the same thing again, it's an update of the map. It's a put operation.

35:37 And you would replace maybe the key the value associated with the key, but the key is only once in the binary search tree. I just wanted to be extra clear that that's what we're doing. So, the the random model we could compare this with is again, probabilities for the numbers 1 up to N. I build an unbalanced binary search tree initially empty where I'm ignoring duplicate insertions. And I keep building I keep adding to this tree until it no longer changes. Eventually, I've I will have seen every key in this interval and then the tree cannot change anymore because every any further insertions I'm ignoring. Okay? So, model clear or you need an example?

36:27 Now, you can do a tiny one with just uh three keys. I suppose N is N is three, so nothing more happens. And this is the random uh order in which I I uh insert the elements. I'm starting with the root one, then the two I can add chunk. Then I get another two, nothing happens, another one, nothing happens, then the three. There we go. And from then on, nothing will happen if uh N is three because every element is already in the tree. Now, uh what distribution over shapes do I get for the tree here? Well, that depends on these probabilities, of course.

37:13 But it turns out it's the very same thing as we've had for move to root. An element I or the the node with uh I is an ancestor of some node J with precisely the same reasoning as in binary search trees, uh random BST case, if this element I is inserted the the first among all the keys between I and J. The probability for that to happen is precisely PI over P1 up to PJ. It's kind of rejection sampling. I'm uh I'm inserting a new key, two options. It's from the range P uh from I to J. Then, with probability PI divided by this, it's uh the key I, otherwise it's some other key and I I don't get this ancestor relation. If the key I'm inserting is not even from the range from PI to PJ, I'm just ignoring it. And that contributes nothing to this probability of the ancestor relation.

38:20 So, very same thing as before. And hence, literally the same analysis shows this unbalanced BST also has expected cost, same same thing as before. So, maybe move to root isn't as magic as we were hoping. At least it hints at a problem, potential problem, uh with these unbalanced BSTs, if indeed the uh insertions come in this nicely independently chosen way, then it's I seem to be doing fine. But if someone conspires against us and somehow makes the insertions come in an unfavorable order, then we're screwed. And it seems move to root may suffer from the same problem. Um and indeed it does. Um Uh someone yesterday pointed this out immediately, so I thought it's a good exercise problem. Uh the statement is is given here, so um there are sequences of requests of of accesses in a move to root tree. And you don't even need a lot. You can have essentially as many as there are uh keys in the tree.

39:33 And the amortized access cost is still linear. So, amortized cost means some of these accesses might be cheap, but if you take the over n accesses, the total cost it will be something quadratic. So, if you average over the accesses, you're you're back to linear per access. And that's of course very bad because it means the tree is completely degenerate. And move to root seems seems unable to escape this this fate. And you said that our whole analysis currently can't fail on that we access every element at least once. Yeah, I guess um It's in our favors when we don't access one element.

40:24 It's just not clear where it is. Uh it depends on the initial tree. You can replace the assumption that we touch every element at least once by some assumption on the initial tree. Then I think you get some some result. The the magic of this very clean formula here, this one, is that you can precisely give these probabilities. I think for that you need some some assumption one way or another. I don't think that's the bad part though. Um the user usual scenario is uh I guess this the question is how do you even start? How do you get with this tree started that you do move to root on? You probably build it by insertions and follow the insertions with some move to root step or so. So, essentially some insertion at root or So, maybe this is is not even an assumption that is problematic if you were to use this as an actual data structure where you build it from scratch.

41:19 Uh it just makes the analysis cleaner if you fix that up front.