Video 3-7: Augmented BSTs

0:03 We'll stay with unbalanced trees for a tiny bit because there's a a bunch of operations that I think are worth knowing about and these are um at least knowing that they exist is important for some of the exercise problems and the occasional old exam question. So I think um I'll recap this here even though you've seen this in algorithms and data structures if you've done it with me and it's uh standard standard operations.

0:27 Um, binary search trees are ordered symbol tables. They don't just associate keys to values. They keep an order on the keys. So, you can ask other questions than just get me the key associated to the value associated with a key. For example, you can ask this question, what's the smallest key currently stored in our symbol table or the largest? Uh, you can also ask, here's some key that may or may not be in your dictionary or in your symbol table. Find me the one that is in the simple table that's closest to it but smaller. That would be floor or ceiling the same opposite with a the smallest that's at least as large as x. And you can ask questions um that count. So uh rank in the same way we use rank for for sorted sets. That's the total number of elements in the symbol table that are smaller than x strictly smaller than x.

1:24 So that rank is essentially zerobased, right? The the rank of the minimum would be zero because there's nothing that's even smaller. And select is the opposite. Um given some rank, it tells you which element has that rank. The how many smallest element? Yep.

1:51 >> Uh yeah, good question. What if X is not in the symbol table? then the definition still applies, right? You count the number of keys that are in the symbol table that are strictly smaller. In this case, it doesn't matter if I say strictly or less or equal, but uh if it's an element in the symbol table, it matters. And the reason why this is um a very useful primitive is that with rank and select, you can simulate something we couldn't so far build, namely an array where you can insert at arbitrary positions. and uh then everything essentially shifts over by an index. But you don't have to explicitly do this index shift. This is just handled by the data structure. I'll show some examples. But let's first see how you implement these operations. And the trick is with the binary search trees we've seen, you cannot really do it. You have to augment them.

2:47 Before that maybe um to make sure the definitions are clear let's look at this example an example tree and um a query that asks for 35 I think most people voted. So, let me open this.

4:12 There's a there's two answers that are uh close, but because it's zerobased, it's four. So, um let's let's see, right? Uh the rank is the same as what you would get if you project all of these down to the x-axis.

4:29 That's the way I've drawn this before. Right? Then you could think of the elements here sitting in an array at the bottom 11 and then 12 and so on. I'm not going to copy them all. And this hypothetical array which is not really there. It's just in our imagination but you can say it has indices 0 1 2 and so on. And that corresponds to the rank of an element. the index that it would have in this in this imaginary array because 35 is here at index 4 the rank is four or by definition you can also go here what is the number of elements to the left of it that are strictly smaller that's these four guys so the rank is four okay how do we implement this how can we find the rank of elements in a binary search tree uh for For that we need to augment our binary search trees with these numbers here namely the sub tree sizes.

5:39 So each node carries an additional integer which stores how many nodes are in my subree meaning me and everything reachable via my child links. So leaves have a one, this has two because there's itself and another child below it. And of course the root has the size of the entire tree. um 16 in this case and um let me show how to do this operation for example, if I want find the rank of 35, I'm starting at the root. That's a bit too fast. Hold on.

6:36 I'm going to do a search in this tree for the key 35. And I'm going to count how many elements I've seen that are smaller than that element. And I start at the root. I go left because 70 is bigger. So I'm I'm following this path down here. So far I have no element that I know that is smaller. Now at this point the the 12 is smaller than 35. So I have to go left. But it also means there's a bunch of keys now that I know that are smaller. In particular the 12 but also this entire subree. Now this entire sub tree here is a single element, a single node. But in principle, this could have been an entire large subree. So I don't have time to count all these nodes. But luckily, I don't have to because they have a subree size stored right in the root in 11. That tells me there's one element I should skip here or one element that I'm I'm uh I'm uh ignoring now, which is smaller than my key I'm searching. So, so far I've seen one from here and another one here that are smaller than my 35.

7:41 And you can also trace this in the array view if you want. So now we move to the right, right? Uh continue the search. 57 is larger. So I'm I'm just moving left in this case. I'm not skipping anything. Uh then the 28 again is smaller. So 28 certainly counts towards the rank, but also its entire left subree. Again, just a single element in this small example, but in principle could be larger. And um one more step then I find 35. At this point I know I can stop and the 35 itself doesn't contribute to its own rank because it's not strictly smaller than itself. So um I essentially now know the rank for question.

9:01 >> Yeah. Um, it's a good question. Um, there's a slide for that, but you can think about it why that is not a good idea. There's a problem with directly storing the rank and it has to do with the updates. Um we we haven't discussed that yet but uh we want the data structure to be dynamic. So we have to deal with insertions and deletions and at that point it turns out that the sub tree sizes are more convenient. Um to finish the rank computation what we have to do is sum up these terms. So the code that's on the right here from Satri and Wayne does this on the way back up. So you know here um how many you've skipped and then you can sum up the elements you skipped. Could have done it on the way down I guess as well. Okay. Um that's rank and the other operations are in a way uh similar. The opposite of rank is select. We maybe jump to that.

9:57 So if you want to find the element of rank four then um we start at the root and we do a similar search but now we have to compare ranks and sizes. So the four here tells us I'm looking for the element at position at index four. That's the fifth in the left to right order really. Um my subree size is 16. So, I'm definitely going to find this index 4 in my subree of this of this element. Well, that's not a big surprise because it's the root of the entire thing. How do I know whether I need to go left or right? For that, I have to peek into my left child and determine how big that is. And in this case, it's nine elements big. I see that from the sub tree size entry of this left child. and nine is large enough that my index four will be contained among those elements. So I have to go left.

10:54 So that's what what we do and we continue to look for index 4. Now here at this point um the left uh tree is small. So um I'm not going to find my index 4 in this left sub tree because it's only a single element which means I have to go right. But now I have to change the relative index that I'm looking at because I'm skipping this element in the left sub tree and I'm also skipping the 12. So I have to subtract two from the four. And in this recursive call on the on the right subree I'm now looking for index two relative to this subree. Apart from that nothing really changes. And we continue in the same way. Again here in the left subree there is enough space for two. So I go left and now I'm in this position. Uh I skip one on the left side and then here another one. So for index two I have to go right and I have to adjust the index I'm looking for. In this case it gets adjusted to zero because um I'm subtracting two. Right? Two notes are skipped.

12:05 And then I arrive here and zero is always the leftmost. In this case, the left child is empty. So the index zero node is the root of the tree. So I found my 35 again. And of course, if you paid attention, this was the inverse of the rank operation. We asked what's the rank of 35? And then I used the same the return of that return value of that as the selection call. So we find the same element again.

12:38 Uh that's basically these operations. Um, floor and ceiling are kind of even easier. They just pretend to search for a value that is slightly above the thing you search for. If you want, you can click through that. Uh, the link is on on the website.

13:00 So, we've done rank and select. Um, and here's the question that you asked earlier. Why do we store these weird sub tree sizes when in fact all we want is rank? And um the reason for that um uh suppose I also store the ranks. These are the Rs on the side. I don't know if it's uh big enough that you can read.

13:44 So uh suppose I I were to store those and now I want to insert something. So let's insert a new value say number five which will go mostly left is a small number. It will go all the way to the left side. And now I have to insert this here. Now what what does that do to the ranks of all the other elements in the symbol table? Uh once I add this here, all the other elements need to change their um rank.

14:17 Every single node in the tree needs to change. Now unless I have some clever way of encoding this, I would have to go and visit the entire tree and make this update. And that's too slow. That's linear time. Whereas if we keep the subree sizes, as you can see in the same figure, um the sub tree sizes are still up here. And where they have changed, there's also the update shown here. I don't know. There's a lot going on in this picture. Maybe it's a bit uh overburdening.

14:54 I'm trying to copy um a screenshot to the slides. The key point is that the sub tree size can only change for those trees where I've changed something in the sub tree by definition. And what I what I changed is I added this new extra node here uh whose subree can change as a consequence of that. Well, my parent and my grandparent and and so on, but nothing else. Only the sequence of ancestors can change. And that's as many nodes as I always touch when I walk down the tree anyways. So that is bounded by the height. And of course the height we now know uh is either good if it's random or we can try to balance the search tree that's coming up next. Okay.

15:53 And of course the same same would be true if you now delete a node. Um then you have the same problem. You're changing uh everyone everyone's ranked further to the right.

16:09 It follows precisely the code from Crick Wayne. That's why it's dancing around a bit. And so again, you see how everyone's rank has changed. Whereas the sub tree sizes again only for the ancestors.

16:25 That makes the code a bit more fiddly to work out the ranks from the sizes, but it makes updates logarithmic if the height or linear in the height as opposed to linear in the number of of keys.

16:51 questions on this part. Um, basically what I wanted to wanted to show you is you can with this cheap trick of adding sub tree sizes support these rank and select operations and they're a rather useful primitive because precisely because they can simulate you had an array where you can insert in the middle. You pay a logarithmic overhead uh but at least you can you can simulate a completely um dynamic sequence with that.