Video 1-2: What's wrong with BBSTs?

0:02 It looks like uh case closed. We have defined an abstract data type, the uh dictionary and sorted dictionary. And we found uh a data structure, the balanced binaries, the augmented balanced binary search trees, that solve all the operations in log n time, which is pretty good. You can even say uh in the comparison model where all you can do is compare keys pairwise, that's even the best you can you can hope for. So, aren't we done? What's wrong with that solution? What's wrong with that solution is just that it's annoying if you actually implement it. It's nothing that wouldn't work. Most languages, except Python, have a balanced binary search tree as part of their standard library, which shows it's very doable and they work well. However, even a um for my taste, the cleanest solution I know of either AVL trees or red-black trees is the one from from Sedgewick and Wayne, from the the red algorithms book, if you know what I mean.

1:10 Uh the original full code is 750 lines. If you If you take out some of the comments and some of the additional operations, the core that you definitely need to keep a tree balanced is still this too small to read part that takes essentially four screens of text. And that's because you have to distinguish a couple of cases. There's the left rotations, there's the right rotations. In case of the red-black trees, you have these color flips. Upon insert, there's various different cases. Delete is even worse. So, if you wanted to memorize, say, this implementation, say uh you know, data structures to take on the on the desert island uh with you, yeah, that's not a great choice. And it's not even that the cases are so super intuitive and uh easy to remember. They're kind of annoying. You have to learn by heart what they all do. Uh I haven't even included the rank-based operations. So, really not that great.

2:14 Can't we somehow do this better? Simpler in this case in this sense. And that's what we'll look at in That's the motivation of this of the next unit. Uh I'll also take it as a motivation to take you through a journey of just fun things. Uh but we'll end up with some some candidates for indeed nicer and simpler solutions.

2:43 One disclaimer I have to give is that up to now, and people have tried a lot uh including the original inventors of some of of some of these Turing Award winners like uh Robert Tarjan and so on. Uh nobody has found a solution that's substantially simpler than what we know and achieves the same guarantees, in particular the worst-case deterministic log-in height. Um indeed, the alternatives I'm going to show you all have some slightly weaker guarantees. They're either randomized or amortized.

3:17 We'll talk about amortized the next chapter. Um it's a big topic in data structures anyways, and then we'll use the uh search to exemplify that a bit. Randomization is the other one, which um is clever use of randomness. In most applications, that's quite fine. We talked about Git earlier. It's not exactly randomness, but it's of the same type. There is a It's not explicitly randomized, but still we kind of hope and pray that this unlikely event of a hash collision doesn't happen. We might as well hope and pray that some other unlikely things don't happen. And indeed for randomized algorithms we have uh a dialing knob that we can make things as unlikely as we want.

4:08 Okay. Um the other thing of course is that simpler may often be faster by the constant factors. These uh worst case balanced deterministic search trees are optimal in terms of the big O class, but the constant hidden inside there isn't quite so optimal. And that's something you can measure as well.

4:37 At this point let me quickly recall two important concepts that you don't want to mess up. Again, this is something you will have seen. The difference between average case average case analysis and randomization. The terms are similar. There's random stuff in both going on. Um but they're distinctively different in how we apply the randomness. Average case analysis says we have a deterministic algorithm, say our unbalanced binary search trees, and we assume that the input is somehow uh randomly chosen. We look at an average input. But if I fix an input, the algorithm does the same thing each time. By big contrast, a randomized algorithm rolls dice internally. So, it uses randomness internally. Even if the input is the same, it'll behave differently each time. This usually makes practitioners, or at least maintainers of standard libraries, very nervous. They hate this idea that performance isn't repeatable or or reproducible.

5:44 That's sad because often times you can do so much easier and better solutions with the randomization. Uh external libraries, many many libraries built by tech companies use randomness where the standard libraries didn't dare to. And that shows you that there's this gap. Okay, I'm I'm digressing. The definition deterministic algorithm on a random input versus non-deterministic randomized algorithm on a fixed input. Uh Here to do the analysis, there has to be some randomness that's in the input distribution. We assume that the input is chosen randomly. Whereas for the analysis of a randomized algorithm, we usually think of the input as worst case or it could be chosen adversarially by someone who tries to make us fail. Here we assume that the world is nice to us. It randomly chooses the inputs. So, a weaker statement, right? A weaker assumption.

6:44 In both cases, we get somehow costs as random variables. They depend on random things, here on the inputs and here on the internal random choices of the algorithm.

6:59 What's indeed confusing apart from the name is that the analysis often uses the same techniques, but keep these two things separate. Uh they're of course very different beasts because in this case, you get a guarantee that is worst case over inputs, so it's a robust solution. And here you have to hope and pray that your assumption is realistic.