Video 2-21: Lazy Search Trees Operations

0:03 With that setup, we can look at how the operations actually work. I've already sketched what they are supposed to do, but I left out the maintenance of these intervals a bit. Um that's what we're what we're going to do next. Insert actually doesn't do any maintenance, so what I told you before still applies. We find the correct gap using the biased search tree, then we find the correct interval within that gap. We insert the element there. And we increment the weight of this gap, which again in a splay tree doesn't really do anything, but conceptually in a biased search tree you have to have this operation. And there is an amortized cost for it. Uh we'll analyze the cost um soon. Uh let me first talk about query, how that works, and then we'll do the analysis together. Uh query became a bit more complicated. The first part is is still um as before. We first find the gap that we need to split.

1:02 Then to be cautious, let's first apply rule M so that we can rely on our invariant and on the sizes of the intervals being sane. Uh then we find within that gap the interval that we need to split. And then we split this interval precisely five times where this is drawn here. This a certain query rank that we get from the outside, we have to split the interval there, and in indeed the entire gap will be split there. But then on the left and right side of this original interval, I'll do two more partitioning rounds. One around the median and one around the median of the half towards the boundary. Okay? So I'll I'll establish a little bit of this exponential growing pattern, but only for two steps. It turns out that's enough so that over several queries you'll not pay too much for any of them in an amortized sense.

2:07 That's what we do for the intervals. Now a bit of bookkeeping is that we have to split the gap and take the intervals. So that's a split of a binary search tree. Um and updating the biased search tree with the new gaps. And then at the end we have to invoke this rule M again on the two new deltas. Because this is the Maybe this invocation never really does much. It's just making the analysis easier. But this one is the crucial one because I I don't know how big these deltas are and they might have had a lot of intervals before and now they can't afford them anymore. So they have to clean up.

2:53 At this point um I've always just pretended that we do selection queries like in multiple selection. And let me throw in here that you can you can essentially do all the typical queries that the binary search tree wants to do and associate a certain rank with it so that it behaves as if it was a rank query. The analysis is the same as if it was a rank query. Uh of course you can That's the original one. You can do an actual selection query. But you can also find the rank of a given value that um essentially searches for that value but then in hindsight it behaves the same for what the data structure does as if it had been a rank query for the rank that you returned. So you don't know before you do it how the result will come out. But what you can do here is this this splitting five times What it really means in this case is you scan through the interval and you find the element uh if this X is present you find it and then you partition around that one.

4:00 And then in hindsight you know what the query read rank would have been if it was a selection query. And the claim is for the analysis of the of lazy search trees these behave the same. It only depends on the rank that you touch. And the same for for these other queries. Uh let me also point out the last ones cuz that's what we'll come back to after this. Um you can do you can ask a query for the smallest and largest. That's of course just a special case of selection.

4:42 We won't get through the full analysis. Uh one option is that we only I only give you the the general flavor of the analysis. And then we we never do the details so we move to overview mode at this point. But maybe that's a bit of a uh unsatisfying experience then. Let's see. I'll I'll introduce the the potential function for the amortized analysis and then we can decide next week as well. That That one we we need anyways. So the the key problem here is that this operation here, this point four this may be expensive. In in actual cost it has to split an interval that could be arbitrarily big. And someone has to pay as always in life. Um the query may not gain enough lower bound to pay for it itself so we'll have to amortize it over many operations. Um let me also mention is essentially just the queries that are amortized.

5:40 All the other operations don't do much maintenance so the queries have to somehow work it out among themselves. Um what works here is the following potential function. There's an annoying term that has to do with the initial start. Um that is the number of elements in zero-sided and one-sided gaps. Great, but you don't know what that means. Um Initially, if you start with an with a tree that was never queried, you have just a single gap. Uh but you still have these these artificial um infinity negative infinity positive infinity ranks to somehow define the gaps. But these aren't actual queries. So, also in terms of the lower bound, if I start after that with rank uh one, that query shouldn't be expected to be cheap just because it's close to the negative infinity's superficial um or kind of uh sentinel rank that we used to define our our deltas. Um this one actually will cost linear linear time.

6:52 That's why um this original gap is zero-sided because its boundaries haven't ever been actually queried. It's just the boundary. There's nothing nothing there. So, zero-sided is the initial state And then of course, when the first query comes, we split this single zero-sided gap into two one-sided gaps, which have a query on one side, but nothing on the other side.

7:43 And then the normal mode of operation starts when you have several other ranks, then this between here becomes a two-sided gap. It turns out you have to work with uh a special treatment for these zero-and-one-sided cases, and you always have these one-sided gaps at the boundaries lying around. They're not going to go away. Uh and somehow they behave a little different. It's That's just life.

8:15 That's where this N01 comes from. It's just the number of elements that still reside in these uh atypical gaps. For all the others or or for all full stop we'll have one contribution for each interval in the whole data structure. And the contribution is is this country is this term. It's a constant for counting the intervals. So you somehow pay a little bit to create more. But the main contribution is this uh excess size over what it over its safety buffer. So if I have within a gap delta I some large interval sitting uh close to the boundary, so this outside here is small, then everything that is in excess Maybe a different color would be good here. Everything in excess to the what what I'm having on the outside Uh let's do this maybe in pink. I don't know. All of these elements they're still part of the same interval, but that's kind of dangerous. I may have to pay for them if a tree becomes here.

9:37 These are in excess of my outside, and so those I have to pay for in terms of potential. They're potential costs future down, whereas um any interval that is far away from the outside, small enough relative to the outside, that's for free. I don't have potential from that one.

10:09 Uh we can do insert um because that's relatively easy. Uh we need to do merge first. Yeah, okay, we need that anyways. Um one one rule uh one one step in query was to apply this rule M, and that's uh that's that's one additional operation. It's kind of an internal one only. Uh but we still have to analyze it. Um so maybe we do that one first. What was rule M doing? Uh I have one delta I, which is split into some intervals, maybe too many for its size. Now, I'm going to go through them left to right, or outside in, rather. Um I'm going to compute for every interval what is its outside. I don't have to maintain that. It's fine to recompute.

11:05 You compute this for all of the intervals, and while you're doing this, you can check if they should be merged. And if so, the merge you just apply. Um Uh this is a constant time operation, because it's just concatenation of two linked lists. Um this is you you can remember the size of each interval. It's a It's a linked list that can just keep account. Well, that's also constant per interval.

11:41 So, so far we've spent essentially time proportional to LI, the number of intervals in here. And we know that this is bounded, right? This is log delta I.

12:14 So, so far we've spent that much time. Um you may worry about the search tree that we built over the intervals. so if you if you do a merge, you you may be tempted to now delete one of the intervals from the search tree. And that could potentially have a log log delta cost each. And you may do many of these, but there's a smarter way to do it. You don't update the tree at all. You just throw it away and rebuild it from the sorted list afterwards. And that is linear time in the number of elements. So, you can rebuild the entire interval data structure.

13:06 And because you have to list the intervals in sorted order, this is again linear in the number of intervals. So, all the actual cost of this operation is order log log I. LI, not log I. Uh but you also may mess up the potential. And that may have a cost.

13:42 So, that's the the total as well. Everything is within within that cost. For an amortized analysis, you also have to look at the the difference in potential. What's the potential before and after? Um I mean, let's uh a few obvious things. This NI is not changing. We're not changing any gaps. Uh all we're changing is certain intervals. And we're also not changing the sizes of the intervals. The the elements don't go away. We just might combine some. Um And a single merge essentially has negative potential cost.

14:38 The negative one comes from losing an interval. And the other contribution, if you um if you look at what we compute here, uh this is where we're in the situation of merging two intervals that are too small to be compared to their outside. So, this O was bigger than the combined size. So, in particular, the contribution from this term for all of the involved intervals, the two before and the one after is all zero by definition. Kind of the uh the merge rule applies exactly in that case that they contribute no potential.

15:26 So even for the new interval I prime the size of this one is smaller than O of this one. So it contributes nothing. Okay?

15:45 So for all of these say I1 and I2 and I prime all have size less than outside. And so the maximum here is the zero.

16:08 That's how uh with this applying the rule we don't have any any extra contribution from the potential. It's actually a it's for free in in terms of the potential change. And we're left with this cost linear in the number of intervals which is bounded by log of the size. Um and this is fine where we use it. This is uh order log delta or order log n if you want to be more generous. And we use this only inside queries and queries are always allowed to take log n time with x log c plus log n. So so far so good. Okay.