Video 2-7: §2.7 Ordered symbol tables

0:00 Ordered symbol tables

0:03 in this next step section we'll look at a blown up version of the symbol table that has additional operations which are often useful in that binary search keys can can also support and this this assumes that like always in binary search trees we assume that the keys have an order we have to be able to tell everything on the left is smaller well what does smaller mean so the keys have some order then we can ask for the smallest or largest element smallest or largest key in the symbol table what we can ask for what's the closest in in this sense if I have some key what's the smallest that's bigger or the biggest that's smaller than the given key so the neighboring ones um and the last two operations those these bring us back to this uh this claim I I told you earlier that that binary Searchers are really like Dynamic arrays you can ask for the rank of an element which is how many keys in the data structures uh data structure are smaller and you can ask for the so-and-so smallest say the 10th smallest or the 100th and these two things together are really what an array can do uh specifically select that's like selecting the I element in an array

1:24 just that now it's always the sorted array of all the elements that are currently in there it's not that the elements get assigned some index and that index is fixed the index is determined by what's currently stored in the data structure so these two together um give us this this truly Dynamic array in that sense that you can access things by index but you can also insert and delete at any point in time

2:03 this might be a good point to pick up on on a question uh so someone noted that python doesn't actually have binary search trees it's one of the very very few languages that don't have a binary search tree implementation

2:23 um but it does have dictionaries and I told you that's that's the main way to implement dictionaries there's one other big way which are hash tables we won't really cover that in in this in this unit in this module um is a lovely topic and worth knowing about so I don't know uh finding the appropriate videos on the resource page for this unit has all the infers about hash tables as well so it's true the the dictionaries in Python are using a hash table what hashing cannot easily support is the ordered symbol table operations that we're discussing right now so the if you need just a symbol table hashing is often faster than binary search trees but it has some some additional assumptions if you need the ordered operations hashing is not really an option

3:30 uh yeah some little practice wake you up on this um this time I have to leave this light on now I mean the point is not about memorizing the definition without having discussed it too much so I wasn't very precise the rank really is the number of keys that are strictly smaller okay

3:59 Clicker Question

5:09 and so Force the correct answer the easy way to work it out would be to exploit that I've drawn the PST as you always should so you can just pretend that there's this array of sorted of the sorted keys and so when 35 is here there's four other keys to the left and these are strictly smaller that's that's one way and we'll find a more algorithmic way on how to do this on on binary search trees in a second but basically if you walk down this path to 35 you run along all the keys that are smaller in some way the the trick is we don't really want to visit them all and count them one by one that would be fairly slow right if I asked you for 97 you would have to visit all the nodes in the tree we don't want to do that

6:16 this is a nice trick that allows you to do this without visiting every node and that's called an augmented binary search tree so I'll uh I'll just draw this like this um but what we really do is we have another field for each node where we store a number and the number is the size of the subtree how many keys are in this subtree including the node so all the leaves that have just null pointers have a one this one has a 2 because it's these two then four for these two 16 is because that's the size of the entire the entire symbol table at this point okay now how is how is that useful to um answer these operations let's do our example from the question again

7:16 that's really the only thing I taught you about binary search trees so what else uh what else should we do now we can find 35 this way but how can we work out the rank how can we work out how many elements are to the left of it and the trick here is that there's two types of nodes that are to the left

7:45 which I would say are skipped in that we continue working to the right and we leave them on the side and there skipped notes these are the notes that we explicitly skip because they're they were smaller than the value we're looking for and we visited them those are the notes on the search path to the left of this line okay so whenever we make this this turn of the search path uh back to the right that's one of these nodes that we skip so we can count how many there are of these but that's not all we also have skipped subtrees and these are the entire subtrees hanging left from the skipped nodes and from other nodes but turns out that we always visit those so uh we only have the left sub trees of the red nodes so we have to skip all of these in the tiny example that's just a single node each but you can easily imagine how this could be arbitrarily big so how can we know how many we skipped well luckily the augmented search trees store the subtree sizes so we can just add up all their subtree sizes okay so in this case we have a contribution of two red notes skipped and we have sub trees with total size

9:15 two skipped if you add up these two things you arrive at four and that's the rank of 35. okay we also wanted to have a look at this opposite operation select so let's revisit what that means I give you an index I it should be the index should be like in an array right we start at zero and N is excluded um but other than that if you if you project the elements down I want to access the ith element in this sorted array except that the array is not really there it's just in my imagination so I can't really use that but that's that's the idea so how can we how can we select um

10:00 Select

10:14 another obvious thing I should have stated Rank and select are opposites of each other if I call rank of 35 I get back the index 4. if I then say select four I should get back 35. that's in that's the way in which they are inverses of each other so let's use the same example and try to select the fourth the element at position four we start at zero so it's the fifth smallest in a way

10:45 how do we do this how do I know at the root whether I have to go left or right I don't have a key oh my God I'm screwed now we do have a rank though so we somehow have to find out if uh is the fourth smallest in the left and the right sub tree and we know how big the left subtree is it has nine elements that's plenty enough to cover position four all right so we have to peek down into the left subtree

11:17 to get its size and then decide yep um 9 is bigger than four so I I can go to the left I have to be careful that I'm starting with uh with one so there's an offset here I'm starting the index counting at zero where subtree sizes they count things so they don't start at zero but that tells me where to go left or right same as before okay now I'm at this point I'm still looking for the node with index 4 in this subtree I can do the same I can peek to the left and I notice no this is uh this is too small this time there's only one note in there but I'm looking for the the fifth smallest so this time I have to go to the right okay uh I do go down here to P get the size and then I come back and decide yeah I have to go right

12:26 now at this point we cannot continue looking for the fourth smallest in this subtree that wouldn't be the same as the fourth smallest overall a position for fifth smallest why did I start counting at zero uh we're trying to look for the position four in the global array but now going to this subtree means we're cutting out this this sub range of the array so we have to adapt the rank that we're looking for and how do we adapt same as before we subtract one for the note that we skip because we visited it and we subtract the size of this sub tree because these are all the elements to the left of where I am now all right so here's here's the green one that I skipped here's the red one that I skipped and the green one that's really the one from the subtree size could be much bigger than a single element okay so at this point I have to look for the element of at position two if I re-index this right relative to this array the indices have shifted clear that's the only little little trick where you have to be a bit careful uh then the rest is fairly straightforward we look again uh Peak down here no that's the wrong

13:58 four is big enough to find position two so I go there then I have again picture from before I peek to the left I find no that's not enough there's not enough notes in the left subtree so I don't go there

14:20 instead I have to go right but I have to subtract again so here I'm I'm looking for two and then -1 for this guy and not another minus one for the sub tree that I'm skipping which works out to zero right so in this case we're looking for the node of position zero which is which is the same as saying the leftmost in this subtree because there's no left subtree at this point we found our 35. so there's a reason why I did select as the last operation is a little more uh cumbersome or there's a little more tricky cases to distinguish because this the rank we're looking for changes but it follows really the same logic from before you have to you have to subtract things that you skipped in rank you have to add it and select you have to subtract it

15:18 Why store subtree sizes?

15:22 last little question I I kind of presented the solution to you before explaining why we don't do the obvious thing if we want to have the ranks of elements why don't we store the rank of rank of each node that sounds like the most obvious thing it would certainly make Rank and select much easier than the than the complicated procedure I've shown you so why bother

15:50 the reason is we want to maintain this upon insertions and deletions remember Dynamic array we don't care about static for this one and so if if you kept the ranks imagine um

16:09 imagine there was a huge subtree over here and you're you're inserting a new element here the insertion of this new element was cheap right you just walk down two steps stick the new note there suppose there was a null pointer before but now suddenly the rank of all the this huge pack of elements increases by one because there's one more smaller element so there's really just no way we can update those in time proportional to the height of the tree we would have to go to each and every single one of them and update their rank that's not possible not without any like uh not without tricks that come out to be equivalent to what we're doing already so um there's always this little devil on my shoulders you can't you can't leave something that's not correctly in all that's not not true in all ways of understanding what you said uh but we can't really update all those notes we would have to visit them all so instead we update we maintain something that's cheaper to maintain we keep something that's cheaper to update now for the subtree sizes that works because the sub tree size is only something that looks downward in the tree so for this red note we would have a sub

17:27 tree size change for this one and this one and this one but that happens to be exactly the notes that we visit anyways on the search path so we can stick a plus one in each of their sub tree size Fields while we're on our way to finding the node find doing the insertion and similar for deletion okay that's why the select procedure is a little more cumbersome to make but it's the only way to keep that maintainable upon insertions and deletions

18:20 oh it's the height again yeah subtree or is it the home find the tree overall uh it's it's just an upper bound okay so uh in a way the statement is a worst case statement what it says is okay one step back Big O of h means it's an upper bound it's at most some constant times h uh asymptotically for a sufficiently large n ignoring constant factors that kind of thing right Big O what's this upper bound so it could be cheaper sometimes that's number one if we're making such a statement without saying anything it assumes the worst case so it could be that the new insertion is the deepest down in the tree that it could possibly be

19:10 um and so it could be that your specific insertion actually triggers as many changes as the tree is tall many other operations can be cheaper yeah in this example we would have three changes whereas the tree could be much taller uh worst case that would be the the same yep