Video 3-5: Symbol Tables and Binary Search Trees

0:02 In the next section, we'll look at symbol tables, which is the abstract data type behind the priority Q, the binary search trees that the slider question here was getting at. And because people are more familiar with these, it seems. Um, let's get started with that. Symbol table is the maybe most important abstract data type of all. You have this operation to associate a certain value with a key and you can read out the value associated with some key with no assumption on the keys themselves other than being being comparable with greater or or um lesser equal or equal.

0:48 And the special case where k are the first n integers is precisely an array then you can just use the array index. But in the general case you cannot do that. And then um you have to use a symbol table. So it's the symbol table is is the name that uh cedric and Wayne use in their book and that people have seen in in algorithms data structures. There's many others that are that are used synonymously and depending who you ask um it's either called one of these terms. Um I guess for for Java it would be map and in Py Python it's even a built-in type dictionaries. Um some of the other names are also used sometimes. The key operations is is put which is the insert operation. It's called put because it might also have this value K already as a key in there and you're just associating a new value with it. Um but it it also handles insertions and then get is like a lookup and you can also delete keys and just test whether something is in the symbol table.

1:58 I would say this is the most basic fundamental building block in computer science. It is also at the sweet spot between being super versatile and useful and not completely trivial to build. So uh the best of um all in teaching and I I don't know of a programming language that has not some form of symbol table built in. Now Python is famous for not having binary search trees. That's a different story. But some symbol tables they still have. And at the end of the chapter, we'll see the alternative.

2:32 But now, um, just the abstract view. You can think of symbol tables as like a mathematical function with two caveats. Um, we think of mathematical functions as values that don't change. If you take a function and you uh associate a different value with one of the elements, then it's a different function altogether. Whereas for simple tables, we think of these as a dynamic mapping that retains its identity and you can change it over time. Uh that's kind of the the difference in the semantics. Otherwise, uh at first glance, it is like a mathematical function. Again, before we look at sophisticated solutions, let's make sure these are needed. What if you do something very simple, an unordered list? You can still use uh a fast implementation of put by just adding a new key value pair at the end of your list uh or at the beginning of your list and then get can go can walk from the beginning to the end of the list and for the first time you find the key that you're looking for you return the value.

3:36 Uh this is way too slow to be useful because you're doing this linear scan and uh it has also the problem that I'm just appending I'm just prepending new mappings of the key values. So um my total space is the total number of put operations and not the number of keys in my dictionary. Uh both both bad enough in its own on on their own. We can also try um a sorted list but as long as it is a linked list with pointers to the next elements.

4:12 Get is slow because uh I can't really do binary search and put is also slow because I need to find the place to insert and that I cannot do binary search for. So it seems here sorting the elements didn't hurt didn't help at all. Of course it's not entirely true. There is this thing called binary search that I'm sure people have seen. If you have an array of sorted elements, then you can speed up the search as follows. You jump to the middle and compare if the sorted key 69 is larger or smaller than this middle element 63. And if so, then you know that everything on the left side cannot contain this 69.

4:58 So you're halfing the number of elements you still have to look at in one step. And you can keep doing this each time you cut in half elements you still have to look at. And eventually either you find the element there or it's not in your dictionary or your list. Uh that's great. Um if you analyze this, you have the remaining elements in each step. You can only half the number of elements and stop at one for login steps roughly plus one for worst case you don't get exactly half but you have one more element left but crucially this needs an a way to jump into the middle of your list and if I have an array I can do that but then I cannot easily insert in the middle because there's no way to insert into an array without copying everything to the >> [snorts] >> And if I use a linked list then I have no way to jump into the middle. So that's the fundamental shortcoming of these data structures of the simple constructions. They either cannot do binary search or if they can I can't use it because I can't insert there.

6:16 And that shortcoming is what binary search trees address. You should really think of them as a version to make this binary search on an array dynamic and we've seen this question um before and people remember this. So what's a binary search tree? Uh it's a binary tree as the name suggests where every node has a left and a right child but both of them might be either of them can be null. So then there is an empty sub tree. Uh and it has to be search a search tree order tree or it has to have the search tree property which means everything in the root is larger than uh the key in the root is larger than everything in the left sub tree uh and smaller than everything in the right subree.

7:10 How to represent this in in computer in a computer is usually in in an object-oriented language. You have some uh some special class where you store the key and value and then you have pointers for the left and the right sub trees and you can allocate one such object per nodes and keep these pointers so that you can navigate from a parent to the children. Okay. Um here's an example what this can look like. Uh there's a um bunch of numbers here. So I'm only drawing the keys, not the values. And you see how it satisfies the search tree property if you take every node and project it down to on the x-axis and write down its value here and then keep its left subree entirely to the left and its right sub tree entirely to the right of that vertical line. If you do that recursively for all the nodes, you'll see that it precisely gives you the keys in sorted order.

8:12 That's an if and only if. It's exactly a search tree if this procedure gives you the keys in sorted order. And so you see if this was an array, you can now try some almost binary search on it. You don't get to choose the middle. The middle is the pseudo middle is chosen for you. It's always going to be 77. But you can still do searches of the type. For example, searching for 63, you would start at the root here and check if 63 is larger or greater than 77. Of course, it's is smaller. So, everything here is excluded from the search. And in the tree, this reflects by moving to the left to the left sub tree. Now again the 12 you compare it with 63 and it's larger so anything on the left of this side is is uh no longer interesting and you go to the right sub tree and you keep doing this you're not going to exactly cut the remaining number of elements in half but ish if the tree is not uh too bad and then after a while you found your element or maybe you found you're in a null pointer and then the element is not in the tree.

9:42 That's how searches work. And um the hope is that usually you won't follow too many pointers down. We'll come back to that uh in a bit.

10:01 Now you can also insert and that's where really search trees shine over what arrays would have done. To insert say this uh element 88 you first do a search for it. So you start at the root follow follow and then 88 here you end up in this null pointer which means 88 is not in the tree yet. Fine. We want to insert it. So um that's okay. Then you make room here and um add a new node 88 for this inserted node and link it to exactly the place where you found the null pointer. Okay, that's how you insert. And um in an unbalanced binary search tree, that's all there is to it.

10:51 The other thing that you want to do is delete elements. And um that one's a little bit more interesting because there's different cases that you can run into. Um the most easy case is if you say delete 11. We start with the search and we find 11 here and it is a leave. So in this case I can simply drop that note which means in the parent set that left child pointer to null and the 11 is gone.

11:26 The next one is that what you want to delete is not a leaf but is a unary child, a unary node. So it has a single child. In this case, you cannot simply delete this, but you can rewire the parent to now point to your single child. And this will always just work. Uh, a bit more tricky is if what you want to delete is a binary node like um in this case, there's no way to just uh reconnect my parents to two things when it only has one slot to be uh redirected. So, we have to do something different. And what we do here is that we first we keep this node in mind as to be deleted and we try to find something that we can swap it with. So, uh, instead of deleting 85 as a note, I'm going to delete one of the adjacent keys in the tree, for example, the successor, which you find by going one step to the right and then as much to the left as you can until you hit the null pointer here.

12:30 Then you're going to swap the 88 with our 85 and instead delete the 85 here. And the point that why this can't keep going is that this node that you swap it with is a leftmost child. So it has to have a left null pointer. So you're back into one of the easy cases. So you're never going to have to do this more than once. It's find once the node you want to delete, find the successor, and then you're done. [snorts] Um also for this uh I coded up some animation. I think for the current level um of of complication we may not need to go through this. Um, if you want to remember this in more detail, um, I can put the link on the website and you see on the right the Java code from Cetri and Wayne, but it's otherwise doing exactly what I what I described.

13:46 Uh, so far so boring. Um, what uh is a bit more interesting is to analyze how well this works. And first let's do everything in terms of another unknown quantity. The height of such a binary search tree. It's defined in the same way as before. It's this uh longest path from the root to any leaf. And you count the number of edges on this path. Then um if you fix h to mean the height of your tree, all these operations that we looked at are essentially bounded by the height. For search, you follow literally one path down from the root somewhere. You may stop early, but you may go all the way down to a leaf to a null pointer in the leaf. So, at most H+1 comparisons get you there. For an insertion, well, you first do a search and that costs essentially the same. Then attaching a new leaf is one extra step.

14:44 uh for a deletion you may have uh if you first think about it a path and then another path but they together are at most a height so even there the comparisons are kind of bounded by the same quantity h+ one u certainly it's big O of H if you want to be less precise so all of the operations that we've looked at are bounded in terms of the height of this binary tree so you could say the height of a binary search is really an interesting to interesting thing to know and uh let me set up the work there and we'll probably do the analysis then uh tomorrow. Uh but let me explain what we'll do. Uh here it's formulated in terms of the height. Now I have a confession to make. The height analysis is rather tricky and I'm not going to be able to do it with you. So instead we'll analyze something different which in a way is just as good. It's a bit slightly different notion. The height if you think about it is the worst case of how long it could take if you start from the rooe and walk down to a leaf. That's literally the definition. It's the longest route to leaf path.

16:05 Uh what is easier to analyze instead is um summing up the the length of the path from the root to any node in the tree and then you can divide by n again then you get the average depth of the node or the average length of a path down the from the root. That is not exactly what we want. Um I'll appeal to your uh understanding here at the end. I'll quote the result for the height and it's just a constant factor difference. Uh the analysis is rather um rather more tricky. Um, also let me mention before we get there.

16:59 In the worst case, this is really, really bad. In the worst case, the height is just linear because you could have a tree that looks like this.

17:23 And then the height is n minus one. If you think back to what this means for our operations, linear time, that's just as slow as if you had a linked list. And of course, this literally is a linked list. You're just not using your left pointer at all. Now, uh this is a maybe very degenerate case, but note that there's various um mixed versions of trees that look a bit like this where you sometimes use the left, sometimes the right pointer, but it's of course no no better. So the worst case is rather abysmal and it would be just as slow as a linked list.

18:17 Now, of course, there's different ways how to deal with that. One that you've probably also seen in some uh previous data structures lecture is to use balanced binary search trees. Now, we'll come back to those. they are a different data structure and uh somehow avoid this case from being possible in the first place. Um another way is to say ah uh fingers crossed let's hope and pray if the if the insertions are not adversarially chosen it's actually very unlikely to see such a tree. So option one is balanced search trees and we'll come back to that. Option two appeal to um our luck that the insertions are not coming in an adversarial order. And so specifically we'll assume what's written here that the insertions come in random order. So if you post hawk fix the keys in your tree suppose they were coming in random order. Um this is actually equivalent to something slightly different.

19:47 Um It's the same thing as demanding that the keys are chosen independently from some fixed distribution. So I guess formally I should say ID and from a continuous distribution ideally so that there's no ties with probability one.

20:31 And um under this assumption, so if if the insertions are just random, it turns out the binary search trees even without any balancing behave extremely well. In some sense, better than a balanced search tree. Okay, we'll do the proper analysis tomorrow. Um here's just u the start of the analysis and why this this quantity may be even amanable to analysis at all. If you let CN denote this uh expected total search cost, so the cost to search every key in the tree exactly once, then you can set up a a recurrence relation for this where you have some tree in the root, some some node in the root and then there's a left subree and a right sub tree of some different order or different size and the size. So the the question is what index does this root element correspond to if I write my elements in a sorted array where oh left first then the root then the right as we've seen in the examples and um under this assumption if everything is is uh uniformly chosen or the elements are chosen independently this position where the root lands is uniform among the n positions.

21:55 So if you want you can write r is equal in distribution to a uniform random variable of this range of allowed indices. Uh okay I'm writing the rank not the position in the array. So let's stick with that. So it's between one and n. And then if that is fixed conditional on that the left and right sub tree sizes are given by R minus one N minus R keys. And so I can apply the same recursive uh the same analysis recursively to the sub trees.