Video 2-7: §2.5 Ordered symbol tables

0:00 Ordered symbol tables

0:06 okay i really think um we should have another subsection whatever it is is it three six two six welcome to the improvised subsection on ordered symbol tables i feel this should be broken into two parts so this is still discussing binary search trees and dictionaries but i want to make this a an additional part so that the videos don't get too long it turns out that the operations from the symbol table i've shown before are not all that you sum that you want and not all that binary search trees can easily support efficiently there's a couple of more operations and and these are the ones um one is finding the smallest or largest key in the symbol table that's similar to priority queues if you remember somewhat related is floor and ceiling that's um well think about well first of all it is the key in the symbol table the largest key that is just smaller than x or equal to x so um sometimes if you use floor you just get x back and then you learn not so much but you learned that x is in the in the symbol table if x is not in the symbol table you get the largest key that is in the symbol table but is smaller

1:43 and if you think about the ordinary floor function on real numbers to be defined as calling floor on this symbol table of all integers is of course infinite and we don't want to represent it in the computer but just uh as a mnemonic you could say you take this floor function on the integers and then it would give you exactly that that function and the same for ceiling right so uh we write this as this that's the the smallest key in the simple table that's bigger than x and the last two so these are these are really the um the important ones they look they look innocent maybe but they're really powerful rank offers of a value is the number of keys in the simple table strictly smaller than x and select is give me the the cave smallest because i used key k for key before i like to make this i this is i and it's just a name

2:29 Rank and select operations

2:59 and think about select really um like an index into an array select is the very same thing as saying a of i i want the i position in an array you can use select to get the i entry in a binary search tree in its left to right order and that means you can use ordered symbol tables to create dynamic arrays in the sense that you can insert arbitrarily in at any position you can add new elements and you can still access the the middle you can do binary search you can do all these things using calls to select now select is not constant time it takes logarithmic time we'll come to it in a minute but you can still use this to build things that are that behave like an array but can can grow at any point in time very flexibly that's um that's the abstract data type so this is um that's the adt and as as before um you see it sometimes as uh as ordered map or all these other names that i listed before the implementation is this

4:14 Augmented binary search trees

4:19 maybe show just the tree for now [Music] is an augmented binary search tree where every node also stores the size of its subtree how many nodes are in its subtree so you see that the leaves always have one and then this one has two one two and this one has four one two three four you always count yourself and that will help us to implement these operations before we do that i want to ask you this question on slido if you take this tree and

5:10 what is rank of 35 if you execute this query what's the result i want to briefly see if you are familiar with the um operations and that it makes sense to move on

5:36 okay five billboarded so you need a little more time i'll leave the tree here instead of showing slido because you probably need it i should probably have added an option i'm confused i don't know

6:44 okay 26 we've reached 37 before so maybe uh i'll give you a minute okay i think the the trend is clear let me show this here um so well i can show the correct answer most of you have it um i'll discuss why in a second uh but there was also a few people who were either confused or said didn't know so it's worth um discussing this again uh very briefly

7:30 so just remember rank is the number of keys in the symbol table that are strictly less than the argument that you pass so in our example here rank is past this value 35 so x is 35 right

7:53 and now we have to count how many keys in the symbol table are smaller and one way to do this is just naively well there's one two three four and then these are all bigger but remember we can project the keys down here so here's the 35 and you have to count how many are in this range that's that's rank and that's uh four all right let me close the poll again

8:18 Computing rank

8:27 so uh caveat number one it's essentially zero based uh you don't count the 35 it's the fifth smallest in this tree but you say the rank is four because we start with zero eleven would have rank zero right um yeah so the second um

8:46 the second comment is probably best shown on the next slide so that's that's rank and you can figure out how the other operations work similarly here on this slide let me show the same example again so we're looking for 35 here i added again the projection down and i added the visuals of an array and now if you do this you see that actually rank is precisely the index in this array okay so for every element it's rank if you call rank with the key of a node you get this number

9:36 all right four is rank of 35 rank means go down and take that number but how how do we compute this i mean this was like human insight and we looked at the sorted list how can the binary search tree compute the rank so let's let's see first we do the search path so we go

10:04 and find our element in this case the the 35 was in the in the tree so we found it here now the rank is computed as follows whenever we go to the left we do nothing to our rank we start with r equals zero whenever we go to the left uh add a node we do nothing when we go to the right we check how big is the left subtree so we take this and we add to our

10:52 the well this node maybe is called v so we add to our the left subtree size i'll just use this this notation for that v is is this node the 12 left is its left child and st is this subtree size that we have stored in each node but we also add a plus 1 because we went to the right that means also the 12 is smaller than the 35.

11:32 here again we go left so we do nothing here we go right so again we look at the left subtree and that has size one and we also add the 28 so we have at this point r is 2

11:53 and once we go down here r is 4 because we have added one and one for the node where we are and if we reach the node that way we leave r where it is and um that's that's the the right answer then

12:08 Computing select

12:10 all right that's uh that's how you do rank it's fairly easy if you have the subtree sizes um how can we do select um how can we find the element

12:30 at position four let's do the same one so we get the same result so again select four it should just be if this was the array it would just be accessing the fourth position at this array except that this array doesn't really exist it's only it's only imaginary it's only in our illustration we don't really have that in memory but we would like to find the fourth smallest element so what we do is we start at the root and we're looking for rank four now um if we look at the entire left subtree of the root

13:17 we know that we can find its um subtree size if we go to the to the left child the left child and then take its subtree size this nine gives me the rank of the root all right now i compare 9 is less than 4 is less than 9 so i have to continue on the left

13:49 um i don't think i can easily duplicate the slide that's um okay um so we know that four is is smaller than nine so we continue to the next one

14:28 so we're looking for rank four now we do the same thing we look at the left subtree look at its rank and that tells us the rank of 12 is one but four is bigger than one so we have to go to the right

14:52 and continue here now here we have to be careful where um as soon as we go into this subtree we're cutting off these two nodes so we have to adjust instead of four we now search two you have to subtract the the rank of the note plus one

15:19 so we start with r equal four if we go left we do nothing but if we go right we do r minus we subtract from our um this uh the size of of this part that we skipped so again

15:43 left subtree size and one for this node so we're now um down to this part and okay this is not too messy so maybe i'll just continue on that slide we try to find the note with rank two in here

15:59 and so one more time we look at the left subtree that has rank four so inside of this tree we have four it's all shifted by two now so four is less two is less than four because four is the rank of this node minus two i know this is a bit confusing

16:28 i wonder if there's a nicer way to illustrate it so we have to go left again and we ask here where is the node of rank two within this you look into the left there you find a one so this is rank one minus two 2 is bigger than 1 so you go to the right okay now you have to adjust the rank again now we ask for rank 0 we subtract this one and we subtract this one and then finally here we look into the left subtree it's null it's empty so that means the root has rank zero and there we found it and return it and that was the correct answer because we know that this has rank 4. that's in a nutshell how you do select in an augmented binary search tree

17:28 Maintenance and efficiency

17:34 here are all the operations that we discussed before and this this slide should have been earlier that's what we discussed they're all bounded by the height and construct is essentially given by doing n times the insert

17:58 okay so there was some a question about the number below the nodes the number below the load the number below the node is not the rank it's the size of its subtree you can compute the rank of the node from it but only in a top-down traversal it's not explicitly stored in the node because you couldn't maintain it

18:28 um okay i think we have to postpone the balanced binary search free part to tomorrow uh one thing i wanted to add here is okay now we have the um i need to turn this off again let me copy the background i want an empty page

18:56 now i copied it before sorry now there we go i screwed it up after that page a new page please sorry for the mishap um so um just to stress again

19:24 each node stores its subtree size because you could not maintain the rank information upon insertions and deletions but subtree size can be maintained can be maintained i don't want to go into the details of this if you want to see this um it's in the book of secret wayne and in their videos basically you can go through the insertion and deletion procedure and see that

20:19 for the notes on the search path you can just increment or decrement their subtree sizes by one and that's enough to maintain the subtree sizes whereas it wouldn't work for rank um maybe let me give you uh a very small example if you like so suppose there's a really huge tree on the left so this might go on for quite a while and now we insert a new node here

20:52 which node's subtree sizes have to be changed there's a plus one in this node's subtree and a plus one in this node subtree and a plus one in this node's subtree but the subtree sizes of all the notes in this big part over there don't have to change

21:12 um now i should have drawn the picture the other way around um it's not too hard to get so bear with me for just one minute and then i'll wrap up for today

21:30 this works just the same except that i need to make the edge a bit longer well that's uh that's doable suppose um this would have been the picture it's easy to insert this node and update the subtree sizes of these nodes because remember these nodes are on the search path to the insertion position so we have to walk that path anyways but if you were to update the ranks

22:06 you would have to go to all of these nodes and add one to their rank because there's a new element inserted left of them and that doesn't work you cannot do this in logarithmic time whereas if you do the subtree sizes you can do it and you can compute the ranks in a top-down traversal

22:26 explained that concludes the part on the ordered dictionary implementations with binary search trees and we'll wrap up the remaining part of tomorrow