Video 2-8: §2.8 Balanced binary search trees

0:00 <Untitled Chapter 1>

0:03 In the last section, I just want to comment on something that uh you already brought up. Um how can we tame the height in general from a worst-case perspective?

0:18 Uh I won't go into much detail, so this will be relatively short. I just want to teaser this in a way. Um and show you what is possible, not necessarily dig into the details of how this is done.

0:38 so let's uh let's see how many of you have seen something like this before. So, the the question is just open text. Um the 2/3 of you who've come from some undergrad CS degree, you should have seen some some balanced BSTs.

0:54 Uh but no judgment in case you forgot. Uh in a way next to sorting algorithms, so there's there's many many sorting algorithms as you may know. We'll we'll talk about some soon. Uh after sorting algorithms, balancing binary search trees in a smart and slick way is probably the other little playground of computer scientists. Uh so, there's many many inventions. Um that are Um well, many are effectively equivalent if you zoom out a bit. Uh some have a slight edge in one way or another.

2:10 I guess the question was maybe a bit ambiguous in the framing. Is Is it enough if you just send the the name of the the way to balance them? It's so useful that Slido now supports emojis. We've all missed it.

2:36 Uh the none thing is fairly big, but that's just because um that collects everyone that said none or you just sent the same same text. Whereas um there's a lot of a lot of interest They keep moving all the time. Uh so, red-black trees got a few votes. That's a very um famous one. Height-balanced or AVL trees is the other big one. I saw a rank balanced somewhere. Moved around. Uh yeah, weight-balanced is another one. Yeah. Now, the other way to show this, I don't know if you can see this as well.

3:20 I can see that 23 people said none and six more said none with the emoji. I think the the Wordle thing uh combined those two. Yeah, okay. Now, I think it's time to move on.

3:35 So, this uh Uh emojis are just such a useful feature. So, um we've discussed that the height can be really bad. It can be linear, which is utterly useless. Then we don't get any speed-ups from using our our nice BSTs. And we could have just done a good old list. Now, fortunately enough, we don't have to rely on our luck of getting insertions in a convenient order. We can enforce the height to stay bounded by some constant times log n by requiring additional things. So, these come in the form of of invariants of what shapes of the trees are allowed. Plus, that's the important bits. Uh we need a way to maintain these these invariants after updates. And so, the rules that uh that are are known for this, they basically differ in uh how strict the invariant is and how quick it is to maintain it and reestablish it upon a uh updates.

4:55 Uh the three most well-known ones, also the maybe because they're they're fairly old as well, are AVL trees or height-balanced trees. There the restriction is um for every node, if I have two subtrees, then the height of the left and the right subtree are only allowed to differ by plus minus one. So, they have to be almost equally tall left and right, but we allow ourselves a little slack from that. Otherwise, you can think about if that's even possible to have exactly the same height. Um and this this allows the the property of of allowing one difference um makes it possible to keep that keep that invariant when you insert and delete. Uh red-black trees are a different idea. Uh there's a lovely explanation in the the lecture videos that are linked, so I don't want to uh discuss these in more detail. Um if you want the the the gist of it is you can generalize binary search trees to to trees that have more than one subtree.

5:58 Generalize Binary Search Trees to Trees That Have More than One Sub Tree

6:05 If a if a node has two keys, it makes a lot of sense to say it has a small key, a big key, and then three subtrees. Everything that's smaller than the smaller key, everything that's between the two keys, and everything that's bigger than the big key. You might as well do that. Now, why would you? The the trick for red-black trees or what leads to red-black trees is you can allow both, either binary or ternary nodes.

6:35 And that's enough to to enforce that the height of the tree is completely equal for all the leaves. So, all the leaves are at the same depth. But the paths can be binary and ternary nodes mixed. And a slightly more efficient way to implement that on uh on just binary trees again leads to red-black trees. If that sounds cool, look up the videos. Uh for So, for for COMPSCI 26, I should say all you need to know is uh these beasts exist. There's some way to enforce worst-case height of log n, no matter what the insertions and deletions are. And we'll uh ignore how this is done. Leads us too far. Uh but I can't resist on spending a few words just to spark your curiosity if maybe. Uh there's a third thing, weight-balanced trees is a little similar to AVL trees, but here it's about the subtree sizes. Um and so, it says that these two uh Well, this is a subtree size, so maybe I should just say S.

7:29 Weight Balance Trees

7:49 If these these two, S1 and S2, then the subtree sizes should differ by at most some constant factor. Uh some something like this. Uh that's a two.

8:16 Um and you can play with this constant a little bit. Uh can make them stricter balanced, makes the search time better, but the insertions more costly and vice versa.

8:28 There's many many more. Um These are the classic ones that give you worst-case height logarithmic. There are other options. We talked about amortized analysis in the context of the the doubling arrays, the resizable arrays. But we said every individual operation might might be really expensive, but I can guarantee if you do many operations in a row, in in total they're cheap, so that the average cost per operation is cheap.

8:37 Amortized Analysis

8:59 Similar things can be done for binary search trees, and they lead simpler ways to guarantee uh good up good good time for the operations. Uh and the last bit is you can instead of hoping that the insertions come in random order, you can enforce it. That sounds weird because the user tells you insert this, insert this, insert this, and you can't really choose what they do. But you can internally randomize and flip things around so that it looks as if it had come in random order. Okay, other cool things. I just like those, so that's why I listed them. Uh we won't dig further.

9:47 Uh the last bit for this for this unit is a big table listing the uh performances. Comparing um the two big data structures we looked at, the binary balanced binary search trees. no. Uh I haven't explained how this works in detail, but I told you they exist and so you'll have to believe me or or look it up. Uh they give you these these running times for the sorted symbol table operations. Okay?

10:17 Um Basically logarithmic in n or for most things. Uh to contrast that, I put the the running times for heaps again. We've had that before. It's just a copy paste. Um and so if you compare these two things, uh I mean there there's some things that heaps cannot do, uh but there's there's a few bits that seem that seem to suggest that there's no real use case for binary heaps.

10:47 Because all operations that they can do, you can basically simulate in a binary search tree. Uh okay. Uh yeah, I didn't didn't comment on this. So, if you want to find the smallest and largest in a binary search tree, you can just follow all the left paths until you hit the the last one before a null pointer. Same for max. That takes log n time because it could be the height. Now, if you really care, you could just keep an extra global an extra variable in your representation of the binary search tree that always points to the smallest element. You can maintain that and so you get it in constant time. If you want to do something with it in a balanced tree, you can't really update it. So, if you want to delete the smallest, um that's relevant for comparing it with heaps, right? If you can you can take a binary search tree and use it as a priority queue. No problem. All are supported.

11:58 Um then this won't work. Uh you cannot You can do access to the smallest in constant time, but the deletion would still cost you log n. Uh the deletions I've shown you, if you have a pointer to the element and that's guaranteed to be the smallest, it cannot have two children, so you could take it out in constant time. But that ignores the fact that we want a balanced BST. So, to rebalance it, you you still get this log n log n cost. Yep. Is this log base two? Uh it's You can basically pretend it's always log base two, but the uh the real answer is on this slide, it never ever matters. You can think about why. I think I mentioned it at some point. Uh yeah, so I'm I'm sloppy not sloppy on on the slides when it matters, I usually use lg for log base two. And when I say log, it's only in big O terms. So, l o g uh because the the base doesn't matter if it's constant in big O. It's just a constant factor difference.

13:13 So, we can simulate everything we can do with a heap with a binary search tree, so why bother? Well, two answers. One is uh the the constants matter, so heaps tend to be a little faster just because they can be implemented in an array. So, that's uh um is relevant enough in pract- in in applications, but that's uh one bit of the story. Um the other bit is that this abstraction of a priority queue sparked people to trigger to find better ways to implement priority queues. And uh so, this is like the the latest greatest uh cutting edge thing, if you want. You can get both insertion and changing changing priorities with constant time.

14:00 Uh e- even in in this sense, um worst case uh and everything. Only the delete max is still log n and we'll see in the next unit that this is best possible. There's no way to improve that in in general. So, mixed message in a way. Binary search trees can do everything that the heaps that we've seen can do. Uh and with the slight exception of the construction from a given list of things, they're never never slower up to a constant factor. But having the abstract data type was still useful because there is better way there are better ways to implement this abstract data type if you don't need all these operations. Okay? So, it's uh it's useful to think about these abstract data types to spark uh the development of new ideas, but also uh like don't don't be a slave of the existing ones. Uh Sometimes it's useful to break them open uh and and look if you can change the abstract data type for your benefit.

15:13 A bit of a mixed message, but I wanted to to compare the two at the end. Um I throw this this bit of information in.