Video 1-9: Skip lists

0:02 In the next section, we'll look at skip lists. Um one classic data structure that uses randomness to be a bit simpler than maybe some of the solutions you would deterministically get. It's not a tree, so I was initially unsure whether I want to put it in this chapter, but then I decided there's a good reason um that you can group it together with the others. Uh and so here it is. Uh maybe we don't even want a tree for the following reason, and that's I think why often this is taught in the context of databases.

0:39 It's a typical application if you use a sorted dictionary as an index that you want sequential scans over some range. Uh we will call this a range query, so you have some upper and lower bound for a single key. So, this is 1D. Forget about the range trees from before for the moment where you had this in two dimensions. Uh the base case either way is in in one dimension. So, you're just looking at some slab of the key space, and you'd like to see all the keys in this range, or iterate over them in sorted order. That's the usual way you want to do it. Um standard binary search trees can do that even um in a in a clever way efficiently. Uh but in terms of the constant factors that come out of that in practice, you can do better. Let me remind you how you would do this in a binary search tree if you have this um this left and right boundary here.

1:39 Uh small and large is left and right, so this would be the lower bound and this the upper bound. You do a a binary search for the two. Mm see if I can Uh let's use this this yellow green for this one, so you have this search path, and then you find your well, whatever the key is closest to your lower bound. In this case, let's pretend it's exactly that key. And then we have the darker green with the other one which goes this way. Now, uh one option would be that you essentially do an in-order traversal or you you simulate an in-order traversal that would start from where you left off with your first search. And so, you would pop from the stack, go back to the next vertex to visit and go into this subtree and visit all these vertices until you reach the target of the second binary search and then you stop.

2:43 Uh this works, um but either way you do it, either you have to keep a stack so that you can move back up or you have to keep parent pointers in the binary search trees, which again, both is is possible, but it has a little bit of overhead. Uh also for um for the first version with the stack, um in amortized over returning several keys, the time to go from one to the next will be constant, but you could sometimes have to pop uh a large amount of nodes from the stack that you don't even output. Like these two guys, you had to go via them to reach this lower bound, but they're not part of the query result. They're outside of the range.

3:34 So, that's possible, but uh maybe we can do better. That's where this will lead to. Now, one nitpick here is if you want to uh return the result instead of iterating over it, you can do this with still the same log n cost uh uh, using the trick that yeah, maybe there could be a linear number of vertices or of keys in this range. Could be the entire tree after all. Uh, but you always can cover the range with logarithmically many many nodes, namely those that are on the search path themselves, like in this case these, and their children, which, if they hang inward, you know the entire subtree is in the range.

4:20 Right? Uh, because you've you've come to the right ones, so you know all of this down here is is larger than 35, which is already in the range. Is already less than 42, which is already in the range. So, this entire subtree you don't need to check. You can just return it. That's why these are these red fat nodes are the ones that you would return. And these uh, non-fat red nodes are the ones that you would implicitly return. That's a nitpick, but if the tree is big and you need to pass these around a lot, this is a big difference. And guarantees that in independent of how big the output really is, you can return something in log n time that encapsulates uh, the output. Of course, if you want to iterate over the range, then you have to pay the time to iterate.

5:19 Uh, yeah, I guess I guess one one classic type of operation that you can do in faster time is any aggregate query. Maybe you don't want to iterate over the keys, but you want to sum up all the values, or you just want to sum up the value of a different column, but for all keys in the range so-and-so in the index. All these are all classic database queries. And this this aggregation you can also do you can precompute this in the subtrees. Can maintain it upon rotations, blah blah blah blah blah. Uh and then again, you can use log in time by picking this guy's aggregate from its entire subtree instead of recomputing it.

6:00 All of this um works with any kind of binary search tree. You could have well used any of our randomized friends. Uh what could we do better? The main point is that if you want to iterate over these in sorted order, which is still uh very common use case, this is not super fast because you have to invoke this uh tree traversal.

6:25 On the other hand, there are sorted lists, which do this very fast. And then that's maybe a reason why many database operations uh in the end boil down to sorted uh processing of sorted lists. Uh that just in um improves the constants by a lot. That's my motivation for why we want a sorted list in some uh in some form or another. But of course, uh a simple sorted list has the problem that you can't insert. So, a skip list tries to fix that. First of all, it is a sorted list at the bottom. That's this part. It's even a singly linked list only. This you can do either way, but uh it turns out that it's just forward pointers or next pointers are sufficient. Uh for technical reason or for to be more convenient, we have one sentinel value and initially it doesn't hold a key, but has pointers to the start. Uh some standard uh linked list would do that maybe as well.

7:28 Then here, the keys are in in sorted order. The good thing about uh a linked list is you can at any point in time insert a new element cheaply into some uh spot if you know where to insert. So, normally in a linked list, if you don't have all this uh uh pointer structures on top, then you can only linearly search through the list, and there goes your fast insert. The idea of skip lists is to have shortcuts that makes make it faster for you to find where you have to insert. And then the insertion itself is essentially dealing with linked lists, and that's first-year problems.

8:26 That's uh supposed to be cheap. Okay. Now, what about these structures? What are they, and how do we build them? Conceptually, um there's there's two ways to think of this picture. Uh for an implementation, probably more convenient is to say this is one node, this whole thing. It has one key, and it has an array of pointers of next pointers. That was a maybe a bad example. Let's pick this guy. Uh this has a key, too, and has four next pointers on these different levels. You could also say I'm looking at this horizontally.

9:10 Then I have one linked list. And that these that these nodes are identical objects across the different levels, that's not really important. Uh you can still view logically that this is one linked list that is comprised of these four nodes. So, conceptually, we have these linked lists where each is if you climb one level higher, you may lose some of the nodes, but you cannot gain. It's always a subsequence of the ones that are below.

9:47 And at some point it stops because the next list would be empty. The sentinel is a special one. We always make that as tall as the tallest in the rest of the list. So that you can always reach things and there's always a start of the of the linked list. Even if there's just a single single node that reaches that height somewhere far away in the tree in the list. And that's pretty much it. Um I'll I'll come to the the search algorithm in a second. Skip lists are intricately linked with a randomized algorithm to construct them. Even though you could see the structure also in a different way. Maybe I'll comment on that later. The the standard procedure is that whenever you insert a new element, you um uh flip a coin whether you promote it to the next level above. And so with with probability 1/2, you produce a copy in the level above. With probability 1/2, you do not.

10:55 Okay. How do you search in such in such a thing? Maybe it's intuitive enough because you follow the shortcuts whenever you can. Um but to be specific, we always start in the top left corner, which means in the sentinel key in the highest level. The intuition is that is the furthest we can jump. So we should always take the far jump if possible. That makes us advance quickly through the list. But in this case, if we search for this value three, um then the first jump is too far.

11:37 So, uh here the key of this next on the highest level was four, and that's bigger than uh our three. So, this is not true. We do instead this. We move uh a level down. Uh down is minus. Um if we at some point reach a node in the next level that is smaller, then we go there. So, then we either make a step to the right or we make a step downwards.

12:09 Uh the way it's written here it would mean that for the three we would keep we would climb the levels down, and only then we would notice suddenly, "Ah, I found the three already." Uh for the it's probably not not ever going to make a big difference uh whether you check for equality here or not. Uh let's let's leave it as it is in the picture. You always climb down to the lowest level. Uh in a way for for insertions, you probably have to do it anyways. So, I think this is intuitive. Also, the range queries are very intuitive. You find the lower bound with the same procedure, and then you just walk along the linked list and produce uh the output. Yep.

13:08 Yeah, uh that's true. L4 and L5 here are kind of uh Well, pick pick whichever whichever you want. One of the two is kind of useless. The thing is this is generated by a random procedure, and randomness isn't very clever. It may well produce these kind of uh inefficiencies. Uh that's why the example includes them. Your code has to deal with them because they might eventually happen. Uh clearly, you could try to avoid this by somehow special casing uh if the previous tower also has this height and then should you stop one early, but the the point is that this is this is um it's very easy to mess up in the sense that you you give a skew to the distribution that overall hurts more than it helps.

13:59 But yeah, uh if you look at it from from our perspective, it's obvious that it's wasteful. Um that's the search. Anything else? Um on that part? Uh before we come to updates, let's have a a think about how well this does. For one simple observation is that any such search path for a key is going to consist of steps that go down and steps that go to the right. It never backtracks and it can never do more down steps than there is layers and it can never do more right steps than there is lists. But especially the second part could be a lot. And also the height mm it's even from the construction here, this is very dangerous. It could be infinite, right? There's nothing that stops this uh coin from always coming up one. And so I'll I'll always add more things. That that sounds very scary. So, we should pair this cute idea with an analysis of whether it's really useful or we only create a memory hog here.

15:20 So, let's do a bit of an analysis and luckily this is why skip lists are taught widely. The analysis is very clean and kind of cute and teaches a bit of basic probability, but doesn't get too onerous to do.

15:34 Um it's basically using properties of the geometric distribution. That's the number of coin flips until you see for the first time heads. Or uh I think here I've always Yeah, called it one and one and zero.

15:55 We'll use it only for the case where the coin is fair, but the the distribution has in general this parameter of the success probability, and then the 1 - p is the the unsuccessful trials. So, then clearly the probability that you need k flips before you see the first success is that you failed k minus one times and then it worked. And I I guess here I should say k starts at one. Depending on where you read up about geometric distributions, it may have you may either count the total number of flips including the last successful one or you count the failures until the first success. So, you have this off-by-one. Be mindful of that. I'm using it to count the total number of coin flips. And then the expected number of coin flips is just one over this probability, which in our in the case that we'll use is just two, right?

17:01 Um something that you'll touch on more in the tutorials, but let me at this point just mention the simple fact. What's the probability that uh t is um at least K. That's also easy to compute. Well, it's the probability that the first K trials all came out as failure. It doesn't matter what happened afterwards. I've used my K trials and that's it. And I guess it did I should have left it. This is more convenient. Then it's just 2 to the minus K. Or yeah. General 1 minus P.

17:49 And uh if I if I have K failures, I'll need at least K plus one in total no matter what happens next. So, the strictly greater is is gives the cuter formula. Uh why did I give you this? Uh especially in our case with the 2 to the minus K.

18:08 What does that tell us about our uh skip list? At least for a single tower, when I insert one element and I keep flipping coins until eventually I get my success and can stop. I might even I might reach a tall height. But it's actually very unlikely. It's exponentially decreasing the probability that I keep going. And the probability that my my single tower reaches height K is exponentially smaller. It is was exponentially going down with K. I'm repeating myself. But this is good, right? Because that's very very sharply concentrated. This is even more than our with high probability uh bounds uh required.

18:55 Now, we'll only use the expected value for the moment. Uh the first simple fact about the skip list is the total number of pointers that you store is is two per element. Um this is the towers. I think you add another N for the base layer because that is unconditional.

19:17 Um Hold on. The No, we count we count the coin flips until success. So, this is already counting the base layer. Sorry, I'll take it back. Uh we do um we always do the success and that counts for the base layer. And all the failures of the coins are Yes, I have to add another element on my tower. So, this is this is total. That's also good because that's essentially what binary search trees would need if you do a left and right pointer. So, even though it looks like we might be very wasteful with this with this structure of potentially having gazillions of of pointers in a single element, we'll on average have just as many as two per each per element.

20:00 That's of course just the expected value, but still. Uh and the next property that we'll need repeatedly is the height of the skip list. That is just a small The highest level that exists is this So, here would be five. Um So, I guess it's technically H H + 1 lists because we start at zero.

20:29 So, it's it's the I didn't define what height is. Uh that's convenient then. Let's define it as the highest level. Uh largest is bad because it's smallest in another sense, right? Let's say highest. Uh let me get right.

21:00 Just to be precise, um we have H + 1 levels then in total. Uh the height that we get the expected height, depends on the number of elements. Even though for a single tower, we we could compute the expectation separately, now the height is the maximum of all these heights. And so that's a bit more tricky to compute. But you can work it out to be uh log n plus two with the following trick.

21:33 First of all, this is just rewritten in terms of the random variables. There's no expectation so far. The height is precisely the sum of all these indicator variables where where I'm summing over a certain list being non-empty. I'm I'm here pretending that the lists keep going as the name, but then they don't exist in the data structure when they're empty. An empty means without the sentinel. The sentinel is always there. We just look at the actual elements that have towers. Uh so that that is um that is true even um exactly. And the indicator that a list is empty, and that's the crucial trick here. That's a very clever idea to upper bound very crudely this 0 1 random variable with the length of the list, which is uh far down a very bad upper bound, right? Uh this is just one, and down there it's essentially a half of the list. Uh note that I'm starting at one here, so we're not we're not counting the zeroth level, which is deterministically always full.

22:43 That's always all n elements. Uh we start at the level above. With that trick, you turn something that's tricky to analyze into something that's rather easy to analyze because these lengths of the lists uh they just come from I mean, what what's uh Uh, what's L K in terms of the list below? The expected I could even Yeah, that's not the expected length of this list is half the expected length half the length of the list below.

23:27 Because I'm generating generating it that way. Uh, all the elements that have reached the level below have 50% chance of being promoted. Uh, and so the the expected lengths of the lists just decay by a factor one each. So, you can write the expected height. Uh, this needs to be an upper bound though. Um, with this sum where now the expected length of the Kth level is N divided two to the K because I've lost K times a factor two in expectation.

24:01 And that sum we can compute by uh, splitting it up. You sum up the first K levels at the first log in levels where this is uh, is dominated by uh, this is is at most uh, is is What is it? Uh, not dominated by the two to the K, so it's not not going down very very quickly. Uh, and this one is the tail where the denominator kills N. Uh, this is always going to be less than But, uh, actually much much smaller.

25:07 >> Why is this smaller than than one? Uh Some something's not right here, right? This can't work. Um Uh the one in the other sum?

26:20 But the sum that goes to infinity is uh is not a good one to bound by one. Because that would give an upper bound of infinite, right?

26:54 I think I was a bit too eager with this with this upper bound. Um Yeah, we should have used it on the second sum only.

27:09 I get the one here by just not doing that. Um the LK is empty stays for the first part of the sum. Um so I my chain of equations is a bit messed up here. I would want to keep these indicators.

27:30 Let's give them a name so I can smuggle it in here. And clearly an indicator is at most one, so that that gives this first sum. For the second part, I use this this less or equal. Um And how do I kill the N there?

27:58 Right. Um that's fine. The second part is actually correct. Um what I missed is the summation in the is the start of the summation. All right, so the the only actual mistake on the slide was this part. The one is not an upper bound for N over 2 to the K for small K. But the indicator was never uh I should have never replaced, then that's fine. And here um if you look at where we start with K, we start with K at a value that's always making 2 to the K bigger than N.

28:33 So uh I can shift the summation so that I'm starting at zero. So the smallest value I get here is less than one. So the smallest value I get here is one. So term by term, this sum is larger than this sum. And I do this for infinitely many terms, okay? But uh um that still works out. Uh then this part just gives me the log n rounded down, but I've ignored that upper bound. And this is the geometric series, which gives the plus two. Okay?

29:14 So again, um I I insist that the trick was to upper bound the indicators by the length. Uh but I messed up the trick by doing it too eagerly. You don't want to do it for the first few. You want to do it for the tail only. This is In a way, this is a good mistake to make because it shows clearly what is actually happening in skip list intuitively. Namely, up to a certain height, log n ish it's very likely that some elements survive. And a little bit above, it's very unlikely that any survive. It's a relatively sharp threshold where uh the probability of having some elements left goes from most of the time yes to essentially never.

29:59 And that's that's uh nicely showing up in the analysis as well. Pros and cons of preparing the proofs typed, I guess. Okay. Um that's cute. Now we know how tall the towers ever get. What we really wanted was the search cost, right?

30:25 Because you could still walk a long way to the right. The The heights was actually from the picture looking fine. Um the the the question is, do you have to walk far to the right? Now it turns out the answer is is a is no. Um we know now that we'll eventually walk log n steps down. So, what this formula tells you is you walk the same number of steps right. That's curious. How does that come about? That's the expected expected length of the search path for some some node U. Um and the the argument is is a clever reversal of the search procedure that makes it um makes it easier to see what happens. So, imagine you're you're sitting down, you have found your node U down here. Now, you know there's the sentinel where you at some point started here at the top and you followed some search path down to U. Now, the good thing about skiplists and the fact that they're randomized is that we can for an expected value pretend that we're we're drawing the coin flips now when you when we do this this analysis as opposed to in the real case, once you once you do the search, everything has already been decided. It's after the fact that the coin flips are done and the structure is as it as it is.

31:57 Uh but for the analysis, we can work backwards in time and consider what what could have happened back then and with what probability. So, I'm sitting at my node U and in each each step, I could have come from the top or I could have come from the left. That's the only two options. And they essentially get decided by I'm sitting currently at some tower. Is that tower one taller or not? Because um Okay, this is this is something uh we should I should mention. Whenever you go up, there has to be a tower that ends here. So, So How do I draw that there is nothing? This doesn't exist or ah better better let's draw cross it out in red. But not dotted.

32:51 Whenever you walk left or when you walked right into this thing there can there cannot have been a higher tower pointer at this point. Otherwise you would have entered there above. So in the search you always enter a tower at the highest possible point. And so in reverse you'll always go up if you can if the coin flip is one. And only if not you need to take a step to the left. So I think I have this on the next slide but let's maybe here. At this point you can go up with probability 1/2 otherwise left.

33:41 And this gives you exactly what the search would have done in reverse. But now the the cute thing about it is that we've we can pretend we haven't already generated the list. We generated it we generate it now with the right probabilities.

33:59 The way to use that is um how often do we need to go in the two directions? Um we already know the height so that's the easy part. The tricky one is how often do we go left? And the coin tosses tell us in expectation is only one step up before you go left again.

34:25 Right? Um okay if that's correct what we want to use is the symmetric version. Um it's in expectation one step left before we go up again. Uh uh that's because the coin is fair. It Uh both both statements are true. Uh that's the one um I want to use. I'm doing my coin flips, and when it comes out as a failure, I treat that as a success to move to the left.

34:54 Um Now we analyze the total length of the path as how many steps have I done on level K. Uh the total length of the search path will then be the sum of all these plus the height at most. Uh probably exactly because we always go down in the in my search procedure. So, we can even make that and keep keep it as an equal.

35:41 And we already know uh what the expected value of H is. So, what's left is to analyze the SK. And from this we've seen we only do in expectation one step on the level before we leave it. So, that's that's the steps you do.

36:01 Um Note that we only get this in expectation, but we sum up the overall things uh by linearity, that's good enough. All right. Um It's only an upper bound. This is For the coin flips, this is precise, right? The expected number of failures before a success is exactly one in expectation. We only get an upper bound here because we might run out of nodes on the level before the coin flips tell us to go. And uh that gives another upper bound. We also have that I can only go as many steps to the left on a certain level as that level has nodes. And the expect the expectation of that size we know from before. That was the we lose half of the elements in expectation whenever we go up. And then we can puzzle things together. Total length is the height plus uh how long we walk on the lowest level and how long we walk on all the other levels.

36:59 I'm just highlighting this here so that we don't forget. It behaves the same as the others. The coin flips to leave the lowest level are the same. Uh so here uh in expectation you get by linearity this. We split up the sum again and this should look eerily familiar now. Um here we use the upper bound of one. Right? And here we use the upper bound from there. Here I did it correctly. Uh and this sums to the same quantities as before because it's essentially the same sums. This starts at zero not at one so we get another plus one. That's all. Uh and so in total it's the two times log n plus five. Uh could have specified the constant here if you want. As an upper bound. So is that good? Uh it's kind of good, right? Um it's uh it's a bit worse than the search in a random binary search tree because that's it looks similar but remember it's slightly different. It's ln not lg so log base e not log base two.

38:14 So this is a bit worse. This was 1.39 lg n for random binary search trees the depth of a random of a leaf. Uh and here the steps we do we do a bit more. On the other hand, if I use many of these range queries, maybe it's worth it.