Video 2-7: §2.7 Ordered symbol tables

0:02 is the recording yeah in the next section I want to talk with you about ordered symbol tables that's an extension of the API we've just covered and that binary search Tre is nicely Implement uh but it's an extension that that drives home this point of having an a dynamic array in the true sense where you can insert elements in any position um that that makes this uh really possible and I haven't really commented on this after uh shouting it out initially so we'll come back to

0:36 that in addition to the symbol table operations we've had before so mainly put and get plus uh deletions and so on uh an ordered symbol table um supports what we've implicitly assumed about the keys before namely that they are totally ordered a binary search tree always assumes that the keys are are in some order so that you can decide what goes left and right um and ordered symbol table exposes this order with extra operations to make it use useful for the user of the data structure so we have Min and Max to find the smallest or largest key in the in the symbol table we have operations that find the closest to a key if that's if the key itself is stored it will be returned um but if the key is not in the symbol table you find the predecessor or successor it's called floor and ceiling because if you think about the integers as your symbol table uh then floor and ceiling in the usual way would work like this so maybe it's a good nimonic whereas yeah that's the design decision from the book so um I just kept it that way and then we have two more interesting operations Rank and select rank is given a key and it finds the number of elements in the simple

1:57 table that are smaller whose key is smaller and select is the inverse operation you give it an a rank or an index I a number and it finds you the element that is the I smallest so uh that also means right if you

2:23 say select of rank of X and X is in the data structure our symbol table you would always get the same thing back so they're they're built so that this works rank would find how many are smaller than x and then select would give you that element

2:47 back and uh Rank and select May by the name not sound like this but you can really use those two specifically select to simulate something like a truly Dynamic array because select gives you access to the the I position so um you can you can use this to build an array as follows you have some some key value by which you keep things sorted and then the value that you associate with that key is the actual thing that you store in the array and then with select you can access the I position in this hypo in this Dynamic array in this hypothetical array and you can insert with the usual Way by specifying a key that lies between two existing keys in a certain position and it will just take logarithmic log and log and time if the tree is balanced if the height is good now I there's one difference to an array if you insert something in the middle all the indices of elements to the right of that shift okay clear right if you I have an array and I want to insert a new element in here all the elements to the right of it will have to make make uh space for this new element in a binary search tree we

4:08 don't touch all these elements that's the whole point we're not like in an array explicitly copying this this array is just mentally in your head it's a virtual array but still if you want to access by index you have to somehow keep track that all the indices have moved if you insert something in the middle that's why ordered symbol tables don't talk about indices they have keys and the keys stay the same but the ranks are Dynamic the ranks can change all the time with insertions and deletions I hope that may may become uh clear bit when when you use this a bit so for now again that's just a definition that's the abstract data type uh how can we implement this um before before we get to that though let me again check whether that has sunk

5:09 in that's a simple question testing your uh understanding of the definition no tricks involved but you may want to see the definition again you may want to see both at the same time

7:04 um we have a peak but we also have many other answers most of you are right so the the only thing to remember is that rank Returns the number of elements that are strictly smaller which is another way of saying it's zerob based uh the smallest element has rank zero so if we do this here um remember we project elements down then we get some sorted list so we can do that

7:42 here and I'll ignore the other ones the one we care about 35 is here and so there will be these four 11 12 17 and 28 which are strictly smaller so the rank should be

8:03 that was the symbol table with the sorted operations how do we implement this I already said binary search tree do the trick binary search trees do the trick but you have to uh add one tiny extra little bit and this has become known as augmented binary search trees um the augmentation consists in

8:23 having another field for each node which stores the size of its sub tree the number of nodes in its sub tree uh including the node itself that's why all the leaves have a one this guy has a two because it adds itself to that one four and so on so you can double check on the slide whether I did it correctly um that's the uh that's the invariant that we try to guarantee so uh every node shall know how big it sub tree is um and um I'll skip how to update that upon insertions and deletions again the videos do it in detail uh let's suppose you managed to do this and it's it's not too hard to do because um say you insert another note here 70 whose sub trees have to change if you do this well 70 is in this node sub tree and is in this noes sub tree oh it's a bigger one and in this notes sub tree and it's in the entire tree the roots of these trees uh let me get rid of that because it's not so helpful to see I think the roots of these trees are this one and this one and this one and this one H and that's exactly the notes on the search path so

9:50 we visited these guys anyways so we might as well while we do the search increment their size by one because they each gain one you know in their sube so that's if we add this this one here ah okay now I just said I don't show you how to maintain it now I did it's not that hard that's the point so how can we use this um for our operations Let's do an example for rank we're trying to find the rank rank of

10:40 35 as always in a binary search tree we'll start with a search because that's pretty much the only thing it can do uh so that's always a safe bet so we go all the way down

10:57 here until we find that node now rank is supposed to return as we've seen in the example four right we find the element here rank is the size of

11:12 this now how do we get this from the notes that we have on the search path without visiting all those nodes we don't want to pay extra so what we'll do is we'll split the contribution um of notes that are smaller into several parts one contribution

11:30 is visited notes that are smaller these are the ones where we took a right turn so it's the 12 and the 28 right whereas H whenever we took a left turn in the path we know that that node was too big and actually also it's right sub tree was too big uh we have to add another contribution

12:08 whenever we do a a right turn like in this case uh or well we follow a right pointer uh we have skipped an entire sub tree namely this one and here we do it again these we don't explicitly touch but we can check how big they are by peeking into that node size field

12:30 okay so in this case um this both works out to two but in general this these pink sub trees could have been arbitrarily big all I need to do is visit this child and look at how big it sub tree is that's the the whole Magic why the sub tree sizes are useful you can visit the node and do one check and then you know how big the sub tree is without further

13:04 looking and that's rank so to to put that into code you would have to do the search uh keep account whenever you um find a note that's that's smaller whose key is smaller and if you found such a Noe you can add its its left sub

13:26 tree how do we do the other operation the select operation which is the it uh let's do the same same example so if we say select or I'd like to get this one as a result because uh again remember this is this is virtual

13:49 right this array at the bottom doesn't exist in the computer memory all that exists is the tree I should have stressed that maybe this is just for us to make it easier to visualize and to think about it all the computer has is the tree structure on top but if I have this this help I know immediately select four should return to 35 but how does the computer do it only knowing the tree H well we do a a kind of search again we start at the root now we can't really make use of the key all we can use is the sub tree sizes this time now the root has 16 in its sub tree that doesn't help us but we can Peak it in its left um Let me show that maybe um as a dotted line so we peek into the left uh sub tree and get out how big it is and based on that number we make a decision now 9 is greater than four greater equal which means um there's enough nodes in the left subtree to contain the one that we're looking at in another way it means there's too many on to the left of this dividing line for our Noe that we looking for to be on the right side it has to be

15:11 left uh the only other option would have been I guess I should add a plus one here minus one on that side because we're zero based if we're looking for uh 70 for select 9 let's do this as a second case

15:33 select nine in this case I would also Peak into the left I would find rank nine which means there's exactly nine things in the left sub tree that means the root has rank nine then I can

15:55 stop okay so let's let's write this as strictly greater in that case we have to go into the left sub tree so we we now actually follow the search path to here now we're in the same situation we Peak into the left sub tree and look at its sub tree size that's one that's too small that's less than four so in this case we have to go

16:29 right but we're skipping a sub tree Now by moving right we move into this sub tree so the remaining tree that we're looking at is only this and there's two to the left of that one so that sub tree only corresponds to this this range okay maybe I should draw it a little more carefully so so only covering that part there's two keys that we are skipping by going left and we have to adust just the rank that we're looking for accordingly so when we go down down this

17:11 road we change our query to select two we subtract one for the note that we just skipped and we subtract one for the sub tree size that we skipped these are the exact same two values that we had before I called this the green and this the purple one before so we skip this and we skip

17:35 this then within this tree we do the same procedure we're trying to select the node of rank two we're here we peek into the thing four is bigger than two so we go to the left sub tree if you go left you don't have to adjust the rank that's the easy case we're still looking for rank two we Peak into the left one is too small so again we take a turn right but we have to

18:06 select zero now because again we omit these two the entire sub tree and this node are reduced are removed from the consideration and now we're down to this small part and now if you want if you say select zero here there's there's nothing on the left sub tree so the root has rank zero in this sub tree so we return 35 and that's what we wanted okay so select from all the operations is the one that's that's most intricate because you have to combine all the things that we've done before um but once uh once you're over that hurdle you have this fully Dynamic array where you can insert things in any point and you can jump to any position all bounded by the height of the binary search

18:58 tree in this case um I told you this solution without motivating why that's the solution first and uh I want to finish off by telling you why that is the solution the solution being augmenting the tree with subtree sizes uh it looks like this made made select rather tricky so maybe there should be an easier way to do it so for example you could instead of augmenting the tree with sub tree sizes store the rank of every node in each node that would be super handy because then rank is triv you just find the node and return the stored Rank and select would also be easy you just do a binary search based on those stored ranks someone wants to shout out why that's a bad idea you could

19:51 do this would work fine for the static problem but not if you want to insert and delete things so you can't really maintain this efficiently and it's if you draw a small example it's obvious to see why so suppose on the right hand side here's a really big sub tree and now suppose I insert a new note here what does that do to all the ranks to the right of this of this red node well they all have to go up by one I have to increase their Rank by one if I explicitly store the ranks in noes I have to touch all those

20:34 nodes I have to explicitly visit them and update their Rank and I just don't have the time to do that if I want to be fast this could be essentially the entire tree and so we're back to linear time where subtree sizes have this lovely property that they're local only on the search path does the subre size change right so subtree

20:57 size is only changing here plus one here plus one and here A plus one and I don't have to visit all of those guys it's just one path