Video 3-6: Analysis of Random BSTs

0:03 We've left off with the analysis of binary search trees. If you start with an empty tree and then you insert the elements that you have in random order because we're doing everything comparison based, we might as well assume that the elements that we have are just the numbers one up to n. That makes it a bit easier to talk about them. But really uh it doesn't matter because all the binary search tree looks at is the relative uh ordering. So it wouldn't even know what values it really has. Uh then the assumption here is that the inputs come in random order and this is technically speaking out of our control. This is something we have to rely on that the world doesn't conspire against us. But under this assumption we can analyze what the trees would behave like and it'll turn it turns out to be u very close to the best case and very far away from the worst case.

0:59 So we have uh already introduced this notation CN as the um the total cost of searching every key in the tree once. This is also sometimes called the um internal path length. It's not a super telling name but uh maybe you can imagine it's the length of all the internal paths. all the paths that lead to um vertices in the tree or nodes in the tree. Okay. And uh for this CN under this assumption we can set up a recursive equation. Namely we we can observe that the root if the numbers are indeed these numbers one up to n the value and the root is uniformly chosen. That is in this model the case. If you pick a random permutation of of n numbers and you look at the first one, it's equally likely to be any of the numbers. And then subject to this first number being r, you have some arbitrary list of other numbers.

2:08 Let's say concrete example, maybe six is this first element. And you could have um smaller and larger values mixed arbitrarily. That's a seven um two. Well, we got two. Three. 1 2 3 four is missing. 6 7 8 9. Let's say this is our input. Then the six becomes the root of the binary search tree because we insert it first. And now what happens to the other keys is that I'm I'm splitting my input according to whether they're they're smaller or larger. Well, those that are smaller than the six, they form this left part and the others form the right part. And [snorts] now the crucial observation is if you just focus on these these green parts that go to the left and the blue parts that go to the right among themselves. They're of course now different numbers. They're not the numbers one up to something. In the left side they are. In the left most call they are. But in general they are some range of numbers. But you could just subtract three from each of these and then they turn into uh seven 5 4 1 6.

3:36 I messed up right. The four is wrong. That's why the four should never have been there. And I should have subtracted six, of course.

3:53 So what I get if I do this this transformation is again a permutation of the numbers one up to some the size of this thing. And if you started with a random permutation up here then also these filtered out sequences of the green and blue they're still in random order because we have done nothing to them to make them not random. Which means if I now build my search trees recursively from these smaller sequences, I again get the same kind of random behavior. The random tree I get from these two I can attach to the root six. That's what's written here as well. Um it will follow the same distribution. So it will have the same kind of behavior, the same expected cost in particular. I just need to know how big these trees are. And then if this is r then this is r - one here five and here n minus r 10 - 6 is 4. Okay that's why we have this recurrence um split into the two sub trees. What is missing is to explain where the terms come from.

5:03 In in the end I want to sum all of the paths to all the tree all the nodes in the tree. But if you think about what this looks like in some hypothetical tree, say this one, I'm going to have one path for each node in the entire tree. Each visit the root. So I'm going to visit the root 1 2 3 4 5 six times. I'm going to visit this node three times because all the paths that go to this node and its children will visit this node and two and one and one and one. So if I want to set up this recursion, I note that in the root, the contribution of the root to all these paths is precisely n for every vertex in the tree, including the root itself. I'm spending one cost to um walk past this node.

6:00 That's the part and this is independent of what the route looks like. All paths start in the root. And then I have a probability namely the probability for the root having a certain value. So this 1 / n is the probability that root has rank r and with that probability the root has this this rank. So then the sub trees have sizes r - 1 and n minus r. That's where this recursion comes from. And of course I also need a boundary condition. If my uh my tree is empty then I don't have any paths and so the total cost is zero.

6:46 Okay. Now this looks like um a rather nasty recurrence to solve. It turns out somewhat unexpectedly luckily this one has a precise solution. I want to briefly walk you through this one. Um first of all notice that we can uh split this sum into two and really this one and this one is doing the same. They're just summing in reverse. This one sums all the C rus one. So this is from C 0 up to C N minus one. And this starts at N minus one and walks down all the way to zero. So I get twice the same sum. That's this part. That's better. But still it has this nasty shape of a full history recurrence which means that the end term depends on all the previous terms. These are a bit uh tricky to work with in general. But here for this specific one there's a trick and this trick I I think um somebody uh had this ingenious idea how to do it and then we know how to do it.

7:57 I find this is rather hard to come up with but it turns out here you can just multiply this creatively and take differences of successive terms and that kills all the problems. So in two steps first thing is we'll multiply our number by n * cn uh that gets rid of this annoying fraction here. So um uh the n turns into n^2. The 2 / n cancels with the n and the sum is where it was. Now at this point you may note that this this wants to be subtracted from itself because this is uh independent of n. The only thing that depends on n is the upper bound of the sum. So if I take two successive terms and subtract them almost all cancel. So that's what we're going to do. So we take n * cn and we subtract the same thing with n one smaller n - 1 * cn minus one. And if you just plug in the n^2 here becomes n^2 minus the one smaller term. And then the two sums I just copied here one with the original upper bound of n minus one and then with n minus one plugged in it becomes n minus2. And so each of these sumans CK appear once with a plus and once with a minus. Well, except for one, right? The last one. That one's left over. That's why this is the whole sum cancels except for this one term. So we have n * cn on this side, n minus one cn minus one on this side, and this 2 * cn minus one on that side. So we bring that to the other side by subtracting or rather let's put that to the other side.

9:54 Then we have all of these on one side. So this one is uh you have to work out what that is. Uh that I'll I'll spare you the details. You can just multiply out and cancel. So it's 2 n -1 and then we have n -1 + 2 that's n + 1 * cn minus one.

10:14 At this point again you need a trick because we'd like to somehow unfold this recurrence but there's an n here and an n +1 n minus one. There's a mismatch in how the factor in front and the uh argument behaves and that's problematic. But you can get rid of that as well. If you divide by n * n + one, then the n here cancels and you get the n +1 as the denominator. And on this side, the n+1 cancels and you get the n in the denominator. But now crucially here I have n and n+1, n minus one, n minus one and n. These are the same offset. So it's a term of the same shape and we produced some uh nasty term in the middle. But crucially now I can replace give this a new name CN divided n +1 let's call it dn and then this one is dn minus one.

11:19 And so this one translates into this very clean recurrence which now if you use the recur rec recursion again in this term you get another of these terms and they just all unfold. So it's just one long sum of these uh terms here, right? So dn would be this 2 n minus one / n n + one. Now inserting what the n minus one is. I just need to insert n minus one in here. Now this quickly gets a bit annoying to write but in principle is doable. and all the way down until at some point I have to stop because my boundary condition is reached and then I get a a plus zero for this last D0.

12:08 So all that's left from my uh recurrence. Um this is also called a telescoping recurrence because they um you can just insert one into the other. What's left is evaluating this sum. This is uh these terms summed up all the way down. We start with n. If you set k to n, you get precisely this term. And we stop when the last term we get is when d n minus one becomes zero. So we have the last term for n= 1. That's why here k starts at one. Okay.

12:51 Now what do we do with this? Yeah. question. Yeah, I updated them a bit. I'll upload them later. So, this term um in itself is a bit still inconvenient because we have to sum these terms up. Uh there's a general trick that you can do at this point. Uh have people heard of partial fractions?

13:21 So then um you may know that you can rewrite this in a cleaner form. Uh in this case you can split it up like this. In the general case if you have a um a rational function like this and it has certain zeros in the denominator there's a a simple trick um that you can apply and maybe let me show this once here. So the the general theorem which is also on the cheat sheet by the way uh one of the few things that are far down if I remember correctly not that far down there partial fractions. So whenever you have two polomials uh n divided one polomial divided by the other polomial um you can rewrite this as a sum of these simple terms where you if in case the polomial has only single roots simple roots then you get just a um sum of terms of this form x minus the zero.

14:43 So in our case we get the two zeros of the denominator are zero and minus one. So we get um two terms of this shape that have these these same roots and then we have some unknown terms here A and B and we know that this this can be solved by uh the following trick. Um this is this is basically our answer. This is how we want to find these terms and to get the minus1 and the three you imagine you have this equation and we'll have this twice. So let me copy it first. Uh first let's suppose we multiply by k. What that does is it cancels this k and it cancels this k and it puts a a k here. And now I'm going to set K to zero, which means this one just kills this entire term. And here I'm left with a equals this term with K set to zero. So if I insert K to zero, then this is gone.

15:52 This is a zero. So I have minus1 divided by one. So I get from this directly that a is minus1 as as we found here. And the same you can do for the other roots there. You multiply with the other um primitive polomial. So that kills this and this term. It puts the k + one here. Once we set k to minus one, then this just vanishes and we have b equals this term where we have to set k to minus one. Now, and if you plug this in, then you have minus3 here and minus one. So, that cancels to three.

16:41 That's always how you can do this. Uh, it gets a bit more annoying if you have multiple roots, but u here we don't. So, question.

16:58 No, probably not. Um, this one's more of an excursion. If you plug this in here, why it helps to split the sum in this way is that these terms are now much easier to sum. In a way, there's still no closed form, but this sum of the uh reciprocals of the first n integers just has a name. That's the harmonic number. Speci specifically if you sum from one up to n one over k then that's hn the nth harmonic number. Here we have it slightly shifted. We have n plus one um k + one inside. So we start at two and we end at n + one. You can write this as the n + harmonic number and you subtract the zero term the one over one. Which means for our recurrence dn remember this was not quite what we wanted. This was just related to our C for this DN. We now have a somewhat closed form at least assuming that these harmonic numbers count as closed form.

18:03 Uh you can massage that a bit by observing that these two are related. Um specifically the n plus first harmonic number is of course the nth plus this one extra term 1 / n + 1. And you can plug that in here and then you get a a cancellation of the harmonic numbers. So the overall result, the simplest way maybe to write it is two times the nth harmonic number with a little bit of error correcting terms. And that's it. So that that solves the recurrence. All we now have to do is pluck back in dn was uh cn divided n +1.

18:42 So cn is n + 1 * dn. So just inserting this last shape here nicely cancels this fraction. So we get 2 * the factor n +1 * hn and then min - 3 * n +1. This comes from the three and the 3 / n +1 * n +1 becomes a + 3 and you can simplify this a bit and then this is our final result. Now what does that mean algorithmically? Uh for that we need to know how big these harmonic numbers are. Um it's a very standard thing to look at in analysis that people will have seen that these diverge as n becomes bigger. This hn tends to infinity but it does so rather slowly. Uh in particular it's essentially um a good approximation is just the the natural logarithm. You could be a bit more precise, but we won't really need that precision here. Um, one way to think about this is that uh you plot these harmonic numbers sums as bar charts. Then you have here the value one, then you have the value 1/2, then a third and so on.

20:08 So clearly what you're what you're tracing here is the function x maps to 1 /x and we're taking something like an integral here um by a bit um shifting things. Let's let's take the integral here from there up until a certain point. So you can approximate these harmonic numbers with a a bit of a a back and forth shift. So you shouldn't expect it to be precise. But as a huristic argument, [snorts] you should expect that the harmonic numbers are roughly this integral from one up to say let's at least do the right number of bars. If here we had four bars, then probably I should integrate up to this point.

21:06 So 2 3 4 5. And what is the function we integrate? Well, 1 /x, right? And what's the anti-derivative of 1 /x? Natural log. And so that is natural log of n +1 minus natural log of 1 otherwise known as zero. So there you go that it should be close to natural log. And indeed you can make it more precise. It's even asmtoically equivalent. Now with that knowledge we can approximate our our CN this total path length in a binary search tree built from random insertions as 2 * n * natural log n or um by change of base essentially 39% above n login with now log when I say just log I mean base 2 always this lg is log base 2 because computer science everything is about bits um The most natural thing to compare with is is log base 2. This is also from another perspective natural because um this was the the total cost of searching everything once in the tree. If you divide that by the number of searches, you get the the average depth of a node in the binary search tree. And that works out to be 40% above the maybe best option you could think for think of because we already worked out that log base 2 of n is the height of a perfectly balanced binary tree.

22:45 Think look back to the heap chapter. And so if you build a binary search tree by random insertions, you're just 40% worse, which may not be worth the hassle of a balanced search tree if that was all there is to it.

23:06 questions for that computation and again I'm uh because you raised the question I'm mostly showing this to prove the point that you can precisely analyze uh algorithms and data structures. This is a rather singular example where it's uh where everything is clean and nicely done and you should rather um know the consequences for algorithms. Um but I wouldn't expect you to come up with a derivation like this for a new problem. Most of the time they're rather hard to come up with but it's worth having seen one I think because then also you can uh apply better judgment. This is one of the places where you can go to precise constants not just pigo terms.

23:56 Now one last thing on this is uh I started this section um I've seen you with saying that we we want rather bound the heights but we won't because the math there is much much more nasty. If you want to read about it if in case you're curious this is the main source and then there's a follow-up paper. uh the constant works out to be some irrational number 4.3 something natural log n. I think what you should keep in mind is this is something like 2.9 blah blah log base 2 of n. So if you build a binary search tree from random insertions the height is going to be bounded by three log n three log base 2 of n. question.

24:53 >> Yeah, that's um uh 10 million animated slides ago, we had this worst case that I uh had handd drawn last time. This is still the worst case. All of this hinges on the assumption that the insertions come in random order. And if that's not the case, then tough luck. Um the performance may be way worse.

25:14 And that's summarized in this slide. Uh this is always true. We can bound the time for the operations in terms of the height of the tree. In the worst case, that's just linear for the unbalanced binary search trees. If you have random insertions, then things are looking much better.

25:39 Um I should stress for completeness I was very careful to always say random insertions. If you mix insertions and deletions of the type how we did them the whole thing dies. uh then if you added deletions you might even have square root n height instead of logarithmic intuitively because our deletion has this this property of being a bit asymmetric if I'm deleting an an internal nodes I always replace it with the successor and that gives the tree somehow uh hang towards the left so um this is really a bit uh brittle on the other hand it's not brittle in the sense Since that is only an expectation, you can still state much stronger results that the probability that if you build a binary search tree like this um that you see uh say 10 times the expected value is astronomically small.

26:38 But that also maybe more for context than for being part of the exam. all these small print things that of course you don't need to know.

26:56 We've done the recurrence and you've seen asmtoically the uh um internal path length of a binary search built from random insertions is uh essentially logarithmic or n login. uh if you take sum up all the paths um and to get a feel for how well behaved this quantity is uh let's look at some some random samples. So the we look at trees of size nine fairly small and if I draw a random tree it might uh look like this and it will have a certain path length in this case 29. So it's put on let's go to raw at at the x position 29 I put this little tree and if I draw a few more uh you see how they accumulate at certain positions and most of them tend to be close to this um this this yellow this this red line which is the number we computed from the recurrence. Now if you do this for the small sizes of course you occasionally see some deviations uh but we have not seen the worst case yet which would be uh 45 I guess uh the worst we've seen is 40 and we've only seen that once and then most of the trees are even maybe uh below the currently our uh median or our average or mean is below the um theoretical number and if you keep doing like this even for these small numbers again jumps a bit around.

28:40 Uh you see that there's a certain distribution that arises and it's in a way very far on the left. Most of the trees have fairly small internal path length rather balanced. Now if you go to um larger trees say um of size 100 and you draw a few more you see how this becomes a rather distinctive curve it seems to converge to something uh but um now the x-axis is scaled so I divide it by n login um so the expected value should come out at 1.38 and so on asmtoically We're with a size 100 still a bit away from that. Now what I want to point out that this is zoomed in the real distribution the worst case is over here and we've not seen this once and this is for size 100. If you go um let's not use the log plot. This is even even more extreme as as you make N bigger.

29:54 Okay. I mean, yeah, the the animation on the side of course is more distraction than than useful. But you see how with 2,00 if I show the full range up until the worst case, you see nothing. And you have to zoom in a lot before things spread out. All this is uh testament to this statement we had on the slide that with very high probability as n becomes bigger you're more and more sure that you're very close to this expected value if you do just random insertions. Okay.