Video 1-3: Random BST model

0:03 In the next section, we'll look at random binary search trees, which is precisely what I mentioned earlier. We study the unbalanced binary search trees under this generous assumption that the world is very nice to us, namely that it gives us insertions in random order, and that that is what gives us the shape of the binary search tree. Um and the goal will later be to make the data structure behave as if that was the case, even if it isn't the case. So, first we'll see if this goal of having someone of the data structure kind of trying to simulate being built randomly, if that's even worthwhile doing. So, we'll first study binary search trees built from random insertions, and if spoiler alert, we will, we find that these are well-behaved, then it's a worthwhile goal to have a data structure explicitly use randomness to get there. Okay, that's that's the idea.

1:07 And what does random mean? Well, to be precise, um that's where the theory side comes. There'll be a some a few definitions and theorems now in the following. Uh don't be scared, they don't bite. Uh they just want to make things precise. A random binary search tree of a given size is one that we get if we start with an empty unbalanced binary search tree and then successively insert the elements um uh the numbers one up to n in random order. So, every of the n factorial permutations is equally likely. For n equals 3, there's not so many permutations, precisely six, so we can build all of these trees. For example, there's the sorted permutation 1 2 3. There's the reverse sorted permutation.

1:57 There's the 1 3 2. There's the 3 1 2. And 2 1 3 2 3 1. Let's build some trees. Uh and just look at the shape. I'm not going to draw all the uh labels. Here we get one first, then we insert two, so that's a right child, and then we insert three, so that's what the tree looks like. And uh in the drawing before I would have had these indicators for null pointers. Let's not draw them. But you know that they're there. This guy is the opposite. We get the three first, then the two, then the one. So it's a mirror image of this, but they're distinct as trees. Left and right is not the same. Here we get the one first, then the three, and then the two, so we get the zigzag. And here it's the other way around. Again, the two mirror images. Now here happens what uh comes the fun thing.

3:00 Both of these give us the same tree. The balanced cherry. Effectively uh effectively called. Affectionately called. So if each of these six permutations originally happened with probability 1 over 6, there's only five different trees. These happening with probability 1 over 6, but the other one with probability 1 over 3.

3:34 And uh note how the single balanced tree among those five is the one that gets a larger probability. That's already a good indication that things are going going well. Right? Yep.

3:51 These are all equally bad. Three. Yeah. One with the depth of two is only one of three times. Ah, good points. That is totally correct. Um, I think it's an artifact of three being very small. Um, if you think about it, these are mm these are essentially linear chains. And the number of linear chains as n becomes bigger is relatively small because to get a linear chain in the the strict sense to have the very bad case, the worst case where the tree is is one long linked list. Uh, in each step, you only have two options. You can have the the minimum of the current thing or the maximum of the remaining uh set of numbers. So, you can go back and forth. So, it's a like such a a funnel. And that could be what the tree looks like. But, there's only two to the n by and large of these trees because you have a choice whether you pick the min or the max in each step.

4:58 As n becomes bigger, there's way more trees than two to the n. Not something I wanted to get into at this point. Um, but as a as a quick one just as a as a remark that what we see with n equals three is a bit unrepresentative. That's the number of maximally unbalanced trees. The number of binary trees on n nodes, does anyone know?

5:42 Is uh the nth Catalan number. Does anyone remember the formula for that? And that is that's the precise formula. Now, if you're uh a combinatorics person, you'd say, "Joy!" >> [laughter] >> But as a computer scientist, how much bigger is this than that? It has to be bigger because these are all binary search trees and binary trees. But how much bigger is it? Huh. Asymptotics to the rescue. Uh I'm not going to remember the asymptotics, the precise asymptotics, right? But it's in a weak sense closer to 4 to the n than any other exponential. It's a bit less. It's 4 to the n divided n to the 3/2, and then there's some constants involving the square root of pi. >> [snorts] >> Uh Again, if you want to see Where did we do this? Um Maybe advanced algorithms touches on it a bit. Uh At some point, I'm I'm going to do a lecture on how to get to these numbers.

7:05 The point here is just that it's way bigger than 2 to the n. So, the probability of this maximally unbalanced tree is dropping like 2 to the n almost. Very unlikely. Now, of course, you will say, "Hold on, that's only the most extreme case. There's a lot in between." And that's right. Okay. But for n equals 3, it looks like these are 2/3 of the cases, and they're for larger n, there aren't.

7:37 Um Yeah, that is what we mean by random binary search trees, uniform over the n factorial permutations, but then you build the trees. Now, if you compare this number to n factorial, that's another huge step. n factorial way bigger than this. Okay, while we're here, what's a good approximation for n factorial? Stirling's formula. Remember? Uh again, I'm going to do just the very rough one that I can remember from the top of my head. Something like n divided e and the whole thing to the power n. And then there's again funny uh additional factors like this. But the point is it's not even just exponential, it's factorial. Uh it grows more like n to the n than a constant to the n. If you uh uh close both eyes. So, again, much, much more uh variability, which means as n becomes bigger, we'll have some of these trees that are generated by a lot of different insertion orders.

8:51 And this example already shows you why. Once the two here is there, the order in which you put things in the left and the right tree doesn't matter because they're separated at the root. If I put the one first and then the three or the other way around, it's invisible to the tree. >> [snorts] >> Oh boy, that was a bit of digression. Um I hope it was useful. Uh let's first see that this model even matches what we wanted initially. Um as a little statement, if you take a tree that is a random binary search tree over n keys, is it correct that if we add another key, n n plus one, that we then get um a random binary search tree a random BST over n plus one keys. Because here what we mean is we fix the number of keys up front and insert them in order. What does that mean if we do it step by step?

9:54 Uh Fortunately it has a well-defined meaning. It just says if you have n keys currently let's maybe again draw the example for n equals three with some Uh let's do one of the not so balanced trees. And this time I'm going to add the uh exact values. Um I'm going to add the I'm going to number also the leaves. Mm.

10:38 And there's always n plus one gaps between these n keys. And now I'm going to pick one of those all with equal probability. Then the result is a tree that's one bigger and has the same shape as if it was built with this random permutation of the keys right from the get-go. Okay.

11:04 To formally prove this you can do a bit of combinatorics. Uh we have two sets. We want to show that they're uh that they're the same and even have the same distribution. We'll show that there's a bijection between the two. Um the insertion order for generating this this larger tree is in bijection with permutations of the keys that we have at the end. By definition that's just the insertion order itself. Uh and that can be put in bijection with inserting the first n keys. And then the last value in in this range, which is the positions of the the leaf that we pick to add the new value. Now, if we do this here, say we decide this is where we insert, then instead of the two, let me copy this, uh, now we'll get a new node, new internal node. But that should now be the formally where where is that should now be the three.

12:08 And what was formally called three is now suddenly called four. And this also needs leaves. And these have to be again two, three, so this needs to be renamed to five. So this insertion changes the labels of some nodes. That's inevitable, but it doesn't change the shape of the tree other than that it adds this new node. So we need to mimic in this bijection what happens here. This last value was this leaf that I picked, and that's a number in uh, I wonder if I was consistent. I think the zero is what we later use. Mm, then maybe here it's rather a value in zero up to n. And we increment all the values to the right of that all all the bigger ones, we increment by one, and then we get a new insertion order. That's the one we could have used to build this tree from the start. If we didn't do it step by step.

13:11 So here's an example. We have first the, uh, insertion order here where we have the the three separated out. Um, so this is the insertion order originally where we have the numbers one up to seven, each occurring one time. And I've just decided to single out the last one as that is the last one. That's why there's this vertical bar. And this is in bijection with having the same permutation, but everything that's above the three here is is reduced by one. And we have the same three. These are the same because I can add plus one and everything that's bigger without losing information. >> [snorts] I've just defined a model of generating random trees. And it happens to be the one that we want, even if we build it step by step. That's all that this lemma is supposed to tell you.

14:29 Well, the the notation here this this notation means one up to n plus one, or in other words uh one to right, that's the more standard.

14:41 And here's the zero not included. That's the Okay, it depends. It's a definition. Uh depends who you ask. I think it's somewhat standard that the zero is not included in this one. Um and here the way I label them, you would want to start at zero. It doesn't affect the bijection, of course, if you rename the things accordingly, but uh Yes. And let me let me peek forward Yeah, I think this is this is one of the things where um I modified earlier slides to be consistent with some of the books I build on. And so that might be a mistake I copied. Sorry about that. Okay. Other than that clear. Um nothing deep going on. >> [snorts] >> Uh Before the next statement which is going to be this one. That we can also build these random binary search trees with a slightly different random model that is some sometimes more convenient so I wanted to let you uh let you have this knowledge.

15:56 Uh you can pick pick uniformly distributed real numbers between 0 and 1. And pick n of these identically distributed and independent. Then uh you insert those into a random binary search tree. You get the same as if you had used this random permutation of the numbers 1 up to n. Basically, the reason is just that they're indistinguishable if you just do comparisons. And the probability that two random real numbers are equal is zero. So you're really essentially never going to see this. Okay? Now to make to make this statement make sense uh I thought it's good to define this and this. Maybe even this. So uh I inserted a few slides that cover this uh about um probability theory. This is hopefully just a refresher. But maybe it's good to just uh recap the terminology there.

17:04 Um we have some probability space which is a ground set. That's the things that can happen. Um and then there's a probability measure of the the probability we assign to sets of that. And an event is uh I think think of F in the discrete case uh in the discrete case F is just the subset the power set of omega.

17:34 Uh no. Uh sorry. Two to the omega as power set. Sets of sets. That's good enough. Forget about the measurable sets and so on. This is uh for the general definition is important, but we don't need that. And then an event is just some some subset. So, maybe omega could be the six outcomes of a of a standard die where you have the numbers one up to six. And then maybe uh an event could be I get an even number. >> [snorts] >> Um I'll use this probability P is uh stands for probability. And I can have the probability of some event. Maybe for the example with the die, the probability to get an even number is is exactly half if it's a fair die. Uh we can have the counter events, which is the uh complement set. It's one minus the probability of the other. Standard stuff. Um the union bound is often useful if you uh take the union of several events.

18:54 You cannot exactly say what the probability of the union is, but you can upper bound it by the sum of the probabilities of the uh subsets. Um and we will need independence. Remember there was this IID popping up. Um a collection of events is independent exactly when their probabilities factor. So, the probability to see all of the events happen at the same time, that probability is the same as the product of the probability of the individual parts. That's the definition of stochastic independence. You've seen this before, right?

19:33 I hope. If not, then this is a bit rough, but in principle, this is is all on the slides. There's not much more to it. Mhm, but it's a bit rough if you've not seen it before. Um, I don't think we need this necessarily right now. Uh, this was events. So, sets of things. A random variable is something that maps this abstract space of potential outcomes to numbers. We'll usually work with uh, normal numbers, whatever, uh, reals or or integers. Um, so, we can have indicator random variables, which are one if the event that they asso- associated with occurs, and otherwise zero. Um, I often write these as this Iverson bracket notation. So, this uh, some conditional in square brackets means one if this condition is true and zero otherwise.

20:41 That's That says else. Oh, come on. Not sure if we need these, uh, cumulative distri- distribution and probability mass function. Um, what we want is also independence for random variables. We had it for events. It's essentially the same property that's uh, carries over. For discrete variables, it's the easiest to state that the probability that two random variables jointly assumed some values just factors. And then last thing, IID independent and identically distributed sequences of random variables means that they're all mutually independent and they have the same distribution. I use this equal D to denote that two random variables have the same Uh that just means they have the same cumulative distribution function. A typical thing in algorithms is for randomized algorithms, we often assume we have access to some some random generator, something that generates random bits and it could be just flipping coins. We assume that one coin flip leaves the coin in the same state as it was before. So, if you flip it another time, the first and the second outcome are independent.

22:03 Question? In In practice, how good does the randomness have to be for these data structures to work as we want to do? Yeah, it's a very good question. Uh question was how good does the randomness have to be for the data structures to work? Uh the answer is it depends. For some, uh you indeed need a lot of actual randomness. Uh and for others, um the the typical phrase is uh is this one. Um it's often good enough if say the coin flips are K-wise independent means if you pick any any or say five five-wise independent. That means if you pick five of the coin flips, they're perfectly independent. You wouldn't be able to distinguish them from perfect randomness. But if you take six or more together, you start seeing patterns. Many data structures have this property that a certain K and then K wise independence is good enough for the guarantees we want to prove.

23:08 I remember that there's a a theorem about quick sort for example that if you choose the pivots randomly it's good enough to have I think five wise independence or something of that sort. Don't don't ask me about the proof for now. That's that's the kind of thing one can prove.

23:36 Usually we'll ignore that part for the analysis first and assume perfect randomness. And then as a second step you can analyze in your analysis kind of meta-analysis in your analysis what did you actually use about the sequence of random things? And oftentimes it just pops out that you didn't really need full mutual independence. In the case of quick sort is a bit more work.

24:01 Okay, with this terminology at least you can make sense of this statement. Uh again the the proof is very simple that if you just do pairwise comparisons these real numbers behave just as if they were the numbers the integers one up to n. And so of course they are the same. The reason why this is a bit more convenient is that you look at the next insertion they're all independent. So any value between zero and one could be the next insertion. And you don't have this annoying renaming of things. If you keep the actual real numbers as labels in the tree they don't move. They just stay the real number they are. That's why this is sometimes a bit convenient more convenient to think about.