Video 1-6: Updates in Treaps

0:02 So in the next section we'll look at how to maintain this property or how to build trips one step at a time. That's crucial otherwise they're not a data structure. They're just some mathematical structure.

0:16 So far it was a static view. Um suppose I have a tree for a number of keys. Now along comes a next key k + one. And these need not be sorted right? KN plus one could be at any position in between. This is adversarially chosen potentially. We don't know. So uh and going back for a deletion. How can we do this? Number one uh it's a new pair. So we draw a new random priority for this k N + one. And then from the search tree property we know where it should be inserted in terms of uh the x direction and we could start there going down the tree inserted in the place of some leaf and then fix things up and I think there it's worth doing small example I have to do some some real priorities anyway so and suppose we insert a new key namely uh the Seven.

2:27 So the first step is we find where seven should go. Start at 10. Needs to go here. and we draw a new random priority for the seven. So a new number between 0 and one and say it comes out as 0.15. Now this is fine x direction wise it's not fine heap direction wise. So we have to fix the tree. How do we fix the tree? Well seven looks at its parent and its parent is unhappy because the priority of the parent is higher. So we have to somehow fix that and the unique operation in binary search trees that's suitable for that is a rotation. So here this doesn't work. So we do a rotation in this direction.

3:50 What's going on? Can't see the tree for forest. Can't see the forest, but the trees. I think it's not properly updating, right? This is uh Is this tree really there? Ah, okay. It looks like manual work.

4:13 That's also wrong. What a mess. Now, I want to fix this sub tree. The left rotation, which I got rid of somehow, makes seven the root of this tiny sub tree and five the left child. Now these two are happy.

4:58 But now the parent here and these still have a violation. So, I do another rotation of these two guys and then we're we'll be done.

6:00 That's what it should look like. And let's add the priorities back in. And now uh the parent has a smaller priority than the new in newly inserted node. So now uh everyone is happy. Um, and if I had drawn it in a proper way, it would also still show that it's left to right consistent. But this is really just the the drawing. If we move this a bit to make uh the tree look a bit better, then uh you see also left to right, the binary search tree property is still fulfilled and the heat property is reestablished. That's how you can deal with insertions. Uh deletions are similar. You find a node that you want to delete. Then you update its priority.

6:56 In our case, uh with positive uh the way I I draw things was u larger priority moves down. So you simulate as if it was inserted and you do the same procedure I've shown you, but you move down towards through the tree. In each case, you know on which side to go because you're either bigger or or larger than the child. So you can rotate down uh until you're a leaf and then you can just remove this leaf. Conceptually it's very simple. Also the operations are in logarithmic time with high probability because we over the whole course of the lifespan of this data structure we maintain that its shape is like a random random binary search tree for which this uh hole holds for the depth of the leaves and an insertion path and the rotation fix up is all bounded by the length of a search path.

8:09 >> Yeah. Um question was what if we have ties for the priorities. Uh the one answer would be this is a randomized data structure and if I pick them truly independent and and uniform this happens with probability zero. So you never see it happen. You could of course have some type breaking rule. What what essentially happens is that this this breaks you don't have a unique tree anymore. But the data structure actually doesn't care all that much. Um if you just say you break ties in that sense some somehow that say you stop rotating uh when upon an insertion you reached something that's uh equal to the parent probably nothing goes wrong just because it's very unlikely to happen.

9:02 there are variants of troops that try to exploit this fact even um maybe just uh so this is one of my cases where I'd say this I'm just mentioning this in passing so you don't need to know uh but there's a a nice paper called zip trees this is a bit like uh trips where ties or the prob Capabilities are allowed for for priorities.

9:49 He's co-authored by by Bob Targen, Robert Tarin, one of the most prolific datab data data structures researchers, Turing award winner and and these things. The first version of these zip trees is slightly worse than random binary search trees um because of this tice issue and because of an asymmetry they introduced but you can there's a follow-up paper that improves it a bit. So this idea in principle can can work.

10:23 Um let me also comment a bit before we move on. Um what we what we've shown so far is uh with this kind of uh blackbox cut all argument if I can never go further down than the depth of a leaf and I have one rotation going up in the worst case that's going to be the most the number rotations I will do uh again with high probability not deterministically but good enough.

11:11 Sometimes this is inconvenient. Um I'll show you an example where this is inconvenient. But trees actually do a lot better in the expected sense than this um crude upper bound suggests. But to motivate you why we would even look at this uh let's see an example where this is relevant. Uh this is a little detour that event essentially I I decided not to go in full because it's already uh enough material material for the module. Uh but an interesting data structure problem is range searches in 2D. What I mean by that is you have points in the plane and forget trips for the moment. This is not uh keys and priorities. These are real two-dimensional points. Say this is um maps on a city of on a cities on a map of Germany that way around or it's some database table with two columns uh with numeric values and the type of queries that are called range queries um in in higher dimensions I should probably say uh orthogonal range queries you have an axis orthogonal rectangle which means for each dimension you have an upper and a lower bound. that's what it is. And you're interested in the points that fall in this in this rectangle. So you want to return these three points but not all the others.

12:39 How could you do this? There's various solutions. Um simple solutions are KD trees or quad trees. Uh these are all reasonable and for some types of data they're good enough. If your rectangles can be fairly large um or at least thin and long, these are almost as bad as sequentially scanning all the points without any pre-processing and returning the points that lie in your rectangle. So worst case for these is fairly bad. you can do much better with range trees. Uh so I think here the problem should be named 2D 2D orthogonal orthogonal range search.

13:42 That's that's the algorithmic problem that range trees solve. The idea of a range tree is to use binary search trees for both dimensions to get the overall search time to some power of a logarithm log squared in the simple case here. Uh the way it works is first you build a tree for a binary search tree for the x dimension. So you have the points inserted just looking at the x value in isolation. But then um for every and I'll I'll show the query here in one go. Um let me first explain the data structure. For every node in this X tree, there's another secondary binary search tree that contains again all the points that are in the X range spanned by this node. And spanned by this node means if you come from the root, the 10 is an upper bound, the four is a lower bound. So the tree rooted at six contains all the points with xcoordinates between four and 10. Okay. And these points you insert into another random into another binary search tree. And that's the y tree for this node six. And there would be another one for the 12 uh which I've drawn here as well that stores these three points that fall into the x range of that sub tree. And you have to imagine you do this for all of the points, all of the nodes in the x tree.

15:14 The picture shows you how do you how you answer range queries. You first find the range in the x tree. And maybe you've done this in 1D. You can always get by with um outputting the result as vis take all the nodes that are in the sub trees of a logarithmic number of nodes. That's the highlighted ones here. Uh basically you have to find the search path and then also these um these sub trees that are entirely contained in the x range you would simply say output all nodes here for the points that are in x range in this in this uh in this range in x dimension in this range for the range search you also have to filter by the y-coordinate and for that you use this secondary tree in the secondary tree you find all the points that lie between the min and max in the y direction. Okay, why do I tell you all this?

16:13 Suppose now there's an update to your tree and um you have a new point that's inserted. Now I have to update all my trees in the data structure. In particular, I have to first insert this into the x tree and potentially also into some y trees depending on where where it goes. But crucially, I might want to rebalance the X tree. Say if that was stored as a tree.

17:06 Let me write X tree here because I'm pretending we store these as ts. So I could potentially do rotations, but that messes up all my Y trees because I a rotation changes the X span of a subree and there's really nothing I can do in general. I have to rebuild these Y trees from scratch and that's expensive. It takes time linear in the size of this Y tree. So for a data structure in used as basis for such a range tree and you can do this in higher dimensions you can add there could be a Z tree based on these and you can use 3D points. Uh if you want to use a binary search tree as basis for such a range tree, you really want that rotations high up in the tree are very rare. It's fine to rotate down in the tree where the sub trees are small. Then you may have to rebuild their sub trees, but they're small, so it's cheap, but high up in the tree, you should only very rarely touch these sub trees.

18:08 Okay, so that's what I mean here with uh a rotation has cost linear in the size of the sub tree and so ideally we want that cost to also be small not just the the 1D case and it turns out for trips you can show a relatively strong result um that gets you closer to this. Uh it turns out we need to brush up a little bit our analysis of binary search trees. So there's a little bit more of calculations done and then um we can get that result. Uh it's in terms of a very cute abstraction that makes the calculations relatively clean. So let me uh introduce that as as our building block. Um the star of the show are these these random variables X axy which are uh indicator random variables. So they're either zero or one. And they express this this property that the higher the x the higher node is an ancestor of the lower the y node.

19:21 So if I have something in my tree here's my x here's my y. Yeah. Uhoh. What happened? Uh, Y. And there could be various nodes in between.

19:43 No, not that way. Right. That's not a binary search tree. Oh, no. Would have been possible. It could could maybe look like this. And the tree continues.

20:03 In this case, I would say that axy is one because x is a proper ancestor of y. Right? Relatively easy easy concept I guess. Um this is defined for any um numbers between one and n. I'm pretending here that we rename the vertices in in order. So the leftmost um one two. So from left to right they're numbered one up to n. Uh note I want proper ancestors for technical reasons more convenient. So ax is always going to be zero and otherwise it's one if and only if x lies on the path from the root to y because everything at the end is connected to the root. Okay. Clear?

20:54 Now for for these ancestors we have a few properties that maybe you already had time to read um that characterize precisely when this is the case. And again um we're back to the idea of random binary search trees. We'll connect it to troops in a second again but for now let's assume we have a tree that is built by inserting the elements in random order. No updates.

21:23 And then we say we we get this first result. This this indicator is one if and only if X was the first among a certain set of keys to be inserted. And this weird notation is just to express that among the keys between X and Y, X was the first. And because I don't know in general whether X or Y is smaller, I wrote it in this funny way. But in this union, always one of the two intervals would be empty.

21:53 That's the key property. Um is a little corollery that this is connected to quicksort and then we can based on that compute what is the probability for this event to happen.

22:09 Shall we take a break here? Well, let's do this proof and then the break after. Okay, this one's not not as bad as it may seem. um even though at first it is maybe unclear how you could potentially prove this. So let's say without loss of generality that X is smaller and that there's a symmetric case if it's the other way around. So let's suppose first of all X is somehow insert the root.

22:43 So I have to show both directions, right? And let's do this a bit more properly. I mean part one main thing we're going to prove and uh I want to show if this ax1 is one then x was inserted first among all those keys between x and y in all of this without loss of generality let's assume x is smaller right so there's going to be some path from the root let's draw paths of unknown length a bit quickly just to express the fact that there may be a lot of tree in between. Um maybe be useful to have this statement around.

23:59 Yeah, it's called a not one. There's going to be some path to X and Y is in X's subree somewhere, right? I don't really know where, but there has to be some path from X to Y if uh this indicator is one.

24:37 One of them has to be inserted first. One has to come first. If it's that is not X but anything up to Y. Then in this sub tree somewhere that has all these keys X to Y below it X and Y will be split because it's inserted after zed. So Zed sends X this way and Y that way. So they're never going to end up on the path. Neither one is on the path to the other.

25:21 This is even true if if set is Y is equal to Y, then it might it will still send X down here. So then Y is an ancestor of X, but not the other way around.

25:57 but that's a contradiction to our assumption which means the first key to have been inserted must have been X in this case. Okay. And the other way around it's almost the same.

26:46 Well, then I'll I'll get some some rootx, some path from the root to x, and then all the other keys here will eventually be inserted. And there might be some others from this range, but y will also be always be sent down here. And there's no other key to separate it. So, uh, it'll have to end up somewhere down here.

27:18 That's the if and only if for part A. And part B is is really just a a rewriting of that statement in terms of quicksort. by what I said last time already. Um the analogy between quicksort and binary search trees is that if you run quicksort and you keep track of the recursion recursive calls by generating a node with the the pivot value, then the left child the subree for the left recursive call and a right child for the right recursive call, you get a binary search tree. And that binary search tree if the partitioning is stable it keeps keeps the elements in the same order uh is exactly the binary search tree you get from inserting. So what does what does this mean that X and Y are compared in a uh partitioning step?

28:19 That just means that uh y on the search path passes x because then there was a a common time where x was the pivot and y was part of the input. So it became part of one of the sub trees, the right sub tree in this case because it's bigger and so they were compared and that's that's if and only if. So it's the same as being an ancestor. It's just a cute extra connection because then with part C um you get an alternative way to analyze the expected case of quicksort a third by now another one from the path length already right um we're missing this part C relatively Is he That's what we want to show. And we know from part a exactly when this uh x is inserted first.

30:01 And now because we're in the random binary search tree setting, it's a random permutation. So in a random permutation, each of these many keys here is equally likely to be the first. So how many keys are there? Well, y - x + one.

30:25 So it's one out of y - x + one cases. That is for the case where y is bigger. If you want the general one, you add the the absolute value and you're done. Okay. Um, how do you get the analysis of quicksort out of this?

30:51 Well, the analysis of quicksort. Uh, quicksort has the nice feature that it never does redundant comparisons. uh or most most implementations anyways do that if you've ever compared two elements in your input. You're not going to compare them again. This is essentially following from the partitioning. Once you've compared something with the pivot, it goes to the sub tree. The pivot is excluded from the subree. They're never compared again.

31:32 But that means uh I have between any pair of elements either one comparison or zero comparisons. So the total comparisons are the sum over all I and J.

31:49 And here I guess I can be strictly less and then whether they are compared or let's write it as an indicator. I'm using I and J here as indices in the array. So I'm identifying elements with their original index in the array. Uh but this is by part B the same as our indicators Axy right except that we don't care which one was the top. So uh this is the symmetric part. Either one can be the top but doesn't matter. they're compared if one is on the path uh to the other. So by part C, this was part B. By part C, you insert this. Then you get this lovely double sum that I'm not going to bother to work out for you this time.

32:57 Two for the symmetry between those two and then J minus I + 1. And you can work out this is now exercise in massaging the summations. You can get the same results that uh the recurrence also gives you.

33:22 That's just as an aside. Um again not not not super relevant for the search trees themselves. Um you can refine a tiny bit this uh notion we had before to say that there's for X for Y and Zed.

33:46 X X is a common ancestor. Now I've drawn the picture here a bit misleadingly. It could it need not be the lowest common ancestor. It could look like this. uh both is fine.

33:58 Um this is the combination of X being an ancestor of Y and X being an ancestor of zed. So in terms of the the random the probability the random variables uh but this is they're not independent. So this you cannot use to compute the probability of the event. But the probability of the event comes from um the fact that now x has to be the first to be inserted between everything between y and zed. Suppose there in in this order y is smaller than x smaller than zed. uh then uh this this indicator works for all cases also when x is not between y and zed that I should mention um but this is the the intuitive case I think for for visualizing it uh exactly when x is inserted first among all keys in the entire span then this is a common ancestor that's a slight refinement that's uh useful that the proof is almost the Now uh we can move slightly forward. Um we can analyze the expected depth of the kith internal node. We had the same for the leaves. You can do it with internal nodes. This is uh where I prepare prepared cooking show and prepared it.

35:30 The depth of the kith internal node is the same as well summing up all the indicators whether some node is above k. Okay. That's the same thing. That's why these a ax k axy are so convenient. You can express all sorts of tree parameters in terms of those. And if you only care about expected values and things are linear functions of these, you get the expectation for free. So in in particular here, the expected depth is the sum of the expected values that we know from the formula. uh to get rid of the absolute value you can split the sum into two parts where x is less than k and larger than k and then this you just shift the index to get some harmonic numbers and that is precisely the result is a very simple calculation it takes longer to write down than to do from scratch you can do a similar thing for the expected subtree size so if I take the kith internal node and I want to know how many other internal nodes are below it.

36:38 Guess what we do? We sum up the indicators the other way around. Any a k with some x below it contributes to this sub tree size. So here you go. The sub tree size is precisely this. Ah forgot the k itself. It counts as well. The indicators were proper ancestor. Apart from the plus one oops um is a similar calculation than before and the result also is very similar apart from the plus one it's the same right that's curious if you think about it the uh in expectation for a fixed internal node um it has the same number of nodes on its path to it as its subree below it if you don't count itself as part of Wow. Curious curious fact. Maybe this is some sort of symmetry that one could expect, but I think it's not obvious. It's just a just happens to be that way.

37:47 So, we're very close to finishing the trips part. Um, to get the bounce on rotations, uh, we need what's called the left spine and right spine of the tree. And what this means is the longest chain of just going to the left or just going to the right, where here the next thing is a leaf in each case.

38:18 And here any any kind of sub trees uh doesn't matter. uh you can analyze these expected spine lengths based on our indicators. Um and here the the key observation I wrote down already uh the left spine. So if I have this is left spine of K, which means I have the K internal node. And now I'm interested in these in this uh these red edges that go to the left.

39:06 Uh sorry, my picture here is is is wrong. This is not what we need for the left spine here. Jeeps have a a different left spine. Uh it's the inward thing. So, uh that part that's the left spine. I think the other would be maybe arms or shoulders if anything for the picture. And same here.

39:50 So the the crucial point is that there will be some somewhere here the key k minus one. Then there can only be a leaf and here we could have things in between. And what we want to count is these nodes and also the k minus one. Um you can think about this um if if k minus one is above k then k can only have a leaf as a left child then the spine is empty. Otherwise k minus one must be below k then we can have a non- empty spine. It's the only case. So I want to count all the nodes X that are above K minus one.

40:40 That's this part. Sorry. But I have to somehow make sure that uh I'm not in this other configuration which um maybe I'm adding another node up here.

41:07 There could be a node X prime which is far to the left of these. It's still an ancestor of K minus one. But this is not part of the spine. We don't want to count this. So we want to subtract the cases where X is a common ancestor of K and K minus one. That gives me precisely the X's on this path that are above of K minus one. but not above of K.

41:38 And from there on um the rest is is doing the math and you get this expression. Maybe let me uh skip the computation. It's the same as before. You insert, you take expectations, you insert from the previous lemas and uh work a bit around the cancellations in in the summations. Now the right spine is completely symmetric.

41:59 you get this n minus k because k here is the number of nodes left the potential numbers for x here is is k things here would be n minus k the point is that in expectation this spine is tiny right it's uh it's never bigger than one in expectation and even for larger k becomes less than one that's an expected value which of course comes from the fact that most keys are most most nodes in a binary search tree are far And you can connect uh I didn't comment properly on this on this lema right um I defined the left and right spine but you can connect the number of rotations that a tree has to do in expectation with these left and right spines.

43:12 this comes from uh the rotations you do. Essentially, when you when you rotate a key X up in the tree, it has to follow some some spine. Um, okay. I wish I wish I had more on that connection.

43:30 Uh, is this precisely the sum of these two things? I'll look that up and and check if if that's um an exact equivalence you get from these two that in expectation you do a constant number of rotations and that's in particular for the keys high up and so um uh if you use trees as a basis for these range trees the um expected cost is still relatively