Video 2-7: §2.7 Ordered symbol tables

0:00 Ordered symbol tables

0:04 in this section i want to talk about ordered symbol tables which is really why binary search trees are good um i'll come back to this in a second ordered symbol tables is an extension of the abstract data type of a symbol table it has all the operations that you've just seen before but it has a few more that come in handy in particular you allow to find the smallest and largest key

0:34 you can find something that's that's called floor and ceiling here if you're given a key you can find what is the largest key that's smaller that is in the data structure that is contained in the dictionary or the the largest that is smaller sorry that's what i just said or the smallest that is bigger so same like um think of floor as being on the set of positive of the set of all integers you can ask for any real number uh what is the floor that is the biggest integer that's smaller than that real number less or equal than that number okay that's that's the definition of floor uh and and ceiling is similar and you can do this in general in in a ordered symbol table now you might wonder why why this is useful but suppose you have a dictionary storing english words then for example uh a crappy spell checker could say the the thing you typed is not in the dictionary this is not a proper english word but look there's one that's close in the alphabet to what you typed maybe that's what you meant that might be it's not a good way because probably you make a typo also in the first few letters and that wouldn't be caught by this

1:53 as uh just one one example the last two look even more esoteric but are actually very very essential for a core abstraction that i'll come to and you can read about it below so rank of a key is the number of keys that are stored in the symbol table that are strictly smaller so in in a sense it's if i were to insert this key the house how many smallest the house if i would insert it then it is the rank x the smallest terrible in the data structure afterwards and select is the the opposite um i can tell you i want the 4d tooth smallest from that symbol table and you would give it to me that's those two operations uh why do why do i think that these are really essential i you can think about those as implementing an array where you can insert at any point and at any position without copying elements around the rank just serves the the purpose of an index and by select you can jump to any position in in the sorted list without really having to have it in one contiguous piece of memory

3:19 uh and in that case yeah you might even do away with the keys if you wanted you could uh just represent the keys implicitly but that's yeah so this is a way to implement a string which is a list of characters right where you can add a little bit of text at any position this is or at least used to be the data structure that text editors were using if you maybe thought about this at some point there's text editors where you can type along and then save your text they have to represent the content of the text file somehow and one way to do this is is like this where um you you store the text in a big binary search tree and then at any point you can insert wherever the cursor currently is you can insert at this point without copying everything around

4:15 now i think modern text editors use a slightly simpler data structure than this because they figured out people are not using text edits in a in an adversarial way and there's there's cheaper ways to do it but absurd from the abstract point of view a binary search is a good way to do it

4:40 another point i want to make here is if you don't need the ordered operations if you just need the symbol table you might actually want a hash table in practice a hashtag is a different way to implement a symbol table that we will not talk about because i couldn't fit it in this class along all the other things but you should really know what a hash table is if you want a computer science degree so maybe you want to read it up and this is also the way how python implements its built-in dictionaries their hash tables which means python dictionaries cannot really efficiently do these things if you need that you need a different implementation of dictionaries but like in this in this truly dynamic array or this this rope data structures for strings so

5:31 that's what it's called uh if you use it for a string it's a name people coined i don't know if it's a good name but it is a name then you need you need really an ordered symbol table

5:48 okay let's see if you paid attention uh here's a little example i just want to see if you have the definition in your head what is a rank of 35 i hope it's just big enough so 35 is here

6:39 eleven there's a few more people in here you have to tell me if i'm asking you to work on an example that you can't see anymore all right uh we have lots of votes in and it seemed fairly clear so let me show this uh you could see the last one so four is um yeah i know you keep changing your votes don't you

7:38 let's briefly see why 4 is the the right answer remember that we we draw binary search trees so that the keys nicely project in x direction while projecting y direction onto the x axis in sorted order so this is the smallest second smallest and so on so this would have rank 0 1 2 3 4 because there's four keys that have a keys smaller than 35 all right that was what rank does the nitpick here maybe is that it's it asks for strictly smaller you could argue with me whether you want less or equal here or strictly less uh depends what you want depends on the application but here's that was my definition for now now you might think about how can you implement these operations rank select and their other friends in a binary search tree and it turns out with the binary search trees that we had so far you can't really do it

8:25 Augmented binary search trees

8:45 instead what you need is what people call an augmented binary search tree and the augmentation on the slide is just there's a little a little number floating around each node so we add another field to every node and the field that we add is the subtree size that's the number of keys that are below this node so the number of descendants including the node itself so for example all the leaves have one then this one has two because there's two below it this one has four and you can check that hopefully the other is all correct as well now how does that help um in answering these uh operations

9:33 let's see how we can do rank and maybe we do the same same again as an example 35 how can we work out the rank of 35 without looking at the tree in its entirety remember what we want to do is just follow one path we don't want to read all those notes the running time should still be dominated by the height of the tree not the size of the output not the number of keys that are smaller so the way to go as always in binary search trees is we start with a find

10:14 until we reach this node 35 uh now there's a few things to to look at we want to count the notes that are to the left of this of this note 35 and there's two types of such notes there's those that we explicitly touched when we were moving down our search path there's two of these so we can count to two of uh already we know that whenever we took the the right child pointer we know we have to add one because the note we just left is one of those to the left of the final target but there's more there's the subtrees that we omitted here

10:56 now how can we count those in this case it's always it's just one one node each but it could be much bigger so what we do is we peak into this subtree and get its size from the root because every node stores its subtree size it's enough to go this one step off the path to know how many notes have we skipped by taking the right pointer in this case sorry right for you okay and so here if you sum up we have two red things that we skipped and two green pointers every two green nodes that we skipped that makes up four and that's the that's the rank of 35 makes sense

11:43 so maybe just one this is on the slides as well and so we can get the sizes of we need the augmentation for getting the size of these red subtrees that we skipped in constant time as opposed to walking along the tree and counting

12:13 um we can also do select in a similar way it's a little is a little more subtle maybe let's do the same one we want to find 35 again so we want to find the element off rank 4. how do we do this

12:34 we start at the root as always we do our our search now i need to know whether i have to go left or right and here the the trick is we have to go a little detour uh we know that this node overall has 16 nodes below us but that doesn't tell us how many are left and right instead though what we can do is we take a look at the left child's subtree size and this says nine so there's nine elements to the left of this and we compare this with our rank our rank is four we want to find the element of rank four and there's nine things in the left subtree that means we have to continue in the left subtree

13:21 yeah i keep getting confused because it's mirrored for you now uh here again um we know that this guy has many things below in its subtree but what we really want to know now is do we have to go left or right so at this point again we peek into the sub tree and get the one which tells us there's only one in the left that's too small we want the fourth so we have to go right

13:54 now so far so good but now it gets a little tricky because if we go into this subtree we have actually cut off two nodes so in the subtree we are now looking at rank two

14:11 we no longer look for rank four that was for the global tree we've excluded two nodes already so we have to sub uh to adapt our rank we have to subtract the nodes that we skipped and but again we know how many because there's the one on our path and we get the size of this subtree from looking into the child so we can calculate what rank we are we're recursing on

14:38 uh so one more step and i'll do it a bit quicker so here we check this guy this is big enough for rank two so we go to the left

14:50 and here we peek into this one one is too small so uh if this one is is um one then actually rank two is is to the right but now we have again two nodes that we have to exclude so here we excluded these two here we excluded these two so we recurse on this node on this subtree but now we want to find the node of rank zero in this subtree

15:16 and well because this one doesn't have a left child the root is at rank 0. and so we return the root which is 35 okay i know this is this is the most subtle of the of the algorithms that we looked at because you have to adapt the rank while you're going but it's the same concept as before you just exclude some notes and you can calculate how many you excluded

15:44 Why not just store the rank of every node

15:46 now i've shown you the final solution how you can augment binary search trees you might wonder because i was talking about ranking select why don't we just store the rank of every node in each node that would have made life much simpler much easier and we wouldn't have needed this weird adapting the rank and all that nonsense now uh you could try to do this but you can't maintain it if you insert an element um think about it as follows so we have a a little tree

16:32 so there could be a huge sub-tree to the right here and now you add a new element here on this side then the ranks of all those guys change and there's just no way how we can possibly visit all those notes in in the short time we spend on walking down the search path we can't visit every other node in the tree and update its rank add one to the rank so that won't work so that's that's the reason why we go for subtree sizes instead because the subtree sizes of all these guys is not changed if we insert something in another unrelated part of the tree and on the other side all the nodes whose subtree size changes must have been on the search path because something changed below them so we must have come across them while we were searching for the for the node in the first place so we can definitely in in order h we can go and update them all