Video 1-13: Jumplists updates

0:02 In the next section, we'll talk about how to do insertions and deletions in these jump lists. Uh and in a way that maintains the structure or the the random the distribution over these shapes as if they had been built from this hypothetical model where we choose jump lists uh jump pointers uniformly at random in each step.

0:29 >> [snorts] >> There's also um Let me let me um come back to this later. Uh there's a an equivalent tree model that corresponds to these lists, but it's a bit awkward. Uh Sorry, this this headline is just in the very wrong place. Mm.

0:59 How do I get this to the right place? Uh Okay. Fine, let's let's do the search first. Otherwise, uh it'll it'll get completely messed up in the in the order.

1:15 Like for the skip lists, I can view these jump lists as a tree-like structure. Namely, um the element that the jump pointer points to becomes the root of some tree. And then the the next sublist and the jump sublist become left and right subtrees. There is one weird thing in doing that, which comes from this non-degeneracy condition. Suppose I I build this tree, right? I start with ele- 11 becoming the root, fine. Then maybe the right sublist, okay, there's a single element. It's one of these plain nodes that doesn't get any jump pointers. So, maybe that's fine and it gets some some extra type of node without jump pointers. But then for the left part, I'm supposed to ignore the key in the one, right? This is for the sublist as if it wasn't there. So, I'm going to have a root of the left subtree five because that's where the jump pointer goes to.

2:16 And I can recursively have five points to 10 because that's where the jump pointer goes. And the left child of five should be where the next inner jump pointer goes. But I'm somehow losing this key one. I have no space in the tree to put it. And so, that's why it has to kind of dangle from the root in this case for the tree to make sense. It's just from the slight awkwardness of defining jump lists like we did. And it seems there seems no um no way around having one way or another being a bit awkward in the trees for these. Um by defining these these non-degeneracy conditions, uh I have this this key in the header that I somehow have to put somewhere. And so, each node in this in this binary search tree has a the minimum of its entire subtree attached to it without that element being part of any of the subtrees.

3:20 You can recursively build this this tree from our lists um using this graphical pseudo code, if you like. If I have um a small list, so again, you can you can substitute for W just two, which means in our case, we have a single uh key in the sublist. That was the case that happened with the 12. Then you make this special leaf node that doesn't have any subtrees. Otherwise, our list is longer and the header has a jump pointer. Then the element this jump pointer points to becomes the root in the binary search tree, but I have to take out the key from the next pointer and stick it into this dangling min part. Because again, the the next sublist ignores the key here. It's fine for the jump sublist because that is already part of the root. So, I don't need to include it here further. But for the next sublist, this X1, I wouldn't have any space in the subtree to go to.

4:21 Okay? Now, you can you can never have more than one dangling min. You'll always have exactly this one. Um which comes from I mean, this construction maybe is is most visible. Every element has a single jump pointer. So, it points to something that becomes the root. And it has a single next pointer, and that key there becomes the dangling min. And the rest is is recursive. If it's if it's a bit um tricky to see, maybe go through the example here and see if you can reconstruct this this tree on the left. The reason why I wanted to introduce the trees is that you should have the trees in mind when you design the design the precise search procedure. I've uh explained that already a bit earlier. Um but if you if you code it up, you have to be mindful about this one case of checking the dangling mins, which is very easy to forget.

5:46 Or you're doing it less efficient and checking more than you need while you're descending in the tree. Uh so again, let's um let's again search for the eight or nine.

6:04 Uh we've done that here in in the jump list. Here's the corresponding tree. And there it's even even more intuitive. You treat it as a binary search tree and delay dealing with these green minima as long as you can. So, searching for say for eight, we start at 18. We descend the tree as in a binary search tree.

6:36 And then from the 10, we would go to this this leaf. And that's a nine. So, if you just treated it like a binary search tree, you would declare, "Oh, eight is not part of the tree." Right? I followed the left pointer from the 10. And it's not there, so it's not in the tree. But of course, that's not true because we have these dangling mins. Uh the last lower bound for the element, this this element six here, uh let me circle it like this. That's the the last point where we um where we took a jump pointer from it. So, we clearly know that the six was smaller than eight because we checked at the time when we entered here.

7:29 11 and 10, they're too big. That means from the six onwards, these elements we still have to check. So, the last time we followed the jump pointer was to 11. From there on, we have to check the dangling mins because the element we look for could be one of those. And for the eight, it is one of those. Uh in the code, this looks less cryptic and you can do it on the jump lists. You first only check the jump keys. You always go to the jump element, check the key, and see if you can take the shortcut. Uh but you remember whether you stepped over some elements. Okay, this is only for the rank operations. Forget about that part for now. Um but you remember when you uh when you last jumped.

8:18 That's the last jump to. Um which is set here. And then after you are done with the binary search part, you still have to check the min keys. So, you do the linear search from this last jump to part.

8:46 Now, I wonder if I would have liked the sublist here section heading here. I think this is where the operations should come in. Um you can analyze this this search and show it's it's a little more efficient than where they when you go from the list, you would compare keys a bit more often. Let me leave it with that. Um Again, what you haven't seen so far is how to do insertions and deletions. Uh so, finally, we'll have to come to this. Also, the search so far was again under this assumption that the jump list is chosen uniformly somehow. Uh what's missing is to get a randomized data structure that enforces this randomness actively as opposed to relying on it.

9:45 Uh one one thing that we use and that we could have done in the randomized binary search trees as well. Uh we've analyzed this in the random BST model. If you take uh if you fix any internal node and ask how big is its subtree size, the number of vertices below it. Uh the expected number was was log n or 2 log n. That was the same Remember these ancestor indicators uh that you could use to analyze these. So, if you're aiming for logarithmic up update and deletion or update time, insert and delete, um you can you can afford to do something linear in the subtree size for the expected cost. For example, we could rebuild the entire subtree and it would still work out to be expected log n time.

10:40 Uh in the randomized binary search tree case, remember what we did? We we followed the search path down and asked with a coin flip, "Should I have been the root of this subtree when I do an insertion?" And if yes, then we made a clever way with uh with split and join to make it the subtree with this inserted root. But in terms of this uh this statement here, we could have also just rebalance the entire subtree or redrawn at random its shape.

11:15 And for the jump lists, that's what we uh what we do here to make things a bit easier. So, there's a um a procedure rebalance that takes part of a jump list and draws its jump pointer uh all its jump pointers in that sublist from the uniform distribution. It's a recursive procedure, so if you have, again, a tiny jump list with no jump pointers to draw, there's nothing to do. So, you just leave it as is. If you have a bigger jump list, then this header needs a jump pointer. So, we draw the index for that jump pointer, where it should go to, uniformly at random from the numbers two up to n.

12:06 And uh we recursively rebalance the next and uh jump sublist. And you can do this in a recursive procedure to pass back the target of the jump pointer. So, you don't have to search, walk linearly down this list while you're building it uh while you don't have uh shortcuts, but rather you can recursively rebalance the next jump list, and then when you have reached the jump list, you can return the target for the jump pointer. So, you don't need to explicitly pay for that.

12:39 Uh so, the overall cost of of rebalance is linear in the sublist. So, how does this um overall look like for an insertion? We uh start by searching for the element we're trying to insert. That's, again, is a linear list, right? So, there will be some part here where x should go.

13:14 then um we have some some new element here, so the red part is where the element was inserted. And you again recursively from top down restore the proper distribution over jump pointers. If the list is tiny, then we don't need anything uh to rebalance, there's no jump pointers. Otherwise, there's an element here uh that was uh that is the header of this sublist. And with a certain probability, this element should point to uh this um this new element. Um And in that case, I have to rebuild the entire list. That's going to be expensive, but it only happens very rarely. Then I'm recursively calling rebalance on these parts and resetting the jump list for the header. Otherwise, um if I don't have to do a new jump pointer target for the header, there's these recursive steps depending on where the inserted element was. If the inserted element is the new header of the list, I'm going to steal the jump pointer of the previous header and just point to this guy, and then recursively treat the repair in the next sublist, where this now effectively is like it had been inserted. It doesn't have a jump pointer yet because I stole it from it, but it should get a jump pointer eventually.

14:56 So, I'm going to re- recall uh call the same procedure here recursively, marking that the first element has been inserted. Uh importantly here, this the next jump list that uh the jump jump jump sublist, sorry, I don't have to touch. This is unchanged. And you can work out that with the conditional probabilities, you're only re- drawing some jump pointers, but the overall distribution of jump pointers is as if they were all chosen uniformly. And the other cases are if the newly inserted element is either in the next or in the jump sublist, and in that case, you just recurse there uh and you leave the jump pointer of the header intact because with the appropriate probability, you've already redrawn it.

15:44 And so here again, you only need to recurse on one side, so these are pretty cheap. Uh you can do the same after deletions. It's roughly the same case distinction. Uh and the procedure is is similar um now you have the the case that uh the deleted element is the target of some jump pointer, then you have to redraw in each case, uh but you can again um bend it bend it around. So, it's a similar case distinction. Um I'll I'll leave it with that. If you want to see the details, you can um you can check it in the paper. There's another picture of this sort. So, with that, you can overall get it to always have this distribution as if it was drawn from um uniform jump pointers from the get-go. And the expected insertion or deletion time is logarithmic. It's slower than the random binary search trees sometimes because occasionally you have to rebalance the entire list. That's that's an expensive operation.