Transcript
The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu. All right, welcome back to 6.046. Are you guys ready to learn an awesome data structure? Yeah. Let's do it. This is a data structure named after a human being, Peter van Emde Boas. I was just corresponding with him yesterday. And he, in the '70s, he invented this really cool data structure. It's super fast.
It's amazing. It's actually pretty simple to implement and it's used a lot in practice in network routers, among other things. And we're going to cover it today. So, let me first tell you what it does. So, it's an old data structure, but I feel like it's taken us decades to really understand. Question. not on. In what sense? It's not amplified. It's just for the cameras. So, uh it's taken us decades really to understand this data structure, exactly how it works and why it's useful. Um our the problem it's solving is uh what you might call a predecessor problem. It's very similar to the sort of problem that binary search tree solve, but we're going to do it faster.
Uh but in a somewhat different model in that the elements we're going to be storing are not just things that we know how to compare. That would be the comparison model. We're storing integers and the integers come from a universe U of size little U. So, and we'll assume that they're non-negative. So, from zero to U minus one, although you could support negative integers without much more effort. And the operations we want to support uh we're storing a set of N of those elements. We want to do insert, delete, and successor. So, uh these are operations you should be familiar with. You should know how to solve these in log N time per operation with a balanced binary search tree, like AVL trees.
Want to add something to the set, delete something from the set, or given a value, I want to know the next largest value that is in the set. Um so, if you draw that as a one-dimensional thing, you've got some items which are in your set. And then you have a query. Say you ask for the successor of this value, then you're asking for what is the next value that's in the set. So, you want to return this item. Okay, predecessor would be the symmetric thing, but if you can solve successor, you can usually solve predecessor. So, we'll focus on these three operations, although in the textbook, you'll see there are lots of operations you could do with van Emde Boas.
So far, so good. We know how to do this in log N time. We are going to do it in log log U time. Wow. Amazing. So, an extra log, but we're cheating a little bit in that we're replacing N with U. Now, in a lot of applications, U is pretty reasonable, like 2 to the 32 or 2 to the 64, depending on what kind of integers you usually work with. So, log log of that is usually really tiny and often smaller than log N. So, in particular, on the theory side, if uh for example, if U was polynomial in N or even larger than that, you can support N to the polylog N. Uh then log log U is the same as log log N.
Up to constant factors. And so, this is an exponential improvement over regular balanced binary search trees. Okay, so super fast. And it's also pretty clean and and simple. Though, it'll take us a little while to get there. Uh one application for this, as I mentioned, is in network routers. And I believe most network routers use the van Emde Boas data structure these days, though that just changed in the last decade or so. Network router, you have to store routing table, which it looks like for IP range from this to this, please send send your packets along this port. For IP range from this to this, send along this port.
So, if you mark the beginnings of those ranges as items in your set, and you given a a query given an actual IP address, you want to know what range it's in, that is a predecessor or a successor problem. And so, van Emde Boas lets you solve that really fast. U for IPv6 is only 2 to the Sorry, for IPv4 is only 2 to the 32, so that's super fast and practical. It's going to take like five operations to do log log 2 to the 32. So, that's um that's it. And as you may know, network routers are basically computers. And so, they used to have a lot of specialized hardware. These days, it's pretty general purpose.
And so, you want nice data structures like the one we'll cover. Okay, so we want to shoot for log log U. We're going to get there by a series of improvements uh on a very simple idea. This is not the original way the van Emde Boas got to this this concept, but it's sort of the modern take on it. It's the one that's in the textbook. Uh so, the first question is how might we get a log log U bound? Where might that come from? It's question for you. This is just intuition. Any suggestions? We see logs all the time. So, yeah. You organize the height of a tree into a tree. Ah, good. You organize the height of a tree into a tree.
So, we normally think of a tree, let's say we have U down here. So, the height is log U. So, somehow we want to binary search on the levels of this tree. Right? If we could kind of start in the middle level and then decide whether we need to go up or down. Un- totally unclear what that would mean, but in fact, that's exactly what van Emde Boas will do. So, you can binary search uh I think we won't see that till the very end, but on levels of a tree. So, at least some intuition. Um Now, uh let's think about this in terms of recurrences. Right? There's a recurrence for binary search, uh which is usually T if you have K things, T of K is T of K over 2 plus order one.
You spend constant time to decide whether you should go left or right in the binary search or in this case, up and down somehow. And then you reduce to a problem of half the size. So, this solves to log K. In our case, uh K is actually log U. So, we want a recurrence that looks something like T of log U equals T of log U over 2 plus order one. Okay, even if you don't believe in the binary search perspective, this is clearly a recurrence that solves to log log U. I'm just substituting K equals log U here. So, that could be on the right track. Now, that's in terms of log U. What if I wanted to rewrite this recurrence in terms of U?
What would I get? If I want wanted to have this still solve to log log U, what should I write here? If I change the logarithm logarithm of a number by a factor of two, how does U change? Square root. Okay, so I've changed what the variable is here, but this is really the same recurrence. We'll still solve to log log U. The number of times you have to apply square root to a number to get to one is log log U. So, this is some more intuition for where uh how van Emde Boas is going to achieve log log U. And in fact, this is the primary intuition we'll be using. So, what we would like is to some take our problem, which has size U, and split it into problems of size square root of U, so that we only have to recurse on one of them, and then we'll get this recurrence.
Okay, let's uh that's where we're going to go. But we're going to start with a very simple data structure for representing uh a set of N numbers from the universe zero up to u minus one. And let's say initially our goal is for insert and delete to be constant time. But let's not worry about successor. Successor could take linear time. What would be a good data structure for storing items in this universe? I want u to be involved somehow. I don't just want to like store them in a linked list of items or sorted array of items. I would like uh u to be involved. Insert and delete constant time. Very simple.
Yeah. Something on the right? In an array? Yeah. What's the array index by? Uh the index n Sorry? Like the index of n. The index of n? Close. Sorry? The value. The value. Yeah. Good. So, I want uh this is normally called a bit vector. Where you index uh you I want an array of size u. And for each uh for each cell in the array, I'm going to write zero or one. Zero means absence. One means present. It's in the set. So, let me draw a picture maybe over here. Uh let me take my example. Give you a frisbee. Uh so, we have um Let me put it in the middle. So, this is an example of a set with if I maybe highlight a little bit.
Uh here's a one. Here's a one. A one and a one. So, there are uh four elements in this set. The universe size is 16. n equals four in this particular example. If I want to insert into the set, I just uh change zero to a one. If I want to delete from the set, I change the one to a zero. So, those are constant time. Good. If I want to do a successor query, not so good. Uh I might need to spend order u time. Maybe I ask for the successor of this item. And the only thing to do is just keep jumping until I get to a one. And in the worst case, there's almost u zeros in a row. Or u minus n. So, that's really slow.
But this in fact will be our starting point. May seem really silly. But it's actually a good starting point for van Emde Boas. So, the second idea is we're going to We weren't going to take our universe and split it into clusters. Uh van Emde Boas the person likes to call these galaxies, I think. It's a nice name for uh pieces of the universe. But uh textbook calls it clusters cuz I used to call it clusters. So, uh Now, there's a question of how big the clusters should be. But if I gave you this picture and I want to think about these galaxies as separate chunks. And I asked for the successor of this, how could I possibly speed up the successor search?
Yeah. Uh because from the tree like drawing like for each cluster, I would connect You could form a tree here and store what at the I mean, you could store like an or Mhm. in the two bits. Cool. I like this. So, I could store the or of these two bits. And this up a little bit. Or of these two bits, or of these two bits. And so on. The or is interesting because it tells me uh this zero bit in particular tells me there's nothing in here. Uh so, I should just be able to skip over it. And do So, you're imagining a kind of binary search-ish thing. It's a good idea. So, each node here I'm just writing the or of its two children.
And in fact, you could you could do this all the way up. You could build an entire binary tree. Uh But remember what we're trying to do is a binary search on the levels of the tree. And so in particular, I'm going to focus on this level. This is the middle level of that tree if I drew out the whole thing. And that level's interesting because it it's just summarizing is there anybody in here? Is there anybody in this cluster? Is there anybody in this cluster? Is there anybody in this cluster? So, we call this the uh summary vector. So, we'll come back to your tree perspective at some point. That is uh a good big picture of what's going on.
But at this level, I'm just going to say let's store the bit vector. Let's also store this summary vector. Uh and now when I want to find the successor of something, first I'll look inside the cluster. If I don't find my answer, I'll go up to the summary vector and find where is the next cluster that has something in it. And then I'll go into that cluster and look for the first one. Okay? That's a good next step. Uh so, this will be split the universe into clusters. Um How big should the clusters be? To balance out. There's three searches I'm doing. One is within a cluster, one is in the summary vector, and one is within the another cluster.
Yeah. Square root of u? Square root of u. Yeah. That will balance out. If they're square root of u size, then the number of clusters will be square root of u. So, the search in the summary vector will be the same as the cost down here. Also, we know that we kind of want to do square root of u recursion somehow. So, this is not yet the recursive version, but square root of u is exactly right. And I also frisbee. Sorry. Here's one frisbee. And yeah. Cool. And I think I also owe you one. Sorry. Um so, uh clusters have size square root of u. The square root of u of them. And cool. So, now when I want to do uh to to do an insert or delete is still uh let's not worry about delete.
It's a little tricky. To do an insert is still easy. If I insert into here, I set it to one. And I check if this is already zero, I should also set that to one. Now, deleting would be tricky. To delete this guy and realize that there's nothing else. Uh let's not worry about that until we do a lot more work. Let's just focus on insert and successor. So, um insert with this strategy is still constant time. We It's two two steps instead of one, but it's good. Uh successor does three things. First, we look let's say um successor of x. First thing we do is look in x's cluster. Then, we uh if we don't find what we're looking for, then we'll uh look for the next one bit in the summary vector.
And then uh we'll look for the first one uh in that cluster. So, there are two cases. In the lucky case, we find the successor in the cluster that we started in. So, that only takes root u time. Uh if we're unlucky, we search in the summary. That takes root u time. And then we find the first one bit. That takes root u time. Whole thing is square root of u. Which is of course not very good compared to log n, but it's a lot better than U, which is our first method. The bit vector. So, we've improved from U to square root of U. Now, of course, the idea is to recurse. Instead of just doing a bit vector at each of these levels, we're going to recursively represent each of these clusters in this way.
This is where things get a little magical and the magic of dynamic divide and conquer. Um and then we'll get T of square root of U instead of square root of U. And then we'll get a log log cost. So, before I get there, let me give you a little bit of terminology. And example for dealing with clusters. Okay, in general, remember the things we're searching for are just integers. And what we're talking about is essentially dividing an integer like X by square root of U. And so, this is the uh whatever, the quotient and this is the remainder. So, I want J to be between 0 and strictly less than square root of U, then this is unique.
Fundamental theorem of arithmetic or something. Um and I is the cluster number and then J is the position of X within that cluster. So, let's do an example like um X equals 9. Uh so, I didn't number them over here. This is X equals 0 1 2 3 4 5 6 7 8 9. Here's the guy I'm interested in. 10 11 12 and so on. So, 9 is here. This is cluster number 0 1 2. So, I claim 9 equals 2 * square root of U here is 4. I conveniently chose U to be a perfect square. Uh and it is item 0 1 uh in within the cluster. And indeed, 9 equals 2 * 4 + 1. Okay? So, in general, if you want to know if you're you're given X, I said, uh look look in X's cluster.
What that means is look at X integer divided by square root of U. That's the cluster number and I'll try to search in there. Uh then I and I look in the summary vector starting from that cluster name, the name of the cluster for this guy, uh finding the next cluster, then I'll multiply by square root of U to get here and then continue on. Okay? In general, uh cuz dividing and multiplying is I don't want to think about it too hard. Um I'm going to say uh define some functions to make this a little easier, more intuitive. So, when I do integer division by square root of U, just like taking the floor, I'll call that high of X, the high part of X and low of X is going to be the remainder.
That's the J up here. Uh and if I have the high and the low part, the I and the J, I'm going to use index to go back to X. So, index of I J is going to be I * square root of U + J. Now, why do I call these high and low? Give you a hint. Here's the binary representation of X. In this case, high of X is two and low of X is one. Yeah. So, so the high X corresponds to the first two the first two bits and the low X corresponds to the last two Right. The high correspond high of X corresponds to uh the high half of the bits and low of X corresponds to the bottom half of the bits. So, these are the high order bits and the low order bits.
And if you think about it, remember uh when we take square root of U in logarithm, it takes log U and divides it in half. So, it's exactly in the bit vector, which is log U bits long, we're dividing it in half here and looking at the high bits versus the low bits. Okay? So, that's another interpretation of what this is doing if you don't like doing division as many computers don't like to do. All we're actually doing is masking out these bits or taking these bits and shifting them over. So, these are very efficient to actually do and that maybe gives some intuition for why they're relevant. So, um let's recurse, shall we?
I think now we know how this splitting things up works. So, I'm going to call uh the overall structure V or struct a van Emde Boas structure I'm trying to represent is V. Um and V is going to consist of two parts. One is point an array of all of the clusters. I'm going to abbreviate van Emde Boas's VEB. Um and recursively, each of those clusters is going to be represented by a smaller VEB structure of size square root of the given one. Okay? And uh I ranges from 0 to uh square root of U minus one. Okay, so there's square root of U of them. Total size is U. And then in addition, we're going to have a summary structure and this is also a size square root of U VEB.
Okay. Um We should think about inserts and successors. Those are the two operations I care about for now. Let's start with insert, that's easier. So, if I want to insert an item X into uh data structure V, then uh first thing I should do is insert into its corresponding cluster. So, let's just get comfortable with that notation. We're inserting into the cluster whose number is high of X. That is where X belongs. The name of its cluster should be high of X. And what we're going to be inserting recursively into there is low of X. That is the name of X local to that cluster. Right? X is a global name with respect to V.
This cluster only represents a small range of square root of U items. So, this gets us from the big space of size U to the small space of size square root of U within that cluster. So, that's basically what high and low were made for. Uh but then we have to also update the summary structure. Right? So, we need just in case uh maybe it's already there, but in the worst case, it isn't. So, we'll just think of that as recursively inserting into V. summary uh the name of the cluster, which is high of X. High of X is keeping track of which clusters are non-empty. We just inserted something into this cluster, so it's non-empty.
We better mark that that that cluster high of X is non-empty in the summary structure. Why? So, we can do successor. So, let's move on to successor. Uh Actually, I want to mimic the successor written here on the bottom of the board. So, what we had in the non-recursive version was three steps. So, we're going to do the same thing here. Uh we're going to look within X's cluster. We now know that is uh the cluster known as high of X. And either we find it and we're happy or we don't. Then we're going to look at V. summary, search for the s- the successor of high of X. Right? Finding the next one bit, that is successor.
Okay? And then uh I want to find the first one bit in that cluster. Is that a successor also? Yeah, that's just the successor of negative infinity, right? Finding the minimum element in a cluster is the successor of -1 or or 0 or not 0, but -1 would work or negative infinity maybe more intuitively. That'll find the smallest thing here. So, each of these is a recursive call. Can think of it as recursively calling successor. So, uh let's do that. I want to find the successor of X in V. Uh first thing I'm going to do is uh do the IJ breakdown. I'll let I be high of X and J be uh could do low of X, but what I'm going to try for is to search within uh this cluster high of X.
So, I'm going to look for the successor of cluster I, which is cluster high of X of low of X. Okay, so that's this first step of looking in X's cluster. This is X's cluster. This is X's name in the cluster. I'm going to try to find the successor, but it might say infinity. I didn't find anything. Okay, then I'll be happy then I'll be unhappy if J equals infinity. Uh so uh that's line one. The next thing we're going to do is well, then we're in the wrong cluster. High of X is not the right cluster. Let's find the correct cluster, which is going to be the next non-empty cluster. So, I'm going to change I to be um the successor in the summary structure of I.
So, I was the name of a cluster. It may have items in it, but we want to find the next non-empty thing because we know uh the successor we're looking for is not here. Okay, so this is the cluster we now belong in. Uh what item in the cluster do we want? Well, we want to find the minimum item in that cluster. We're going to do that by a recursive call. Which is J is the successor within cluster I. Of uh minus infinity, I'll say. -1 would also work. So, this will find the smallest item in the cluster. And then uh IJ in both cases we get I and J, which together in this form describe the value X that we care about.
So, I'm just going to say return index of IJ. That's how we reconstruct an item name for the structure V. We know it's substructure it's in and we know its name within the the substructure within the cluster. Is this algorithm clearly correct? Good. It's also really bad. Well, it's better than everything we've done so far. Last Last result we had was square root of U. This is going to be better than that, but uh still not log log U. Why? Both of these are bad. Yeah. Right, I make more than one recursive call to whatever the operation is. Here insert calls insert twice. Here successor calls successor potentially three times.
All right, this is a good challenge for me. See. Uh off by one. Off by one. Okay. That's a common problem in computer science, right? Always off by one errors. Um Okay, so let's think of it in terms of recurrences in case that's not clear. Here we have T of U is 2 * T of square root of U. Right, to solve a problem of size U, I solve two problems of size square root of U uh plus constant because high of X and low of X I'm assuming take constant time to do. It's just I have an integer, I divide it in half. Those are cheap. Uh what does this solve to? It's probably easier to think of it in terms of log U, then we could apply the master method.
Right, this is the same thing as T prime of log U is 2 * T of log U / 2 plus order one. Uh this is not quite the merge sort recurrence, but um it's not good. We start One way to think of it is we start with a total weight of log U. We split into uh log U over 2, but two copies of it, so we're not saving anything and we didn't reduce the problem strictly. In terms of the recursion tree, we have, you know, log U. Well, it's hard to think about cuz we have constant size here. But um our constant total cost. You could just plug this in with the master method or see that essentially we're conserving mass.
We started with log U mass. We have two copies of log U over 2. That's the same total mass. So, how many recursions do we do? Uh well, we do do log log U recursions. Total number of leaves in that recursion tree is log U. Each of them we pay constant. So, this is um log U. Not log log U. To get log log U, we need to change this two into a one. Can only afford one recursive call. If we have two recursive calls, we get logarithmic performance. If we have three recursive calls, it's even worse. I have to Here I would definitely use the master method. That's obvious. Um in this case we get uh log U to the log base 2 of 3 power.
Which is log U to the 1.6 or so. So, both worse than log N. Right, this is strictly worse than log N. This is maybe about just a little bit worse than log N depending on how U relates to N. Okay, so we're not there yet, but we're on the right track. We have the right kind of structure. We have a problem of size U. We split it up into square root of U subproblems of size U from a data structures perspective. This is the first time we're using divide and conquer for data structures. It's a little different from algorithms. So, that's how the data structure is being laid out, but now we're worried about the algorithms on those data structures.
Those we can only afford T of U equals 1 * T of square root of U plus order one. Then we get log log U. So, here we have two recursive calls. Somehow we have to have only one. Let's start by fixing insert. Uh insert. No, let's start by fixing successor. I think that will be more intuitive. Okay, let's look at successor cuz successor's almost there. A lot of the time it's just going to make this call and we're happy. The bad case is when we need to make both of these calls. Then with there's three total. Very bad. How could I get rid of this call? I was being all clever that that the minimum element is the successor of negative infinity, but it's actually not the right idea.
Um yeah. Got to change the minimum element in in the cluster I. Store the minimum element of cluster I. Yeah, in general, for every structure V let's store the minimum. Why not? We know how to augment structures. Uh here in 206 you took a AVL tree and you augment every node to store the subtree size of the node. In this case, we're doing a similar kind of augmentation. Just for every structure, keep track of what the minimum is. So, that will be idea number four. I'm going to add something here, but for now let's store the minimums. So, to do an insert uh into structure V item X, first thing we'll do is just say, "Well, if X is uh let's see if it's the new minimum.
Maybe X is smaller than V.min." If that's the case, uh let's just set V.min to X. Okay, and then rest is the same. Same insertion algorithm as over here. These two recursive calls. I just spent constant additional time and now every structure knows its minimum. Again, ignore delete for now. That's trickier. Okay, um now every structure knows its minimum, which means uh we can replace this call with just V.cluster I.min. One down. Okay, so uh if we look at successor of V {comma} X I'm going to replace the last line or next to last line with J equals uh V cluster I {dot} min. So, now we're down to log U performance.
We only have uh at most two recursive calls. So, that's partial progress. But, we need another idea to get rid of the the second one. And the intuition here is that really only one of these calls should matter. Okay, let's let's draw the big picture. Um Here's what the recursive thing looks like. We've got V {dot} summary. Then we've got uh cluster zero cluster one cluster square root of U minus one. Each of those is a recursive structure. Uh and we're also just storing the min over here. Copy. Um So, when I do a query for uh I don't know, the successor of this guy. There's kind of two cases. One situation is that I find the successor somewhere in this interval.
That case, I'm happy because I just need this one recursive call. Okay, the other case is that I don't find what I'm looking for here. Then I have to do a successor up here and then I'm done. Right? Then I can teleport into whatever cluster it is and I've stored the min by now. So, that's constant time to jump into the right spot in the cluster. So, either I find what I'm looking for here or I find what I'm looking for here. What would be really nice is if I could tell ahead of time which one is going to succeed because then if I know this is not going to find anything, I might as well just go up immediately up here and look at the success successor in the summary structure.
If I know I'm going to find something here, I'll just do the successor here and I'm done. If I could just get away with one or the other of these calls, not both. I'd be very happy. How could I tell that? Yeah. Store the max. Store the max. Store the min and the max. Why not? Okay, uh I just need a similar line here. If X is bigger than V {dot} max change the max. So, now I've augmented my data structure to have the min and max at every level. And what's going on here is uh I won't find an answer if I'm greater if I'm greater than or equal to the maximum within this cluster. That's how I tell.
If I'm equal to the max or if I'm beyond the max, if all the items are over here, the max will be to my left and then I know I will fail within the cluster, so I might as well just go up to summary and do it there. Okay, on the other hand, if I'm less than the max, then I'm guaranteed I will find something in this cluster and so I can just search in there. So, all I need to do, I'll probably have to rewrite this slightly. Uh if X is not X close. I'm going to mimic uh this code a little bit. At least the first line is going to be I equals high of X. And now uh that's the cluster I'm starting in and I want to look at the maximum of that cluster.
So, this is going to be uh So, I'm looking at V {dot} cluster I {dot} max and I want to know is X before that. Now, within that cluster, X is known as low of X. So, I look for low of X compare low of X to cluster I's maximum element. If we're strictly to the left, then there is a successor guaranteed within that substructure. And so, I should do this line. I wish I could copy paste, but I will copy by hand. Successor uh within V {dot} cluster I of low of X. Okay, then I've found the item I'm looking for. Else I know that this is if I'm beyond the max, I know this is the wrong cluster and so I should immediately do these two lines.
Well, except I've made the second line use the min. So, it will only be one recursive call followed by a min. Okay, so this is going to be I equals the successor within V {dot} summary of high of X. And then J is that line successor uh within Oh, sorry. The line that I used to have here which is going to be V cluster I {dot} min. Okay, and then in both cases, I return index of I J. Okay, so we're doing essentially the same logic as over here, although I've replaced this step with the min to get rid of that recursive call. But, I'm really only doing one or the other of these using max to distinguish.
If I'm left of the max, I do the successor within cluster high of X. If I'm right of the max, it's J. Uh if I'm right of the max, then I do the successor immediately in the summary structure cuz I know this won't find anything useful. And then I find the min within that uh non-empty structure. And in both cases, I J is the element I'm looking for. I put it back together with index. Clear? What's the running time of successor now? Log log U. Awesome. We finished successor. Sadly, we have not finished insert. Insert still takes log U time. But, progress. Maybe your routing table doesn't change that often, so you can afford to pay some extra time for insert as long as you can route packets really fast.
As long as you can find where something belongs, the successor in log log U time. But, but for kicks, uh let's do insert in log log U as well. This is going to be a little harder. Or I would say more more surprising idea. So, maybe uh I don't have a great intuition for this step. I'm thinking. Um Let Let me But again, most of the time this should be fine, right? Most of the time we insert into cluster high of X, low of X and we're done. Yeah, as long as there's something already in that cluster uh we don't need to update the summary structure. As long as high of X has already been inserted into the summary structure, we can get away with just this first step.
The tricky part is detecting. How would we know? Well, that's that's not enough just to detect it. Um if this if high of X is not in V {dot} summary, we have to do this insert. Can't get away with it. But, that's kind of rare. That only happens the very first time you insert into that cluster. Every subsequent time, it's going to be really cheap. We just have to do this. It's easy enough to keep track of whether a cluster is empty. Um For example, we're storing the min. We can say V {dot} min is none, special value, uh whenever the structure V is empty. But, we still have this problem that the first time we insert into a cluster, it's expensive cuz we have to do this and we have to do this.
How could we avoid uh in the case where uh a cluster is empty. Remember, uh a whole an overall structure looks like this. We can tell that's empty by saying min equals none, let's say. What could I do? Sorry, there's also a max by now. What could I do uh to speed up inserting into an empty cluster? Cuz I'm first going to have to insert into the empty cluster, then I'm going to have to insert into the summary. I can't get away from this. So, I'd like this to become cheap in the special case when this cluster is empty. Yeah. Lazy propagation? Lazy propagation. You want to elaborate? Um, like we we mark the the the place we we want to insert in, and then we will take it down whenever we do any search.
Good. So, when I insert into an empty structure, I'm just going to have like a a little lazy field or something. Uh and I'll put the item in there. And then the next time I insert into it, maybe I'll carry it down a little bit. That actually works. Uh and that was the original van Emde Boas structure, uh I learned recently. So, uh that works, but it's a little more complicated than the solution I have in mind. So, I'm going to go uh I'm going to unify that lazy field with the minimum field. Say, when I insert into a structure, if there's nothing here, I'm just going to put the item there and not recurse.
I just I'm not going to store the minimum item recursively. Definitely frisbee. Um so, that's the last idea. Pretty much. Idea number five is don't store the min recursively. This is effectively equivalent to lazy, but we're actually just never going to get around to moving this guy down. Just leave it there. First if if the min field is blank, store the item there. Yeah. What do you mean by moving the guy down? Don't worry about moving the guy down. We're not going to do it. Uh but in general, moving down means when you I want to insert an item, I have to move it down into the sub cluster. So, I want to insert X into the cluster.
High of X with low of X, that recursive call, that's moving it down. I'm not going to do that. If the structure is empty, I'm going to set V.min equal to X, and then stop. Let me illustrate with some code. Maybe over here. Here's what I mean. If V.min is special none value, I use Python notation here, then I'm just going to set V.min equal to X. I should also set V.max equal to X. So, I want to keep track of the maximum. And then stop, return. That's all I will do for inserting into an empty structure is stick it in the max field. Okay, this may seem like a minor change, but it's going to make this cheap.
So, the rest of the algorithm is going to be pretty similar. Uh there's a couple annoying special cases, uh which is we have to keep the min up to date, and we have to keep the max up to date in general. Uh this one is easy. We just set V.max equal to X. So, we're not doing anything fancy with max. Min is a little special because if we're inserting an item smaller than the current minimum, uh then really X belongs in this slot, and then whatever was in here needs to be recursively inserted. Okay, so I'm going to say swap X with V.min. So, I'm going to put X into the V.min slot, and I'm going to pull out whatever item was in there, and call it X now.
And now my remaining goal is to insert X into the rest of the structure. There's only one item that gets this uh freedom of not being recursively stored, and it's always going to be the minimum one. So, this way the new value X goes there. Whatever used to be there now has to be recursively inserted, cuz every item except the minimum, we're going to recursively insert. So, the rest is pretty much the same, but we're going to uh instead of always inserting into the summary structure, we're going to see whether it's necessary. Because we know how to do that, we just look at cluster high of X, and we see do we is it empty?
Cluster high of X. And empty means uh its minimum is none. So, we're we're we're going to in fact the the next line after this one is going to be insert uh V cluster high of X {comma} low of X. All right, that's this line. We're always going to do that. And in the special case where there was previously nothing in V cluster high of X, we need to update the summary structure, and we do that with this line. So, I'm going to insert into V.summary uh high of X. But I'm only doing that in the case when I need to. If it was already non-empty, I know this is already happened, so I don't need to bother with that insertion.
Okay, this is a weird algorithm because it doesn't look much better. Uh in the worst case, we're doing two recursive calls to insert. But I claim this runs in log log U time. Why? Yeah. Because when we update the V.summary, it just happens after the first Good. Yeah. In the case when I have to do this summary insertion, I know this guy was empty, cluster high of X was empty, so this call is just going to do these two lines. Because I optimized the case of empty. When when a structure is empty, I spend constant time, no recursive calls. That means in the case when cluster high of X is empty, and I have to pay to insert into the summary structure, I know my second call is going to be free, only take constant time.
So, either I do this, in which case this takes constant time, or I don't do this, in case in which case I make one recursive call. In both cases, I really am only making one recursive call. Okay? So, this runs in log log U. Cuz I get the T of U equals 1 * sqrt(T(U)) + order 1 recurrence. All the work I'm doing here is constant time other than the recursive calls. Question? So, when we insert the first time, we don't update V.summary? When I insert into a completely empty structure, we don't update summary at all, that's right. We just store it in the min, and we're done. Um but then uh well, if you were to call like Mhm.
Good. Yeah, the successor algorithm is currently incorrect. Thank you. Some frisbees for that question and the last answer. Um Yeah, this code is now slightly wrong because sometimes I'm storing elements in V.min, and successor is just completely ignoring them. So, it's not going to find those items. Luckily, it's a very simple fix. Uh out of room, but please insert right in here. Uh if X is less than V.min, uh return V.min. That's all we need to do. Uh the min is special because we're not storing it recursively, and so we can't rely on all of our recursive structures, we can't rely on cluster I, we can't rely on summary on reporting about V.min.
V.min is just a special item sitting there, it's not represented nowhere else. So, uh but we can check because it's the minimum element, and we're looking for successors, it's really easy to check for whether it's the item we're looking for uh cuz it's the smallest one. If we're smaller than it, then that's clearly the successor. Okay, so in that case, we just spend constant time. So, it actually speeds up some situations for successor. We're not exploiting that here. Doesn't help much in the worst case, but now it should be correct. Hopefully, you're happy. Any other questions? So, at this point, we have what I would call a van de Bos.
This last version we can do insert and successor in log log U time. With yeah, sorry. I modified the wrong successor algorithm, didn't I? I meant to modify this one. This is the fast one, so please put the same back code here. That's the log log U version of successor. We just added this constant time check. And now this runs in log log U time. The key idea here was if we store the max then we know which of the two recursive calls we need to do. If we store the min we this doesn't end up being a recursive call. So that's very clean. With insert we needed this trickier idea that the min we're not even going to recursively represent.
We'll just keep it there. That requires this extra little check for successor, but it allows us to do insert cheaply in all cases. Cheap meaning only one recursive call. Either we need to update the summary structure in which case that thing was empty and so the we can think of that cluster So we have the special case of inserting into an empty cluster which is super cheap. Or most of the time you imagine that the cluster was already non-empty and so we don't need to update the summary structure and then we just do this recursion. So in all cases everything is cheap. Now the one thing I've been avoiding is delete.
Yeah, question. So if X is greater than V.max I'm just going to update V.max. V.max is stored recursively. We're not doing anything fancy with V.max and we had some point a similar line. So this is just updating V.max. Yeah, nothing special there. In your problem set you'll look at a more symmetric version where you don't recursively store min and max. It works about the same but in some ways the code is actually prettier. So you'll get to do that. Other questions? All right. Um So delete. We have insert and successor and through all these steps it would actually be very hard to do delete. It turns out at this point delete is no problem.
So let me give you some delete code. It's a little bit long. Um maybe I'll start with a high level picture. There's some main cases. Uh Deleting the min is a little bit special as you might imagine. That element is different from every other element. So if X equals min we're going to do something else, but let me specify that later. Let's get to the bulk of the code which is we're going to delete uh delete low of X from cluster high of X. That's the obvious recursion to do. This is essentially the reverse of insert over here. First the first thing we do is undo this. In all cases insert was doing that, so in all cases delete has to do that.
Other than the special case of the min. And then we need to do the inverse of this. So if that was the last item then we need to delete from the summary structure. So it's actually pretty symmetric other than the tiny details. So after we delete we can check is that structure empty? Because then the min would equal none. Okay. If that's the case we delete from the summary structure. Okay. Cool. Um and there's a bit of a special case at the end which is when we deleted the maximum element. Okay, so I need to fill these in. Um and it's important that these are filled in right because in some situations here we make are making two recursive calls.
But again we'd like it to be when we do both calls we want one of them to be cheap. Now this one's hard to make cheap. So when we delete from the summary structure we want this to delete to have taken only constant time, no recursions. Um and that's going to be that's going to correspond to this case because if the if we made the cluster empty that means we deleted the last item. What's the last item? Has to be V.min. Okay, if you have a size one structure it's always because that item is in V.min. Everything else is empty. So that's the case of deleting V.min. So we want this case to take constant time when it's the last item we're deleting.
So let's uh fill that in a little. See if I can fit it in. Uh This is code that turns out to work in this uh if X equals V.min. It's a little bit subtle. Uh but the key thing to check here is we want to know is this the last item? Okay, and one way to do that is to look at the summary structure and say do you have any non-empty clusters? If you don't have any non-empty clusters that means your min is none. That means the only thing keeping the structure non-empty is the minimum element that's stored in V.min. So in that case that's the one situation when V.min becomes none. We didn't have we never set we never set V.min equals none in the other algorithms because we were initially everything is none.
But when we're inserting we never empty a structure. Now we're doing delete. This is the one situation when V.min becomes none from scratch. In that case no recursive calls. So that means this algorithm is efficient because if I had to delete from the summary structure this only had a single item which is this situation then I just set V.min equals to none and I'm done. So this will overall run in log log U time. Uh Now it could be we're deleting the min but it was not the only item. So that's this situation. In that situation we want to find out what the min actually is. Right? We just deleted the min.
We want to put something in V.min. We can't set it to none because that indicates the whole structure is empty. So we have to recursively rip out the new minimum item because it should not be recursively stored anymore and then we're going to stick it into V.min. So uh Now finding minimum items is actually pretty easy. We just looked at the first non-empty structure and we looked at the I think I'm missing No, V.cluster I min I guess close parenthesis. That is the minimum item in the first cluster. So I want to recursively delete it. So I'm setting X to that thing and then I'm going to do all this code which will delete X from that structure.
And then I I mean I'm doing it all right here, but then I'm going to set V.min to be that value. So then V.min has a new value cuz I deleted the old one. And recurse and it's no longer recursively stored. I don't want two copies of X floating around. So that's why I do even in this if case I do all these steps. Cool. Uh you can see delete set min Uh why did I set V.max to none? The Oh, right. I'm not done yet. I haven't specified what to do here. Yeah. Okay. You really want to know? Okay. Let's go somewhere else. Not enough room. Think. Uh maybe I can squeeze it in. It's going to be super compact.
So, um when x equals v.max, there are two cases. So, max is a little different. We just need to keep it up to date. So, it's not that hard. We don't have to do any recursive magic. Wow. I need another line, sorry. Uh let me go up to the other board. Okay, I think that's the complete delete code. You asked for it, you got it. So, uh when we if we just at this point we have just deleted the max, which means we need to find basically the predecessor of x, but we can't afford a recursive call. Uh I mean, it's okay. It's just we're trying to find the max in what remains. We need Imagine v.max is just wrong.
So, we're going to set it from scratch. It's not that hard to do. Uh basically, we want to take the last non-empty structure, that would be v.summary.max, and then find the last item in that cluster. Okay, so cluster i is the last one for v.summary, and then we look at v.cluster of i.max, and we combine it with i, that gives us the name of that item in the last cluster, last non-empty cluster. But, there's a special case, which is maybe this returns none. Maybe there actually is nothing in v.summary. That means we just deleted the last item, I guess. Or, there's only one left. We deleted the next-to-last item.
Now, there's only one item left, namely v.min, so we set v.max equal v.min. So, that's the special case, but most of the time you're just doing couple dot maxes, and you're done. So, that's how you maintain the maxes even when you're deleting. And unless I made an error, I think all of these algorithms work together. You can do insert, delete, and successor, and symmetrically you can do predecessor in log log u time per operation. Super fast. Uh let me tell you a couple of other things. One is uh there's a matching lower bound. Log log, maybe you wonder, can I get log log log time? Or log log log log time?
Or whatever. Uh no. In most reasonable choices of parameters, it's a little bit more complicated than this, but for the most most of the time you care about, log log u is the right answer. Um this is proved in 2007. So, this is the It took us decades to really understand. Um it's by a former MIT student. So, I'll give you some range where it holds. Which will raise another issue, but Okay. Uh so, this range is the range I talked about before. This is when log log u equals log log n. So, that's kind of the case where you care about applying it. If log log u is more like log n, it's not so interesting.
Uh but as long as u is not too big, it's a little bit bigger than polynomial in n, uh then this is the right answer. Now, technically, you need another assumption, which is the space of your data structure is not too superlinear. Now, this is a little awkward because uh the space of this data structure is actually order u, not n. So, the last issue is space. Space is order u. Uh let me go back to this uh binary tree picture. So, we had the idea of well, there's all these bits at the bottom. We were building a big binary tree above those. These are The leaves are the actual data. And then we're summarizing by for every node, we're writing the or of the two nodes below it, which is summarizing whether that thing is non-empty.
Um What van Emde Boas is doing, so first of all, you see that the total number of nodes in this tree is order u, right? Cuz there's u leaves. Total size of a binary tree with u leaves is order u, 2 2u - 1, right? So, uh and you can kind of see what van Emde Boas is doing here. First, it's thinking about the middle level. Now, it's not directly looking at these bits. It says, "Hey look, uh I know my item the the thing I'm doing a successor of, let's say, is three. I want to know the successor of this position. First, I want to check, should I recurse in this block? Or, should I recurse in the summary block?" Which I didn't draw, but it's the part of the tree that would be up here.
And that's exactly what we're doing with insert. Uh we're saying, "Look, uh sorry, with successor, successor, should we recursively look within cluster i? Or should we look within the summary structure?" We only do one or the other. And that's the sense in which we are binary searching on the levels of this tree. Either we will spend all of our work recursively looking for the successor within the summary structure, which is like finding the next one bit in this row, the middle row, or we will spend all of our time doing successor in here. And we can do that because we have the max augmented. Okay?
But, that's the sense in which kind of you are binary searching in the levels of this tree. So, that's the that early intuition for van Emde Boas is kind of what we're doing. The trouble is to store that tree takes order u space. We'd really like to spend order n space, and I only have 4 minutes, so uh you'll see part of the answer to this. My poor microphone. But, let me give you an idea of how to fix space bounds. Let's erase some algorithms. Uh main idea here is only store non-empty clusters. Pretty simple idea. Uh We want to spend space only for the present items, not for the absent ones. So, don't store the absent ones.
Um In particular, we're we're doing all this work around when clusters are empty, which case we can see that just by looking at the min item, uh or when they're non-empty. So, let's just store the non-empty ones. That will get you down to almost order n space, not quite. But, close. Um to do this, v.cluster is no longer an array. Just make it a hash table, a dictionary in Python. Right? So, uh v.cluster, we're always doing v.cluster of i, just make that into a dictionary instead of an array, and you save most of the space. You only have to store the non-empty items. Uh and you should know from 006, hash table is constant expected.
We'll prove that formally in lecture eight, I think, but uh for now, take it hashing as given. So, this is basic everything we did before is essentially the same cost, but in expectation. No longer worst case. Uh but now the space goes way down because if you look at an item, uh when you insert an item, it sort of goes to log log u different places in the worst case, but um yeah. We end up with n log log u space, which is pretty good. Almost linear space. Uh it's a little tricky to see why you get log log u, but if you I guess if you look at the insert algorithm, uh you know, even though we had two recursive calls in the worst case, one of them was free.
When we do both of them, we insert here, this one uh happens to be free cuz it was empty, but we still pay for it. We set v.min equal to x, and so that structure went from empty to non-empty. So, this costs one, and then we recursively call insert v.summary on high of x. So, we might when we insert one item x, if lots of things were empty, actually log log u structures become non-empty, and that's why you pay log log u for each item you insert. It's kind of annoying. There is a fix, which is in my notes, you can read it, uh for reducing this further to order n, but uh okay, I have 30 seconds to explain it.
The idea is uh you're not responsible for knowing it. This is just in case you're curious. Um The idea is instead of going all the way down in the recursion, at the very bottom you say, "Well, normally if you uh you stop the recursion when you have one uh you equals one." Just stop the recursion uh when n equal is very small. Like log log u. When I'm only storing log log u items, put them in a linked list. I don't care. You can do whatever you want on log log u items in log log u time. It's just a tiny tweak, but it turns out it gets rid of that log log u in the space. So, uh it's a little bit messier, and I don't know if you'd want to implement it that way, but you can reduce the linear space, and that's fanem de Boas.