Video 2-11: Geometric View of BSTs

0:03 The next section is mostly based on a single paper that introduced a very beautiful idea and some consequences from it. Uh it it shines a very different light on this problem we've talked so far about. And this is uh a geometric way of looking at this binary search tree problem. Uh or the the paper had essentially three contributions to are listed here. One is um there's a different contender for dynamic optimality now. A different optimal a different online algorithm that may be optimal or not, who knows. Um I'll talk more about that. Uh but also maybe conceptually a different way that makes many results a bit more intuitive. And the third result is what I alluded to earlier, namely that computing optimal is likely NP-hard. Uh the third result in this paper is that a generalization of the real problem that doesn't uh include the special case we're interested in is is likely hard. Uh the way this works in a picture is that instead of an access sequence of numbers, we look at a geometric point set, 2D points.

1:20 They're all on integers. The key space I'm I'm just replacing with numbers between 1 and n. All all the points um all that will matter is the relative order of x and y coordinates. So, it's without loss of generality that it's on the integer grid. This doesn't matter. Uh if you have if you're given some access sequence for some given key set um 1 up to n, then the the 2D points are the y-axis is the time, and I'm always drawing it downwards. So, um it increases downwards. You'll see in a second why this is the right way to do it. Uh and the x-axis is the element that is accessed. X like axis. I guess that works nicely. And then it says the binary search tree problem is equivalent to finding some additional set of points, the red guys in this case. But this is one option, it's not the only way. That satisfies some some geometrically defined properties.

2:21 And then it corresponds to a binary search tree algorithm that solves this access sequence. And we can precisely say how much it would cost if we executed it.

2:31 I think at that point, if you just look at this and you stare at this diagram, it's very cryptic what on earth this should have to do with search trees. I will get there. I should also say this has been around for a while. Initially, when this was published, people were very enthusiastic that now the big conjectures are all going to fall one after the other. And this has not yet happened. There's a few very cool results that followed from this, but not the big one. Neither for splay nor for this other contender. Um so maybe it's less powerful than we thought or some clever ideas are just lurking beneath the surface waiting to be discovered. And the the uncertainty which of these two options it is, I think is part of the fun.

3:20 So what are these point sets about? Um the simple property that we have to satisfy to make out of this access sequence one that simulates a binary search tree is that we have to add points to make the total point set arborially satisfied. So tree-ish, if you like. Uh we'll always start with this access sequence x as before. Uh not in dotted, please. So again, this is the the set of points where you have an access at time t to an element at t. So x axis is the access element and and y axis is the time. And you want to find a super set. You add some red points. A super set of x that should be arbitrarily satisfied.

4:12 Uh what does arbitrarily satisfy satisfied mean? Uh let me do an example here and then explain. And going to add this one. And this. And this and this. Arbitrarily satisfied means that whenever you find you define a rectangle take any two points in your point set. Say these two. They define a rectangle. That rectangle is not allowed to be empty. Um it must contain another point unless the two points you chose are on the same x or same y coordinate. So these two are not on the same x and y coordinate. Hence for this uh set to be satisfied, I have to add one of those red points. In this case one of the two would have been enough. But if I say leave out this one and only add this guy, there's another rectangle formed by these that forces me to add a point here.

5:23 Um if you take say this guy and this guy the same is So this is a property of a point set. It doesn't matter if it's red or red or black. This large rectangle contains a ton of point sets. That's all fine. Um in principle for such a rectangle to count as non-empty we need a red point here here, or here, or here. Anywhere in the interior or on the boundary is fine. But if you think about it, uh if if you have a point in the strict interior, say you only had this case, so then well, let's draw symmetric case once for change.

6:13 Suppose the only point in here was this guy. Then I find another rectangle where I take this point and the corner, or the lower and this corner. And I have to have a point in this rectangle, in these two rectangles as well. So, you can keep going like this, which means we can always force a point to be on one of the two uh sides. So, from every point to every other point, there's these two sides. Mhm. So, this and this, or that guy. One of those two sides has to have a point, otherwise I get a contradiction from some smaller rectangle.

7:05 That's already a small observation or a little lemma. Now, you can check, unless I made a mistake here, this the union of the black and the and the red points that aren't are really satisfied.

7:19 Um so, you can always find some points to add to your set of rectangle to make this happen by essentially adding the corners of rectangles. Right? When you When you have an unsatisfied rectangle, putting in one of the two corners makes that one satisfied, and it doesn't add new unsatisfied rectangles with the original two points, because the new point is on the same X and Y uh line.

7:51 So, the problem is is what does this have to do with binary search trees? Let me copy the picture. Uh the problem is uh that's not what I wanted. That this is the trace of an execution of a binary search tree algorithm seen serving this sequence.

8:12 >> [snorts] >> And uh if you look at a certain time slice, so say at time t equals 2, the points that you have on this Y line, these are supposed to be the nodes in some top tree sub part, some top part of a binary search tree that you touch at that point.

8:34 Now, why that is connected um we'll we'll show in a second. Um but let me define um Okay, first the theorem. Uh let's rather first first define the problem. Uh The the problem will be you're given a point set X, and we specifically care about those that come from the access sequence, but in principle, you could ask the same question for any subset of of uh 2D points. And I want to find the smallest superset that makes this union the smallest superset that is already satisfied.

9:15 And if that analogy to binary search trees is correct, that at any time you're touching precisely the elements that have a point in that line, the total cost of the binary search tree algorithm is just the total number of points in this point set. So, cardinality of Y. That's why this is so cool. It makes the problem much cleaner. We don't have a weird model with moving pointers and all that. We don't need any of that. All we have is this set of points and a slightly awkward property of how to make it satisfied.

9:50 So, let me prove um the connection to the trees. And this is in a way doubly constructive. Um it shows nicely what what happens in in both cases.

10:08 yeah. So, we'll prove that a point set Y uh corresponds to a valid BST execution. So, a valid trace of a BST execution means if I execute my binary search tree algorithm and at every time step is one access to some element, what is the BST algorithm allowed to do? Well, it touches a top part of the tree. And I'm going to make a point for that key that I touched at that time step if that node was part of the top part of the tree that was touched. So, this corresponds means of Y So, Y intersect all of N times just the time T of BST touched at time T.

11:20 That's what this left side is supposed to mean. And the right side, I guess, is clear. And the claim is this is an if and only if.

11:31 So, of Of you want to prove the two implications for this. Now, let's first assume that we have a point set that corresponds to a binary search tree algorithm. So, we've we generated it by tracing a binary search tree algorithm. So, we have to show that it doesn't contain any unsatisfied rectangles.

11:52 Yeah. And maybe it's convenient to give the access sequence a name. Maybe we don't need it, but um >> [snorts] >> Just to be specific.

12:35 Now, let me just draw this schematically, there are no unsatisfied rectangles in in this point set. Uh so, let's look at some some time I and some later time J.

12:56 And uh two elements that are accessed at time I and J. These are two points. They could be at risk of forming an independent an unsatisfied rectangle.

13:10 And note though that these may or may not be um original accessed elements. These might be any point any nodes in the binary search tree that are touched. Okay, I'm I'm drawing them in black because I don't want to uh stare at red all the time. But, these can be any points in Y. Indeed, Y doesn't even distinguish between the the original access sequence points and whatever was added to make this thing up really satisfied or so. Uh I mean, uh I shouldn't I should say it doesn't distinguish between the access points and the notes on the search path. that come from the trace. So, let's say this is uh key X, this is key Y. Okay?

14:06 Let's also denote by A the lowest common ancestor of these two of X and Y. Um Okay, I've also have these. Let Let's call it B because A is already used. And uh the understanding is that because X and Y from the different time slices, these the trees are rearranged, so these move around. So, B can change with time, right? Uh for from each time step to the next, it might be some different lowest common ancestor.

14:51 Now, let's look at um the two time points just before we do these two accesses. Right before time I, when we access X, uh there's there's the option that this lowest common ancestor is um not the same as X.

15:21 Which means the lowest common ancestor of X and Y, well, that's certainly some ancestor of X because it's lowest common ancestry is indeed a specifically a common ancestor. So, um at that point So, I'm going from it's not really readable from root to X. Again, remember that the fact that there is a dot means I've touched X at time I, which means I always have to start at the root. I have to have reached it. So, if B is on the path from the root to X, I have touched B. That means there is a point B, so also observe This should have come maybe before this.

16:28 At any point in time, the lowest common ancestor of two nodes in a binary search tree has to in value between those two. Uh if it was to the left or to the right of both, then the search path for both elements continues over the same edge, so it cannot be the lowest common ancestor. It has to be in value between those two. So, again, um there must be a dot for touching B at time I, and B is somewhere between these, so B could be here.

17:14 Or it could be Y, that's also fine. In either case, my rectangle would be satisfied. Symmetrically, if right before time J if my lowest common ancestor is different from Y by the same argument, I have some node here.

17:50 Which would mean there's some element In this case, I also have a point in my rectangle. And uh this is rectangle is satisfied. So, there's only an awkward case left.

18:16 Which means that neither of those two things happened. At time I the lowest common ancestor of X and Y was X. And at time J, it was Y.

18:41 This by itself is not a contradiction at all. But it means that uh if you if you think about how this looks in the tree the fact Well, what what does it mean that the lowest common ancestor between X and Y is X itself? That means there's X here. And then I have a path down to Y. I don't know what is on this path. But I mean uh if lowest common ancestor between two things is one of those, the other is an that a descendant. So, this is at time I, but then at time J, I suddenly have X symmetrically below Y.

19:20 How do I get from this to this? Well, only if at some point I rotated X down. So, I have to have somehow rotated this edge. And for that, I have to touch X. Okay?

19:57 And this touching X to rotate it is happening somewhere in between Y and J, so it could be somewhere here. And voila, we again have our point in the rectangle.

20:07 So, in all cases, if we start with a point set that's generated as the trace of a binary search tree algorithm, it has to be a an arborially satisfied point set.

20:26 That part is cute. That shows you where this operation come where this property comes from. Uh but the cuter and much more insightful direction is the opposite because uh somehow we're now generating a tree out of nothing. I just have this bunch of points.

20:45 So, how can we show that also the other direction works? So, here AS is not almost surely or something like that. It's uh arborially satisfied.

21:11 Let me again uh um draw a small example to illustrate this construction a bit. We'll essentially show constructively that there is uh a binary search tree algorithm whose simulation whose trace is that point set. And the constructive argument there is what makes this uh powerful.

21:50 Uh what does this mean? Um I mean I I can proclaim that at certain times I touch certain nodes, but this has to have somehow fit together. If I have a if I've touched some some nodes in the previous step, and then in the next part I touch some completely different part of the tree, there's no way to have a a route between those or somehow uh I have to be able to go from one step to the next by rearranging this top part of the tree. That's all I'm touching. Right?

22:43 Okay, so small example. Uh Try not to waste too much time on this. Also, I think I need a bit more space. Let Let me draw it here to make it a bit bigger.

23:06 It's going to be small example with just four different keys and one two three four five time steps. And I'm going to have accesses time one I'm accessing one time two I'm accessing this this. It's a relatively harmless sequence of accesses. And let me um add some points to make this a really satisfied again.

23:52 I'm following an algorithm which I'll I'll teach you but may have to wait till tomorrow morning. So the basic idea is somehow inductively I suppose there is a binary search tree up to this point. Now we touch or visit this top part of the tree.

24:31 And now I have to decide how to rearrange this. And I'm going to use a treap. And there's only going to be a little bit of a cheat in this. Maybe someone spots it. So it's a cheat it's a treap where the priority is the next access time for these elements.

25:14 This may be eerily familiar. It sounds a bit like what we've said greedy future does. But it's in this case where we're given the the points in advance and it's not just the accesses to the keys, it's also again, maybe I'll do an example. What I mean is any dot on the same vertical line.

25:36 So, these are the keys one two, three, and four. And I'll I'll draw in between the time steps what the tree looks like before the axis, then what happens at the axis, and then what the tree looks after. So, before we start the rule doesn't really say that much, but let's suppose the initial tree is also formed in the same way. I'm building a tree over the first axis. So, for for this time step here before the time 0.5 if you like the the points that are relevant is the topmost point for the topmost dot in every column. So, this one, this one, and this one, and this one. These are my priorities for the trips. So, clearly the tree will just look like this.

26:30 Or let me write the keys to be more specific. One, two, three, four. As makes sense, these are actually the the actual first accesses to the elements. So, that's a good initial tree to look to to work with even intuitively. Okay. Now, at this time I'm going to touch the top part of the tree. So, here Now, this I did in red always, right? Okay, let's do red. I visit the one and I can rearrange the single node, so nothing's going to happen. Still going to be 1 2 3 4. Now, I going to touch the first two part, the first two nodes, one and two. And now the algorithm says, take for these two nodes their next access and arrange them according to that. The one is touched only at this time five, whereas two is touched right again after, so two wins. So, two goes to the root. And one goes down. And then I'm reattaching the subtrees. Here, it's just like this.

27:40 Okay? And observe that now two three, the next thing I'm supposed to touch, is again a top part of the tree, so I can do that. And I do the same. Two is accessed at time five, three is before, so three wins.

28:00 And I'm I'm reattaching the subtrees, so this one and this one. I just go one and four. That's right? I'm only looking at the red elements. Uh because uh the other ones I may want to rotate up or so, but I'm not allowed to, right? In this time step here. Um so, this is always this is touching this, this is touching this, this time I'm touching this. I only touch these top two nodes, two and three, so I can only change those two. The subtree of two elements, I can only put it one of the two configurations. Now, in this >> So, it's like that. One is touched at five. So, So, what I mean is uh there's time 1 2 3 4, right? And five. So, here two the next access next access to two after this is at time five.

29:10 And for three, the next access um after time three is at time four. That's why here four wins and becomes the root. And the two is hanging down.

29:31 It's the same though. Uh here one is touched at five and two is touched at three. Yeah, but the next is at three. It's always the highest that wins. All right, time progresses top-down. And the next access means when is the the the nearest from now that I'm going to touch this node again. Uh in general, they're all going to be touched many times more, but the first one is what counts. That's what I mean by next access time here.

30:10 Uh and then already at the end, I think. So, here uh the three wins again because four is never touched any again at any time. This just stays. And the last step touches all of this to reach the point one.

30:28 So, this in the example kind of shows what happens. Uh I'm glossing this is a well-chosen example to make one special case disappear. You can think about which one. Uh what I want to do in the remainder of the time is convince you that this is not just a happy example where it works out, but indeed that um we have an invariant the entire tree is a treap over the next axis time. And that's way stronger than what I've what I've done here. I've only just looked at the top part and rearranged the top part. I've not touched any of the subtrees. The example is a bit small. There's not too much going on in the subtrees, but even if they're arbitrarily big the claim is or the invariant says even between such time steps the entire tree is a treap.

31:58 So, maybe schematically, right? Um Why is this so big? Uh if I'm if I'm sitting between these two time steps here's T, here's T plus one. Ah.

32:14 Space is for free, right? Um I'm looking at this. This is where I'm I'm sitting. Now, there will be points for all my keys somewhere somewhere here somewhere further down and there could be many. And if I were to draw this a bit more carefully, you would see that some are on the same x-axis as others. Uh in a way, what counts is just the the top top most of each of these. If they're below, then let's let's pretend these are these are above of each other.

33:00 Uh but this is separate. This is separate. Say this is separate, who knows. Uh only the top uh of each of these poles is what counts.

33:13 So, I'm going to take these these next axes is and build a treap on those. So, if you will, take the points as they are.

33:30 Copy them somehow scaled. No, just All right. So, the treap at this point in time looks like a treap ought to look like for the points of this shape. So, uh and here you see what where the the cheat comes in. There may be ties. Like this this top root thing, these are all on the same line. They're kind of one um multiary uh node here. Whereas the rest is then a binary tree. So, the only cheat, if you like, is that here treap means I'm relaxed in terms of ties. They can go either way. There is a way to pick a binaryfication uh of this of this conceptual treap where I have several several keys in the same wide node with several children. All right. So, you you can say this is one big node and it just has slots for one, two, three, four children.

34:32 That's one option. Or you say there is a way to make this fat node into a small binary tree over three nodes that makes the rest work out. I'm just not going to tell you yet which it is. But that's the invariant. Um there is always a tree of this relaxed kind for all the keys in the data structure. Uh not just the ones that I touched. For those I'm explicitly building it like this, but uh for the others um we have to show that this is this is indeed the case.

35:22 And um why is the invariant even important? Uh I guess that's something I should have said. If the invariant holds, it means that any point between the accesses the tree is heap ordered, priority ordered by next access. But well, this means that all the elements that are touched in the next time step are above everything touched later. So, they form a top part of the tree and I can do this access that I'm supposed to be able to do. It worked out in this example magically, but uh we didn't prove that it does or why it does.

36:23 Okay. Uh so, conceptually we have some binary search tree. There's some sugar cone. Looks a bit like a a mountain with snow. There's some top part that we touch. And um suppose this was violated. So, there uh Let me get rid of this. We touch some top part. And suppose there's a um a node X here.

36:59 And a node Y here. Which is a child of X. Um and so, if there's any violation to the invariant, there must be one where it's a it's a node below X. I guess this needn't even be a child edge. Uh it's it's fine if this is any path, I think. So, suppose there's uh a pair of nodes so that the next access time for Y uh next access for Y is earlier Yeah, in that case, the invariant would be violated. And now we have to show that this can't happen if the point set is averagely satisfied. Right? So, I'm I'm trying to come to a close soon.

38:05 We're currently at this point now. We're looking down, when are these things accessed next? There's the next access time of Y, which comes first. Then there's the next access time of X, a bit later.

38:21 And then there's X and Y somewhere in key space. The way I've drawn it here, X is smaller than Y. This is in general the other case is symmetric.

38:31 So, um we're now touching Uh now it doesn't have a line yet. At the current point, we have touched X. There's a a red dot for X now. And then there's dots for Y at this time and for X at this time by definition. And this the next X is time. Okay. Now, uh I Since the point set is satisfied, there must be some some point in this rectangle of this X and this X.

39:28 because well, X is touched after Y, strictly after. The strictly less. So, this is not going to satisfy the rectangle. If the rectangle is supposed to be satisfied, there must be some point here. And remember this little lemma, if if there is uh if there is a satisfying point without loss of generality, if it's on one of the two uh co- um boundaries of the rectangle.

40:02 So, this is just from overall satisfaction. Now, uh this point set also somewhere in the key space. This is between X and Y in key space. Where can it be in our tree? Well, uh uh it has to be um Uh I think here I need that Y is directly the child of X.

40:44 So, there's nothing else between those two. The point is that indeed Z has to be somewhere in this subtree. Uh and it's touched now. But, uh Z is a descendant of Y, which we don't touch. So, that's somehow a contradiction. We would have had to jump over Y to reach into this subtree. And that can't happen.

42:01 Subject to the um the case that Z is above in the tree that we somehow have to exclude. Uh that proves that the invariant always holds. And we've seen it work at the example. So, in principle, given such an arbitrary point satisfied point set, you can reconstruct what the binary search tree algorithm was uh while it was running or what what it was doing. What of course is not clear from that is this just a trace. It tells you, "Ah, now I'm doing this tree. Now I'm doing that tree." If there was any logic behind this, it's completely unclear. And for an arbitrary point set, there may not be any logic. It might just be random points.