Video 5-5: Binary Tries

0:02 In the next section, we'll look at sorted dictionaries for integers. And we'll we'll start with some uh easy basic data structure that's is the basis of the more sophisticated ones to follow. But before we get there, um I should motivate a bit why we don't do certain things. And what do I mean by that? Uh first of all, this quick reminder of what the ordered symbol tables uh operations are. Um we talked about those earlier in the module. Just as a reminder, we want to have some order of the elements so we can ask for the smallest and largest elements in our set. Uh crucially, we can also find an element that's not in the set and find the closest elements that are in the set. Floor and and ceiling or predecessor and successor. Um in this chapter, I'm going to mostly talk about these names because they're what is used in the literature for that area.

0:55 Um this particular predecessor is the standard name for the problem that we'll look at. Uh but it's the same that I used to call floor and ceiling before. And we have rank and select where you can find how many keys are smaller or you can find the so manyeth key in sorted order in your dictionary. All of these, of course, classically solved with augmented binary search trees. For the first three, you don't even need the augmentation. Augmented means we store subtree sizes. We've done that in the first part. Uh and you can do various various schemes of randomization or or other tricks. Uh sub- subtree sizes are needed to solve these last two. Maybe already a hint that even for binary search trees, there's a hierarchy. There's simpler operations, the first three, and more sophisticated ones or more more demanding ones, rank and select.

1:54 Now, uh in terms of integer data structures, this distinction is much more stark. And I'll have a section at the end of this unit specifically about lower bounds for integer data structures where we try to show, or at least I'll I'll I'll state some famous lower bounds that are known. And I'll prove some simpler versions of those. Uh one of these, informally speaking, um says if I want to maintain a dynamic set of integers, here is important that I um can insert and delete. And I want rank and select queries, then I have to pay essentially n log n over log log n time for each operation. Even though this is on the word RAM where I can do, you know, w bits at a time, etc. I cannot beat binary search trees by much. I can beat them a bit. Asymptotically still a very different beast to have log n or log n divided by log log n.

2:52 Practically speaking, not really, right? It's a very close. And so um I'm going to very briefly visit how you can achieve this. You can There's a data structure that matches this. And I'll briefly sketch this, which is uh appropriate for the data structure as well because it's based on sketching. Um but I'm not going to focus on that as much. Uh rather, I'm going to focus on ignoring rank and select. Because if you take the rest of the uh sorted dictionary data structures, which by and large is just predecessor, successor is is sym- uh symmetric. And min and max are kind of, at least for the data structures we look at, trivial to do. So, um if you want insert and delete and predecessor on top of maybe look up, which you can do with predecessor as well, uh then you can do much better than this binary search tree bound. So, that's why we focus on that restricted subset.

3:57 If you ask for all of the sorted dictionary operations like binary search trees offer them, you're stuck with this lower bound. Now again, uh, this lower bound is only true if you need dynamic sets, if you can insert and delete all the time. Um, now I'm uh, I'm thinking um, if this set set is static, I guess it's If the set is static, then you have to talk about the space of the data structure, otherwise you can precompute all the queries. Let's not get into that. Um, we'll revisit these questions at the end. Okay. So, uh, one last remark which is on the slide here is because min and max are easy, and I can do general insert and delete, I can build a priority queue with what I've got here. I can insert, I can find the minimum, I can delete an arbitrary element, so I can delete min, and I can even do decrease key by just deleting and reinserting.

4:58 So, if we can do insert, delete, and predecessor, plus min and max, which I promise you are easy, we have a full priority queue. Uh, which also means um, for integer data structures, there's a big difference between the full sorted dictionary sorted dictionary and the restricted priority queue operations. Now, I haven't told you how well you can do insert, delete, and predecessor.

5:28 And I won't for a moment, but let's see what we can do easily. The first um, major insights uh, is that integers are essentially strings. Um, you can see them as as bit sequences or or ones, so we can use any string data structure and use them to store integers. So, let's use tries. Um a binary trie is the most convenient in this case, and I've drawn it here in a way so that you see which other elements of the universe are missing. So, here clearly my my universe is uh uh zero up to two to the four. Um and I have these four keys, uh otherwise known as 3 9 10.

6:17 Sorry, no, that's not 10. It's 12 and 13. I can maintain these in my trie like I would normally do this for strings. Um the first data structure that we look at is just that. It's this trie with two little simple additions. Uh for one, I'm going to store the leaves in doubly linked way, so all of these have forward and backward pointers. And I guess we have some uh sentinel values on the left and on the right.

6:57 And the second is um that nodes have an additional pointer that allows you to quickly jump to some leaves. You'll see in a second why that's uh needed. And the rule here is um there's maybe maybe simpler ones, but uh that that one works. If I have a node that is not binary, I only need these jump pointers if a node has a missing child. If it has a missing child and it's the right like in this case, then I point to the rightmost leaf in the subtree. Um same with this guy. Uh say here we have a node that has a missing left child, so we point to the leftmost leaf in the subtree. I'm not sure if I want to include the minus infinity here or not. It shouldn't matter. So, all of these would have these pointers. There's only this one missing really, right? And this guy. In my simple in my tiny degenerate example, this seemed to not do much, but imagine a like bigger examples, this might the blue pointers might go many levels down.

8:03 Why do we need these pointers? Um First of all, it's easy to maintain these two type of pointers if you do updates. Uh if you add a new element, you have a new leaf here. You have this new path. Um I can insert this leaf into the linked list in constant time once I have this found and I know the predecessor successor. And these I can get from the jump pointers of these nodes where I left. And then follow one successor. So, I I can always find one adjacent element quickly and then the other one I get from the linked list. And also these jump pointers, um I basically need them for the new nodes and I need them for potentially uh nodes that now uh have me as their jump pointer as opposed to where they pointed earlier to. Um And this example, there is no no such one. Uh this one has the jump pointer here.

9:15 So, that's uh that's the one thing you can maintain these without extra cost. What do I mean by extra cost? Well, uh the cost for searching and updating a trie is linear in the height, right? I have to walk down uh my my trie to find an element. And if I insert one, I also have to walk down. If I fall off the trie while doing so, um I'm going to add all these nodes, but the number is still bounded by the height. So, all of all of these, um, operations are in order W time if that's the height.

9:56 And, um, most of the time here we'll set the length of the integers to be W bits. That was the standard assumption. And, the the reason why we have these pointers is that we can simulate predecessor and successor queries. How do we do that? Um, let me maybe, uh, copy this slide so that I can draw this cleanly without this addition here.

10:34 So, what do I need to do? Uh, let's try to do the predecessor of five, which would be 0101, right? I would search for this string in the trie. So, zero, now I would like to take a one. This, of course, should be a one. Uh, same here. Ah, fun. Okay. Ignore the zeros in the grayed out parts. I probably messed up the picture. Uh, you know what the right link should be a one. So, I would have wanted to go down here, right? But, there's nothing there. Now, if ever that happens, I found the longest common prefix of the thing that I'm searching to some to any of the numbers that are stored. Here, there's there's only this one, but again, in general, I walk down the path of the trie as long as I can. Uh, as soon as I fail to be able to continue, I've reached the longest common prefix between my search key and any key in the data structure.

11:39 Now, that doesn't help me find I mean this this key need not be the predecessor in general. Or at least not not obvious. Um Maybe let's do the successor to make it a bit more interesting.

11:55 Same same principle. Uh I fall off the trie at this point. Now, because this guy has a missing child, which is the one I would want to follow, otherwise I wouldn't be stuck. It has an appropriate jump pointer that I can take. And so, this pointer takes me to the rightmost existing leaf in the entire subtree. Right? This That's the subtree, but actually this is the rightmost one. Now, my five would have been somewhere in this subtree. So, this guy is indeed the predecessor in this case. And I can use because I want the successor, I can use one of the linked list pointers to get to the next element in sorted order. And so, this is my successor, nine. Okay? That's how we use tries in kind of a a slightly different way. You would normally not do this for strings. It I mean, you could do this for strings as well if you want to find the the next string in your dictionary in alphabetical order from where you stopped. Uh where where you found the the search string.

12:58 It's not the very standard way to use them, but tries clearly support this. Okay? Now, how good is this? Um We can write down a theorem to state the result um of the discussion. We're storing a set of n numbers. They're all W bits long. Uh we can support updates and predecessor and successor queries as well as lookup. And the The is the height of the trie. Right.

13:36 Uh also, what's the space of the data structure? Um This is a bit pessimistic, but um I may have to store a separate path for each of these strings. If n is fairly small, then this is uh is achieved. Then I may have branching out for log n levels, and then I may have separate chains. Uh the bad case could be complete binary tree, and then long chains essentially down. If there is the n numbers here, this is height log n. Uh so, the actual space would be w minus log n times times uh n. Uh but this when n is small with respect to w may at least maybe this uh n times w. It may be a bit better overall, but it's not linear. And this is words of space, because this is the nodes in the trie. I need pointers and so on. Okay? So, in if n is substantially larger, if it's closer to w or maybe much larger than w, right? Uh It's maybe a bit bit pessimistic, but we cannot be sure that it's just big O of n at this point.

14:57 Now, you could try to get into making the trie compacted and so on, but let's not go there, because the main problem is that the height of the trie, w, that's actually a crappy search time. Why? Well, uh n is always going to be less than 2 to the w by definition. It's a subset of of that. That means log n is going to be at most W. In other words, W is larger than log-in. So, all that we've done so far is create a crappy binary search tree. Right? Which cannot even do all the operations. So, this uh is fine, but so far it's worse than um standard binary search tree.

15:46 But, we won't stop there. This is a building block that we're now going to be using to improve. And again, space is not great, but let's forget about space for the moment. Let's focus on the time. How can we speed this thing up? Um let me again stress one thing here. Uh I wish I had the Maybe I should have had the code somewhere on this slide. How does the search or the predecessor or successor search work? There's two phases.

16:30 Maybe I can copy the pictures I have to reference. Oh. There's two things we have to do. First, we have to find in the trie this longest common prefix.

17:15 I say I'm doing predecessor of X. I find the longest common prefix in the binary representation. And then the second step, uh this was some some internal node, right? And then in the second step, I follow a few pointers to find the actual guy I'm interested I'm interested in the predecessor. Which is follow one jump pointer and maybe follow one link list pointer, depending on whether I'm stuck where the left or the right child is missing.

18:25 Now, I I spelled out in detail these two steps uh to analyze how long they take. Because this first part, that's the slow bit. This takes time, potentially the height of the trie. We may be lucky to stop early, but usually you have to live with at least um W um as the worst case. Whereas the the second part was just following a constant number of pointers. That's already constant time.

18:55 So, if you want to improve on this data structure, we should focus our attention on the trie search, clearly.