Video 2-12: Geometric View of BSTs Proof Part 2

0:03 Where we left off was showing that indeed the invariant always holds. And we we've done all the hard work, but let me um insert something on top that makes the argument a lot cleaner, and then uh the rest of this goes through. So, uh we'll we'll prove this by contradiction. Suppose the invariant doesn't hold, then there has to be a violation to the heap property. The binary search tree property we never violate, so that that's uh clearly not not what happens.

0:58 And uh whenever we have things like this, assume that's the first violation in the execution of the algorithm. So, up to this point, the invariant was true. And then suddenly it became false. When can this possibly happen? Uh it can't happen while we're still merely not changing the tree. It can only happen when I go from one time step to the next. Which means I've somehow rearranged the top part of the tree, and now I'm in violation. That's the only place where it can happen.

1:34 Now, what's the heap property? Well, it says at every parent-child pair, the parent is higher priority than the child. So, if there is a violation, there must be one at a parent-child pair. Piece one of the that's one of the missing puzzles from yesterday, if you remember. So, uh that's a simple argument that >> Any such violation you can trace to um a single edge.

2:12 And say without loss of generality Y is a right child of X. Where the priority is the wrong way round, but that's exactly this right because priorities are in X axes.

2:28 And earlier here it means strictly less, otherwise we wouldn't have a violation because the treap is fine with ties. Uh again, um what you really do in a binary search tree is have some binary fication of this. All we're saying is there exists one. Uh and if there is one, uh you of course never violate the heap property inside of this thing. All the priorities are tied. What we really get a violation for here is when these are when when uh Y's priority is strictly less. Now, in principle there could be several cases where this violation occurs.

3:08 And uh the first where it could occur is somewhere up here in the top part of the tree that we now touch and rearrange.

3:23 But that actually can't happen because we by definition of the algorithm rearrange the top part into treap order. So, uh that wouldn't happen. And the same thing if they are both below the top part, not part of the top part.

4:05 >> Well, then I get a violation with that being the earliest violation because I haven't changed anything and the accesses to these guys haven't changed. I'm not touching them now. They haven't been accessed. So, if there was a violation now, um it would have happened earlier. So, the only case that's left is the one that we're we're looking at the picture here for.

4:36 Which means this is a single edge in the tree and it crosses the part that we touch. Second piece that was missing from what follows now, the rest of the argument is as I've I've given it. Um if there's an access to X now, but not to Y by definition of this case three, and then there's a later access to X not before Y is touched, there can't be any point on this side of this rectangle formed by the red axis and this access to Y. So, there has to be a point Z somewhere here. And it can't be Y. Otherwise, we would have touched Y now. It's It's not in the top part. So, it has to be some node Z. Now, the second part that I was missing yesterday is why does Z have to be down there? If it was further up in the tree, if it was an ancestor of X and Y, it would be a common ancestor where they split because X is smaller and Y is smaller. This is a binary search tree.

5:35 This part is blatant obvious, but uh well, uh it's still an argument that's needed. So, Z has to be in the subtree of Y. And And a violation because we can't have touched something without going Y at Y. So, that's the part uh that's spelled out here.

5:57 So, in this whenever you have a point set that um has the uh arbitrarily satisfied property, we can translate that into a valid sequence of trees. And it all nicely works out to be treaps if you look at it look at it in the right way. Treaps over when when the next access uh happens. Maybe it's the Y here. Is that constantly no X like great stuff? Uh this part? Yeah. Oh, it's by definition that uh the next access to Y comes before the next access to X. This would mean there's a another touch of what of X and that is the first access to Y. So, I'm assuming that there's nothing here as well. That's how we drew the picture.