Video 1-8: Randomized BSTs

0:02 In the next section we'll look at a slightly different way to do roughly the same what treaps do, but um it has some subtle different properties. Uh I won't give as much details as for treaps because maybe at some point um it becomes more of the same. But it's not exactly the same. Uh there's there's two things that treaps may leave open uh on the wish list. Uh let me do the second first because it's more more obvious. We have these priorities, then we have to generate, and then we have to store, and they're actually good for nothing. They I mean they keep the tree in shape, but algorithmically they're just there to keep the tree uh balanced. We can't use them for anything else. That seems maybe extraneous or wasteful. And the other subtle property is maybe a kind of a theoretical problem, but suppose you were for some reason very unlucky with the priorities all being weird. Let's say uh the priorities for some reason were all very small and even happened to be decreasing.

1:08 That's unlikely to happen, but if it happens, you're stuck with it because you never change those priorities again. So, you may have some some top part of the tree as a long chain, and because all the priorities are are very tiny, most new keys will just end up getting added down here, or well, uh maybe not down here. Mm, this is ordered by key. Let me revise my worst-case example. It'll be somewhat balanced.

1:50 Uh I think to make it make it really bad, uh not even so easy. Um because the the keys also distribute things a bit.

2:01 I don't know how to um to pin this down better than saying you're stuck with the same priorities. Uh they're probably going to be fine, but what if they are for some reason not not convenient? Uh then you'll never change them ever again if you have a data structure that you use for a very long time. Maybe this is a a problem, maybe not, but it's a thing that treaps certainly satisfy that they don't change the priorities. And as an alternative that uh uses a slightly different randomization uh strategy. Um the key for that one, uh a property that we've used before, is if you have a random binary search tree, among other things, the root is uniformly distributed among all the possible keys. And that's true for the root of the entire tree, but it's also true for every subtree recursively. So, yeah, you pick the the root uniformly, that splits the universe into left and right, and then conditional on that root, that subtree on the left and the subtree on the right again have uniform from their range the root chosen, and so forth.

3:13 So, how about forgetting about these priorities and rather enforcing that this property is always true? That's a bit weird, right? We have one fixed tree. How can we say that uh we're having the right tree with the right probability? Well, it only becomes an issue when you change the tree. So, upon insertions or deletions, we can try to make make this happen. And it's actually not as hard as it may be sounds. So, uh we'll we'll only enforce something new whenever some uh shape of the tree has to change because insertions or deletions happened. I use the reference for this. Uh I'll try to be a bit um more diligent with this in some chapters that are a bit more recent to give the the original citations. Um then also some of the the detailed proofs uh can be found there. What we do for that um for for for making this work, maybe from this formula you can already see if for every subtree we need the root to be chosen with this probability depending on the subtree size, we probably want the subtree size.

4:22 So, we store that. Uh but remember that many binary search tree implementations will want the subtree sizes anyways to do these rank-based operations. So, unlike for the priorities, this is this is not a a wasted space. It may be something we anyways store.

4:43 Now, uh look let's suppose we do a new insertion. So, in general, it may may insert in some some path in the tree. So, here's our new Uh okay, that's not that's not making it a leaf. Uh here's our new element. And now, um there's going to be some subtrees on the other sides of the path of various sizes. Now, we've added the element here because that's where our insertion uh took us. But if this element had been part of the tree from the beginning, there was some chance that it ended up in other places in the tree. Specifically among uh the search path, it could have been that it becomes the root of the entire tree. There's a small chance, just 1 over n, but it it might have happened. Similarly, um for all these trees, if you look at one of them, the subtree size here m, there's a chance that this element would have been the root of that subtree conditional that the rest of the tree was was chosen as it is.

5:54 There would have been a choice probability for that element to become the root here. And so what we do is we go cut top-down and at each point we flip a coin that has an unfair coin a biased coin. At the root it has probability one in N or I guess now I should say um it needs to be the new sub the new size so N plus one. Uh we flip a coin at the root whether this element should be the root of the entire tree. If not then we continue recursively with the search and keep trying again with coin flips on the search path further down. But if we um if the coin flip decides it should be the root then we somehow have to make it the root without messing up the rest of the tree or the distribution over the rest of the tree structure. That sounds thorny but it's actually not because we have an insertion at the root procedure from before.

6:58 And you can analyze that if you use this this split and join for this you don't mess up the random uh distribution of over tree shapes. This is uh this takes a bit of work to go through all the cases and that's why um I'll I'll point you to the paper if you want to read the details that indeed when when you are in this case you determined I'm there's the the probability that this guy becomes the root and that has now happened. Now I have to change change the rest of the tree into one that is conditional on this fact that that new element is the root equally likely or has the distribution that we want from a random binary search tree. Uh and um you can prove that the split and merge procedures give you that if you started with a random binary search tree from the beginning.

7:58 That's for insert. Uh I'll show some some more clean code on the next slide after the rough idea. But you go essentially down the search path, each time flip a coin, and if you have to make it the root of this subtree, you insert it at the root using the same procedure as in the treaps.

8:18 And you can also handle deletions. Um there's no choice what to do with X, it has to go. So, you'll find it somewhere on the on a path. And then it has two subtrees. Now, these have to be somehow joined into one. That's the only option we have. Uh and the only uh choice really in join was which element do we make the root? But we have to do this recursively. And here, if you have these two trees, well, this is already of the right distribution, so its root is uniformly chosen among all these keys. Its root here on the left is chosen uniformly among those. So, if I choose among those two uniformly chosen elements with the right respective probabilities, weighted by the subtree sizes here, that's what what this says, then I'm already good. Then the root is uniform again. And recursively, I get the same uh guarantee for the joint subtree.

9:30 So, let's look at the code briefly. Uh the code again is is is not complicated. Um just to be specific, uh here it is. So, you insert a new element X. Um You draw How do you flip this biased coin? The easiest is to draw a random number between zero and n exclusive. And check if it's zero. I guess this is never going to happen otherwise. You need to pick one out of these n options. That's That's what it says. Mhm. And we want n plus one. Okay, so the code is is broken. This should be n plus one. Because that size is the old size. We haven't incremented it yet. Um And I think my code here never increments the size. So, maybe the fix should rather be that we increment the size now. Okay, so this uh Yeah, update size only recomputes it from the subtrees.

10:41 At some point I actually have to increment something, right? This is This There's no incrementation There's no plus in the code. That's fishy. Um Oh, insert at root does that. Mhm. So, I think it's fine. It's hidden, right? It's in It's It's hidden in here. So, the only bug is the one that I fixed here that the probability should have used the new subtree size. And that's only updated after the fact, so we have to add one here manually. At least then the comparison here makes sense again. Okay, uh edit distance to correct code was small. Um but a bit of a subtle a subtlety.

11:27 Um And you see it's a it's a cute combination of the standard insertion where you follow a search path and the insert at root where you would you stop at a certain point.

11:45 Uh This is copy-paste mistake, right? This is uh This makes no sense. An expectation of all random Okay, forget it. Uh Just ignore that part. I can fix that.

12:15 Okay, this This takes too long. I don't understand why. I'm probably generating a lot of invisible Uh there we go. There's nothing to see here. Good. Uh Deletion uh uses join. I've reproduced the code here because it needs a slight change. Previously, we've I said join uses the sizes. It just puts the larger root up and then we modified it for treaps to use the priorities. Here we modify it again to use um a random choice of the roots. And we take the size of the left subtree, the size of the right subtree, pick a random number between zero and the total size exclusive. And uh if the number we get is on the left side, then we use the left subtree's root as global root, otherwise the right. That's the only change. The rest is the same same code as before. Uh and then deletion um I think there there nothing um interesting happens.

13:35 Uh but here I'm not updating the size or do I? Uh I think here uh it might work because update size then in the next um Okay, I'll I'll think about update size. Uh I thought it's clever to have concrete code, but then you want to get the details right. Yeah. We have at some point we have to update X. It could be that it works out because we always have some null pointer and these are taken account for in in update size. For getting the the uh precise point where we update the size, what you do is uh you recursively find X. And the usual case is this one. Um join might update the sizes already correctly from the recursion. And again using the nulls as the base case. So, maybe it's fine. Um that's the case where we delete the root and the only change really to before was as explained which root to pick.

14:55 Okay. The non-trivial part about the randomized binary search trees is proving that they have the right uh shape distribution. And here I'll just appeal to your intuition that uh things are symmetric and we don't destroy the symmetry in the updates. This is again it is a non-trivial statement that needs a proof, but maybe we've spent enough time on this. So, the the the proper proof is in the paper that the link is linked above. It has a long case distinction, but not very complicated.

15:36 Once we have that, we can again harvest all the results we've proved about random binary search trees. By now, you know this uh at the end of of this section, hope hopefully you even know the results by heart. What is the depth of a random uh node, random leaf? Uh we also have this high probability bound, etc., etc. Um you can also analyze how much uh the insertion and deletion has to modify. So, what's meant by this is um Both uh insert and delete have a a recursive part, where you just walk down a search path, and that is bounded by the height of the tree as always. And then it has the insert at root part, respectively the the joint part, which uh I mean, also is bounded in terms of how far it can go down by the height, but this is the part where we modify the tree, and where potentially we have to pay more to update secondary data structures, and so on.

16:41 Uh and here you can show that in expectation you do just constant work, and it's the very same argument as for treaps. Because again, the tree after the fact kind of gives you a trace of where you've been. Um and the the random the the symmetry from the random binary search tree means most most nodes end up low in the tree towards the leaves.

17:10 Okay. Um Part A, that's uh uh using the results. Yeah, that's that's uh tying it back to the analysis of the treaps, as I said.

17:37 Okay. Enough on standard trees and randomized binary search trees. The point with this second alternative was to show you even for the same goal of of uh forcing the tree to have the shape of a random binary search tree, you can do two fundamentally different uh approaches that give you different randomization, and these are not even all this. I mentioned the zip trees before, which are somewhere in between of the two, if you like, closer to treaps, but um uh try to use less randomness. There's this there's some some design space to be explored. It could be that a a simpler solution is still out there to be discovered.