Video 1-10: Skip list updates

0:02 A short section on how to do insertions and deletions for skip lists. This part, I think you may have seen also before. Uh of course, we want to do insertions and deletions. Um if you follow a if you do an insertion, how would you do insertion in a in a linked list? You uh have a pointer here that used to go from three to four. And now you plug your new element in the middle of the pointer, which means the old pointer points to the element and the target of the old pointer becomes the pointer of the new element. Now, in a skip list, you have to do this on all the levels. At least on all the levels that this new element has a a tower slot for. There's a convenient way to do this, um which I've I've seen under the name of keeping uh a hand of pointers, which is just um and any pointers you currently followed uh and any pointers you skipped, excuse me, any pointers where you didn't follow, so you you followed them to check, but this was going too far.

1:11 All these pointers, let me say uh so this is this this one and this one and then the red ones. These were pointers that you checked, but then you didn't go over. These you have to keep in mind. What I mean by that is keep to the element where they come from. So, when you insert this new guy and it turns out that it hides it it hi its height is reaching into this pointer, you know where it comes from, and so you can do this insertion into the linked list by bending a a few pointers around. Okay?

1:56 This is the only point where you actually do random coin flips in the in the data structure. The search there of course is deterministic. Just our analysis was pretending to do the coin flips now. Um Yeah, with with this with the hand you can do it without a stack. You can just recurse and remember the pointers. The other option you could do a recursive descent and on the way back up bend the pointers around. Both works. That's insert. Um What's the cost? Well, the cost is essentially the search path. We uh walk down the green path. We update a few pointers, but the number of red pointers is bounded by the height, which we already know. Uh so the total cost in in expectation is logarithmic.

2:49 Deletion is kind of similar. You do the same in reverse. So you find the element you want to remove. Now it may have had some tower of pointers, which now you need to short circuit. So there's some pointers and you keep those in your hand that uh let into this element. And these you have now to update to whatever the deleted element pointed to.

3:21 And notice it's it's again uh you search for three in the right way. It's the same kind of pointers, the ones that you didn't walk over. I think you would have to modify the the comparison for the picture to be the same.

3:39 Or you you search for X minus epsilon. And then then this works. Then you do one step at the bottom. Yeah, that's that's delete. Um the cost by the same argument is also bounded by the search path. So, it's also logarithmic.

4:03 Uh, something I'll I'll not do in in any detail, but I wanted to mention that it's possible are the rank-based operations. That's what we do with subtree sizes in binary search trees. Uh, there's no subtrees here, so we can't really do that. And if you were to try to keep, say, the global rank of any element in the list, that's not going to be maintainable. What you can maintain is the length of the pointers. So, each of the towers has a pointer and uh, the number of elements this pointer skips over. And this you can maintain. Here's a picture. Um, if you want to see the details, there's this Let me give a shout-out here to the to this lovely book. It's from Pat Morin, a researcher in in Canada who put out uh, an open textbook. It was under a Creative Commons license. So, you can you can mess with it and modify the pictures and all these things.

4:59 Um, but they they were created by him. Um, if you want to see more details or full code for the rank-based operations, they're in in the book. Uh, so this this picture just shows you as you walk down upon an insertion, you already increment the pointers that you don't take because those are the ones that will see this new element inserted. And then for those where you do the update, you make the uh, increment uh, you reverse the increment again. Because this um, this element is inserted here or you're you're subtracting what is the length of the pointers behind. It's not It's not just a a minus one. It's maybe a a bit unfortunate that these are all length one.

5:49 Okay. Uh, so without more details, you can do rank-based operations. Uh if this is easier than in a binary search tree, I'll leave to your judgment.

6:01 That brings me to the end of skip lists. They're very simple in the way they use randomness. All they rely on is is single bits. That's the main uh the main benefit, which also makes the analysis particularly clean and easy. Um ironically, still possible to mess it up. Uh and the range queries are particularly fast because you just follow pointers that give you give you things in sorted order. Uh what is still left on the wish list, or they've messed messed things up in a way compared to treaps again, if you want to keep this, but not have the downsides of skip lists, then you have to come back next week. So, the uh one downside is that these towers I always found inelegant and somewhat somewhat troublesome to have these variable-size objects. Remember also, you have to allocate those in memory, and uh memory allocation usually rounds the sizes you can allocate to some to something, maybe a power of two.

7:05 So, you you're this is this is using a bit more memory than than would be needed. You can't easily compact it and so on. And if you care about this, the constant factor in the search cost is also substantially worse. It's uh two instead of 1.4, so maybe if searches are are important, this is a thing.