Video 1-1: Recap - Sorted Dictionary and BSTs

0:00 Symbol table foundations

0:04 In the first unit of actual content, which we'll just start a little bit today, um we look at at randomized trees. So, alternatives to uh standard binary search trees, or roughly dictionaries, that somehow use randomness. But you may ask, why would you even want to? Uh to motivate that a bit, uh I'll I'll recap a bit where we come from, and then uh we'll slowly work our way to various alternatives that all uh exhibit some some cute ideas, I think. Uh well, let's first see uh where we come from, and I expect that this is nothing new. Maybe you've seen it in slightly different language, but you'll this will be essentially very familiar. Uh symbol table, or dictionary, or one of these other lovely names, is one of the key abstractions in computer science, I would say. Uh you can put in a mapping for a key, assign it a new value. You can read out the mapping, or the value assigned to a key, or you can delete uh the mapping, or ask whether it's contained, plus a few other things. That's the bread and butter thing we use all the time.

1:16 Java calls this maps. Um in Python, it's even a built-in um I guess data type. Of course, it's also a data structure. So, very well known. I'm sure you've all used them in programming. How do we implement these? Well, okay. Before we get to implementing this, there's a few other operations that you would sometimes like to have. Uh if people just say map, or or symbol table, or dictionary, they usually mean mean just this, a key-value mapping. Um you can also, if the keys have a a linear order, or a total order, support these other operations, where min and max are maybe not so exciting, but you can find for a given key, what's the the closest in key space that is stored in the dictionary? Either the one that's smaller or larger than a given key. And rank and select are powerful primitives to build essentially something like a dynamic array where you can insert in any position.

1:30 Ordered symbol tables

2:22 What do I mean by that? Well, rank gives you for a given key, how many other keys in this data structure are smaller? That's a bit like the position in that list in sorted order. And select is the opposite. It tells you for a given index what is the key such that I elements are smaller. So, these two together you can use to implement something that looks like a sorted list, but you can insert arbitrarily at any place um without copying like in an array where you would have to move everything to the side.

3:03 That's what this uh sentence here with the extra dot means. Um This of course has the additional assumption. This um assumes that the key universe is ordered. Whereas the previous didn't need that assumption.

3:22 Binary search trees

3:23 I'm sure you've seen both of these before maybe with a different name. One option to implement both at the same time are binary search trees. I think all of you have seen those, so uh it's familiar to you. Uh you could say it's a dynamic sorted array of sorts. The simplest version is composed of of pointer structures where you have nodes in this binary tree that each have a left and a right child. And we have the search tree property which is crucial for searching in the tree. Okay.

3:57 If I'm like interrupt me, please, if I'm going over this too quickly, but I'm I'm hoping this is just uh undusting memory. Uh if you look at these operations, rank and select, from just this, it's actually not clear how to do that. Uh at least not efficiently. Um but there's a standard trick that probably you've also seen. Usually goes by the name of augmented binary search trees, which just means every node stores its subtree size. So, if there's a a node X, and it has a certain number of other nodes below it, right? It really looks more like like this, right? Uh we draw these triangles to abstract from the actual shape. Uh then in this case, this X would store 1 2 3 4 5 6 7 8 9 10, including itself. So, maybe uh here on the side, it would remember that its subtree size is 10. And turns out with these numbers, you can solve rank and select, and you can maintain these sizes efficiently upon updates.

5:05 So, binary search trees, at the very least with this augmentation, solve all of these previous operations. Now, how fast are they? That depends. Um first of all, here's a binary search tree as you would want to draw it. Do we need an example for search? Again, maybe not. Um you navigate down if you want to find the 63, start at the root, you find 63 smaller, so you go left, etc., etc. Um insert, you do the same, the standard insert. I'll I know this is baby stuff. We'll we'll come back to this at some point. I want to make the contrast. Insert in a binary search tree is normally done like this. You find the leaf if you want to insert 88. This leaf is where you would have expected to find 88 if it wasn't the tree, but at the moment it isn't. So, you replace that leaf, that null pointer, with a new node with that key.

6:11 That's how we normally do insert. And then delete is a bit more tricky. There's this annoying case distinction. It's easy if you're removing a leaf or a node with a single child, then you can just shortcut. If you're told to remove a binary node, there's not enough parents to hold both children. So, you have to do something. And the usual version is to go to the predecessor or successor in sorted order, swap the value with that, and then recursively delete that guy. And it turns out you only ever recurse once because your predecessor or successor is guaranteed to be a unary node or a leaf. It cannot have another left or right child because that would be you. Would be the 12. Again, uh undusting memories, standard deletion in binary search trees, uh also known as as uh Hibbard's deletion.

7:15 Uh that that is the person who first described this. But again, this is with almost 100% certainty, this is how you've seen it. One of the two one of the two versions. Either you go to the successor or the predecessor, it doesn't matter.

7:33 Performance and randomness

7:33 Okay. Now, how fast is this? Well, it all depends on the shape of the tree. You have all these operations. Uh for some, you can be a bit clever if you just uh keep track of the global minimum and maximum in the tree with an extra variable. You can do this in constant time. But almost all of these operations have to follow down a path in the tree. I guess constructing from N keys means just N times insert. Um, not even clear if we need that as a as an extra operation in in this case. And the path down the tree along a search path is never longer than the longest search path, that is called the height. Hence, in the worst case, all these operations are bounded by the height of the tree. Again, we haven't left baby data structures land. This is uh how you learned it back in the day.

8:31 Uh now, unfortunately, in unbalanced binary search trees, which just means you insert as things come and don't care about what happens to the shape of the tree, this height depends on the insertion order. Is always between log N and N. Uh maybe I should say log I'll always write LG for the binary logarithm. Cuz it pops up so often. It's convenient to have this extra symbol. So, that's fine. But between log and N there is a lot of space. There's an exponential space, right? Uh it turns out if you randomly insert things, specifically if the keys come in the order of a random permutation of the final set, then it's actually uh close to this best case. We'll look at that in more detail soon. Uh also, what this means, this is where we leave baby data structures land. This term probably doesn't come up. I don't know if you know uh a formal definition of it.

9:35 It's a bit of a trick question because there's more than one. But show you the the usual one. Someone want to Yeah, what's what's with high probability? What does it mean?

9:50 It should be with probability somewhat close to one, close-ish. But what does that mean? Pardon? Define close. Yeah, um it's an asymptotic statement. As n becomes bigger, we get we converge to one to the probability one that this holds. Well, uh we'll come back to that. Uh I just want to mention it could mean different things. It could mean that the probability is 1 minus little o of 1. So, that's the weakest form. It converges to 1, but I'm not making any guarantees about how fast. Or it could be 1 minus 2 to the minus n. Exponential convergence. That's great. It's very quick. Maybe a bit too much. Uh we'll settle for something in between. So, at this point, you're not supposed to know this or you're not supposed to see why that's the case. I'm I'm telling you promise, pinky promise, this is what will come out of the analysis that we'll do.

11:00 Balanced tree schemes

11:00 Okay, but that's for the knowledge about unbalanced binary search trees. Now, you're going to say, "Yeah, I know how to solve this. We know schemes for balancing binary search trees. 85% new red-black trees. Maybe the other 15 know AVL trees. Uh one of the two probably you've seen. These are any kind of rules that upon updates, insertions and deletions, somehow change the shape of the tree to guarantee that we have a logarithmic height.

11:36 As I said, the two most well-known are AVL trees and the red-black trees. Uh there's others and there's to be honest, there's a a large family of of more modern ones that all have slightly different properties. Um all of them guarantee that the height is big O of log n at all times. The constants hidden by this big O, in terms of the the uh largest uh length of a search path, they actually differ and this is the not just part of the analysis, there's really a some schemes, like AVL trees, are more balanced than red-black trees. Uh okay, here it depends on the parameter. Uh you can you can look further into this if you wanted to.

12:24 All of them essentially do rotations on the search path. I'll briefly recap that on the next slide. Uh sometimes you get additional guarantees that are useful in some uh let's call it fringe use cases that are not so fringe, but uh we're not going to uh dig into this uh that much. Um computational geometry often makes use of this property that you don't do a lot of rotations high up in the tree.

12:57 What's actually an open question is to look at a closer statement. For most of these trees, it seems our mathematical toolkit is not able to handle these questions. If you do fix one of those rules for keeping the height logarithmic, we know an upper bound for the height that follows from the worst possible tree you could still find that satisfies, say, the AVL condition.

13:24 But if you start with random insertions, like previously where we say ah if if inputs if the insertions come in random order even the unbalanced tree is closely balanced. If you do that on either AVL trees or red-black trees you essentially get 1.01 times log base 2 of n height or search cost. They're extremely balanced but nobody really can prove this. Is this you can do experiments and then people observe and I think there's some some things known that it's not exactly optimal log n without a constant in front but the constant is maybe indeed 1.01 or so something of that sort. And we don't know it seems we're not uh the the math tools that we have are not sharp enough to handle this question yet. Or uh maybe there's a clever idea that nobody has tried. It's an open problem. I was just very keen to have an open research problem in the first lecture.

14:25 So that is one that's easy to state. Not sure how excited you are about this problem but it's a a kind of tantalizing question that we don't understand these very basic data structures all so well.

14:42 I said all these um Yeah. I don't uh It's a good So the question was is it proven that there is some constant times log n as the cost? Uh I think it's proven that if there is a constant it's not one. That's I I remember a statement like this. Probably it's not known whether it's a constant times log n. It could be some some term that is periodic with log n or some crazy behavior that's not a constant. It's possible I guess. I I know of a result saying it's not not the case.

15:29 But there's some exact average cost for every n, right? It's a well-defined thing. We just don't know it. I mentioned that all these uh um balancing schemes are based on rotations. So, let's briefly recap what the rotations do. There's essentially two cases, and then you can build further rotations from that. But the key one is either this, the topmost tree has um this structure, and you care about moving Y further up. The symmetric version has Y as a left child. Okay, X and Y should look different.

15:38 Tree rotations

16:16 And here A, B, and C are any kind of subtrees. They could be empty, or could be large I'm just giving them some names.

16:30 And by and large, the two rotations let you go from one to the other. Uh if you move Ah, this is Let me swap the two. This is very unintuitive. I'm sorry.

16:46 Because now, going from left to right is a right rotation. We uh You move The right rotation says I'm moving this guy up and this guy down.

17:03 And so, maybe in between, there's somehow like this. I can't really connect them well, because it's It's a proper tree. But then at the end, this guy moves further down and it's connected like this.

17:30 Both before and after, note that um cool, X and Y are wrong. This was testing your attention. Obvious. Note that before and after Y is smaller than X. Here it's because it's the left child and here because X is the right child. And A is everything smaller than Y, B is between Y and X, and C is greater than Y than X. And that doesn't change during the rotation. All that changes is the shape of the tree. Now we're just doing a local flip. So if you see if you look at what changes it's this pointer and this pointer and this pointer that changes. So we um take that back. This one doesn't even change. It's two. Double rotation changes three. Uh it's two pointers that we that we change and then we slightly modified the tree. But what happens to the subtree sizes or the heights is that this uh whole tree C moves a level up and the a level down if we go to the right.

18:34 And the whole subtree A moves a level up or vice versa. Now uh if you're in the situation that you want to move this B up, then you have to combine the two rotations. That's why AVL trees and friends also use double rotations. If you just use these single ones, then you're not moving B.