Video 3-8: Balanced BSTs

0:03 In the next section, I want to briefly mention how to bound the worst case of the operations as opposed to appealing to the life being nice to you and giving you some um uh random insertions. Uh this part I'm only going to cite results, so um maybe we can collect what people know there.

0:31 If you've done algorithms and data structures lately, then you will have seen some uh this a whole zoo of possible options. Uh there's two classic ones that are normally one of them is taught in undergraduate data structures.

1:12 Yep, red-black trees and 2-3 trees, that's the the one classic one. Uh B-trees are, if you wish, uh very similar or very related. One is a special case of the other.

1:29 Yeah, I guess the 1-2-3-4 trees belongs together. Uh does it break up at spaces? Amazing [laughter]. Well, uh I think the one that's missing from the list that many people also know is AVL trees. That's one other classic one. Uh I mean either of them does the job. Um the fact that we want for this module is just as a black box, you're supposed to know that there is such a thing as a balanced binary search tree, a BBST, that magically makes it happen that the height is always bounded by a logarithmic a logarithmic term with some constant factor. And we have ways upon insertions and deletions to enforce that this this height stays bounded like that. Um what you've mentioned, the classic ones um are listed here again. AVL trees is a tree where at every node the heights of the left and right subtree have to differ by at most one. And that's again a rule you can enforce um I guess this is this is the historically oldest, so that has some significance.

2:51 It's otherwise a bit less practical than red-black trees, so they fell a bit more in fashion. All of them are fine. Um there's many other variants, and indeed uh there's further options that are also interesting. If you're eager to learn more about some more uh tweaks and twists and more practical versions of these things, you can come to advanced data structures in a year or so. For now, let's just leave it with that. So again, for efficient algorithms, all you need to know is there is such a thing as a balanced binary search tree. We won't look into this this again. Um also from the uh survey it seems most people have seen something like this at some earlier point. Let's Let's wrap up um what we've seen with that. So now we can just have running time. It's worst-case in the in the strongest sense. Uh for balanced binary search trees, all of these operations you can support in worst-case times as given.

3:54 Uh um if you store min and max, you can do a bit faster here. And let's compare that also to the priority queue implementation we've seen binary heaps. And you may note that um there's a bit of a superficial mismatch that put is called insert here and so forth. But basically it seems that apart from this construct operation we don't need binary heaps because binary search trees are just as good. All of the operations that they that the heaps support these um balanced binary search trees can do as well and in the same big O running time. Now one one remark is it's um it's true that binary heaps are still a little faster than binary search trees in practice. Uh there's a constant factor difference. And you win there a bit. The more important point from, from a eternal truths perspective, is that this abstraction of having a restricted interface where you say, "I don't need a full-blown symbol table; I only need a priority queue where I can't access elements, uh, from anywhere in the in the key range, only the maximum, say, is efficiently accessible."

5:15 This abstraction has value beyond what you see in this table. And one reason for that is to communicate to someone else that you don't need this extra fancy operations. And the other operation the other reason is that you can in do it indeed support these operations faster with more sophisticated data structures. I will not look at those here. Um again in advanced data structures you'll see some that achieve this. Uh if you want to see those, for now I'm just leaving this as a kind of point in case that having this abstraction helps because there is a better way to support it. And if all you do is work against this um abstract data type of a priority queue, you can just swap in a better implementation. And for example C++ this boost library has all all sorts of priority queues implemented there. You can literally swap out one for the other. Uh other other libraries um there's nothing built in for Java that comes close, but um boost is also not built in.