Video 1-5: Treaps

0:02 In the next subsection, we'll look at the first uh essentially two data structures that force our binary search tree to be in the shape as if it had arisen from random insertions even if it didn't. Uh the first is called treaps. You'll see in a second where this name comes from. Let me first throw uh an observation at you that may have at first at face level value nothing to do with our task. If I take a binary search tree, let's maybe do some arbitrary small example to make it concrete.

0:47 I don't want to make it too small. I wish I had another I'll have to rename this. You want to keep a permutation. Here's a binary search tree. I can do the pre-order sequence of that binary search tree. So, I visit the root first. Then I go left and visit the root here, then I go left, visit the root there. I go down here, visit the one, then I come back. The two doesn't have a right child, so I come back. The three has a right child, so I go there. Then I'm done with this subtree, done with this subtree, done with this subtree, and the five has a right child, the seven. So, I go there, then the left child, then I'm going to the nine and then the eight and then I'm done. So, uh I followed this tour around the tree, and I output a vertex the the label of the node the first time I see it, and then not when I visit it again.

1:53 That's pre-order. Uh you all know this from kindergarten. Um the point here is that the pre-order sequence of a key is one is always one valid insertion order that generates this binary search tree. Because by definition, if something comes earlier in the pre-order sequence, then it's higher up in the tree than anything that comes below it or it's separated anyways, and the order doesn't matter. And that's an if and only if. Uh if the uh Look at the three here. Everything that's below, the one, the two, and the four, they have to come after three in any insertion order that's supposed to generate this tree. And again, in the pre-order, that's the case. The three comes first, and two, one, and four come after. There's many insertion orders that generate the same tree. Because after the five, whether I do the three first or the seven first, is invisible to the tree. They're split, and so now it doesn't matter which I do first.

2:56 But pre-order is one such insertion order. Uh and that means it uniquely determines the binary tree shape. Because I can always regenerate the tree with just running through this from scratch and inserting it. Okay. Also, the other way around, the pre-order is unique given a tree. I've just shown you an algorithm to compute it. So, if I can somehow enforce that the pre-order of a tree is as in a binary search tree in a random binary search tree, then I've enforced a random shape of the binary search tree. Okay? So, in a way, this is all we need to do, but it seems unclear how to do that.

3:47 Note that uh in general for a binary tree, you need two of the reorders, pre-order, in-order, and post-order to be given so that the tree is fixed. Um for binary search tree, the inorder is always fixed because it's sorted. So, we really get the preorder and implicitly the inorder sequence of nodes. And those together determine the the tree. How does that help? We can't really change the labels because these are given by the user. The user wants to insert the key seven the item seven. I can't really change that simply uh because it's inconvenient for my shape of the tree. What I can do, however, is add another component.

4:37 For example, let me label these with their inorder index. So, the position in the Sorry, the preorder index, the position in the preorder. And now draw a two-dimensional picture where on one axis we have the value of the keys.

5:09 And on the other axis I have this preorder index. So, both go 1 2 3 4 5 6 7 8 9. And let me decide to here go backwards just to make it nicer.

5:41 It's the same picture just reversed. So, um And now for each um item here, we get a point in the plane. For example, 5 1 is one point. Then 3 2 is another.

6:04 2 3 is another. And 1 4 is another. Okay, need to be a bit more precise. 7 6 and 6 7 Is this so universal? Like where does it even come from? Uh it's impossible to mention these numbers at home for me because it's going to trigger 15 minutes of nonsense. Uh whatever. >> [laughter] >> the internet. Um and 9 8 and 8 9.

6:54 That's a curious bunch of numbers, no? Now there's a certain similarity between this tree and these points there. uh if I apply the following recursive procedure, I can get the tree back. I'm going to start at the top and take some some horizontal line and let them slide down until it hits some point. And what happens when a when a line hits a point is that it breaks. Now uh I suddenly have here a break point. And the lines fall down independently left and right. So, this line now moves down here until it hits another point. And when it does, this becomes the left child of this guy. And similarly, the other line falls down until it hits this point.

8:08 Then breaks into two. Then I have a a node here. And if you check, these are exactly the nodes labeled three and seven as in the tree. Okay? I can recursively continue this process to get a tree which looks a bit stretched but is otherwise the same shape as the original tree.

8:31 Okay. Now, what is special about these pre-order index numbers? Or let me ask another way. What do we need to do to get this tree in the shape of a random binary search tree? Well, we need to make sure the pre-order is as in a random binary search tree. But the pre-order is just the insertion order of the keys, which in a random binary search tree was just any random permutation. So, I want that these numbers here attached to my if if a permutation is random, also the inverse permutation is random. So, I want that the numbers attached to my keys are a random permutation. If I don't know n up front, [clears throat] that's a bit inconvenient to have these numbers be one up to n. I would have to rename things and so on. But remember what was also on the slides way back. I don't want to click through 100 slides, but it was there.

9:32 We can get an alternative model for random binary search trees when we insert uniform identically distributed uniform real numbers between 0 and 1 say. Because the relative order of uniform numbers is again random a random permutation. So there's nothing special about having these be named one up to nine or one up to n. All I need is that they're random numbers and then the rest of the tree will be stretched and squished together. But the topology, the shape of the tree who is who is parent or child will not change.

10:18 That's the idea of treaps. Um formally define them like this. Uh The idea is to have this second dimension. So it's defined for a set of pairs as in the picture. Of a key and a priority. And here I'm defining the priorities precisely like this as some some real numbers between 0 and 1. And let's not worry for the moment about how to represent real numbers in a computer. As you'll see it's all comparison based so you will you will always from these random numbers that will pick only access a prefix of certain number of bits. And that's all essentially with high probability you'll not need a lot of bits there. Okay. Um then the treap is is a binary tree that has this property that it's a search tree with respect to the keys and a heap with respect to the other property. If you look at it that's precisely what we've done here. We always made sure that the parent is higher up than the child.

11:21 That's also known as a heap. A min heap in this case. I didn't explain it that way because I think this this visual explanation is a bit more memorable. But they're equivalent.

11:38 This explanation explains where the name comes from. It's the a portmanteau of tree and heap. Now, let's play mathematician. Uh if I define an object, I want to know whether it exists and whether it's unique. Um both is true here. If I have some some set of such points, uh key priority pairs where all these are distinct to make it uh easier and and more well-defined, then that's the distinctness I need for the uniqueness. Then there's exactly one treap that uh fits our definition.

12:46 There's always built some valid tree and that is one possible treap. For the uniqueness, you want to do an induction over the number of points.

13:07 So, if I have a single point, well, there's only one tree that I can build with this. If I have more than a single point by distinctness of the priorities I have to have one minimum priority. That becomes the root and then I recurse. So Uh K1 and P1 up to KNPN.

13:59 Then I pick all the keys that are less than the key for I. For I, say the root. And the choice of the root is unique by the heap property. I have to have the minimum priority uh in the root.

14:37 So, I take all XJ. Uh Sorry, this was K. The key. where the key is less than the key in the root. Um I take these.

15:07 Again, this They're all distinct, so this uh is exclusive. There's no ties. The treaps for these subsets are smaller than most N minus one, so I can apply the inductive hypothesis. So, they are unique.

15:29 >> And so, the root is unique, its two subtrees are unique, which which means the whole tree is unique. >> [snorts] >> Okay, didn't quite fit uh in my plan space. But that's that's the proof, relatively simple. So, that's good. Uh we have a well-defined thing. Now, uh how can we how can we work this? Okay, one more step. Uh so far it was defined for a fixed set of key priority pairs without telling you where the priorities come from. Um the keys are what is given by the user of the dictionary, and the priorities you just pick uniformly and independently. Uh we'll we'll not worry more about uh whether you can get away with uh with less um powerful randomness. Uh for the moment, let's let's assume they're all independent.

16:25 >> [snorts] >> Now, because we enforced that the insertion sequence is as in a random binary search tree, the shape of these randomized treaps is the same as the shape of a random binary search tree. So, all of the work we've done last week, we can now use and just apply to the treaps.

16:47 Has the same distribution, hence we know, for example, the search cost. Uh the expected search cost is at most the expected depth of any of the leaves, and that's what we computed back then. It was this two times ln n. Remember, this is this 1.39 log n. lg for log base 2. Uh and that's the expected cost. You can also have this high probability statement, same as uh for random binary search trees. Okay? So, that's good. That's a good data structure. Now, what do we need for a good data structure?

17:30 We need some way to build it and maybe also to update it.