Video 1-7: Insert at root

0:04 So far the treaps still use rotations, which we started out as saying at least being a bit inconvenient to implement because you have these two cases that are a bit tricky to put together into one. And there's a a general solution that does better, which is just departing from the way we insert into binary search trees.

0:27 We can simplify further um by an alternative that works for general binary search trees and has nothing to do with randomization from the start. Um we need a helper procedure to split a binary search tree into two binary search trees that contain all the keys that are less than a given key and all the keys that are bigger than a given key. This sounds like it's expensive, but it turns out it's actually a proportional to the height again. And we need the inverse operation, a join operation, that takes two trees where everything in the one tree is smaller than everything in the other tree and puts them together as one tree.

1:09 To make the code particularly clean, I'm using uh this trick that the children are not two separate pointers, left and right, but a tiny array of two entries. Then you can often combine certain cases um and use a helper method for when the subtree potentially has changed to update the subtree size, which is if you remember what for rank-based operations, we need this so that we can uh find elements by rank or uh count the number of elements smaller, these things. >> [snorts] >> And that split can be built as a a simple recursive procedure. And then maybe give the the picture version next to it. Um it's a recursive procedure. I have some key in the root and I want to split around a key X. And in general, this is a binary tree that has two subtrees, either of which could be empty, but there's going to be some left and right subtree.

2:14 Now, what I do depends uh it's going to be big braces. Uh what I do depends on how X relates to Y. If X is less than Y, the right side with Y can stay the same, but I want to recursively split the left side. So, I'm going to assume in this case that I'm splitting This is such a such an amazing feature. I've I've already turned off the scroll bar on the right and still sometimes happens. It's not clear to me why. Okay, let's do this. Ah, stay where you are.

3:09 So, I'm splitting L around X recursively. A bit small to read. And that gives me two subtrees, uh two two trees containing from L everything that is less respectively greater than X. And what I return is a pair, namely the tree LL and a new tree that I reassemble from the bits and pieces I have like this.

3:38 Right? That way I have made one step progress. I'm I'm a little further down. Uh the recursion in particular is on a subtree of the original, so I I make progress. The other case is symmetric. If X is greater than Y, there's going to be an R L R R coming from a recursive call of the right.

4:10 And then I reassemble in the same way symmetrically. Y is in the root. The L stays the same. Here we have R L. And then there's R R with bigger than X. R Uh surprisingly in code, this is very little text. It's doing the same thing. There's one recursive call. Um Here the cleverness comes from passing down the the direction is zero or one depending on how X and Y your called t.key are related.

4:45 Uh so I can pass the appropriate child to split. I can reset the appropriate child with a bit of uh logic. Here you see which one is reset. Um and I can update the size in between even when uh I'm doing this rank-based queries. And what I return is this little pair of nodes and Java doesn't have pairs, so it has to be a little array. Okay, fairly simple procedure. It's just recursion with an appropriate base case. Uh join, same game. Again, recursive procedure. Remember, it has the assumption that everything in the key to the left is smaller than everything in the key to the right. This is important, otherwise this wouldn't work. Um So, I don't know if I uh want to try to sketch it. So, this X and L1 R1 which joins with Y L2 R2.

5:53 And then I have different cases if both are empty, that's the first line. Uh I return empty a leaf. Um if X is less than Y, I guess S X always has to be less than Y. Uh what does the code do? Uh how does it break the tie?

6:35 By size. Um So, you have two two trees you could build. Both are valid binary search trees. And maybe just draw both and we'll we'll modify the choice which to use in a second anyways.

7:00 Uh the other would be you put the Y up here and then the X here. Then Uh sorry. The join here. Uh both are valid and you have some some choice which one to pick. Here I'm somewhat arbitrarily choosing by size, but this uh you can you could also do differently and we will. Okay, that's the join.

7:41 And with With you can do insert and delete very easily. In particular the insertion now makes sure that the new key is always in the root. I'm going to come to an end in two minutes. You first split the key the T the the tree around the key X. You make a new root node and append the two split subtrees as the children of the root. And the way you split them around the key X makes sure that these are valid subtrees. And for deletes you find recursively the tree the node that you want to delete. If that is the right key that you want to delete, you return the join of its two children. And pass that up as the new child of your parent. And the rest is the search part which just goes in the direction where you would find key X. And here you always Following an edge means replacing it by the return value because the child could be the one that was deleted and then you get a new child passed back up.

8:48 It's very clean and and compact code. Now this is in in general a bit awkward because we had this choice in join and it's not so clear whether one or the other option is better but in treaps and here's finally a Tamio's very concise C++ implementation of treaps which follows this paradigm. In treaps what you want to do for join is break the tie here by priority. If X has a smaller priority than Y you pick this version. If Y is a smaller priority you pick that one.

9:45 >> And so, by and large, uh this code does exactly that. Um it has some further s- character savings baked into it. First of all, it works with pair because C++ has this built in that saves a few uh a few bits. Um another clever trick that the Java code above didn't use is the use of um a special sentinel node for the leaves, which has loop pointers back. So, it's is one object that is rep- that is replacing the null pointers. And it has a pointer back to itself. And that way you can avoid checking for null, instead checking for for equality with this thing. Uh that removes one or two corner cases. Um you can also, with extracting the place where you change the child of a node in a single place, isolate where you have to potentially do something on the subtree. For example, the size um of the subtrees or here computing sums on sum over the subtrees.

10:58 Um modification of the size uh follows the same procedure. And so, this uh for this part, I would say is is the end of that story. Um less than 50 lines of code clearly fits on the slide in a font size that you can read. Um the C++ code maybe is very terse uh if you're not used to this. The Java version, based on the bits I've shown you in the previous slides, maybe takes 20 extra lines of code, but is also very clean and simple. And the good thing is also, you can you can write this down from memory and there's only a few places where you have to quickly think, but there's no weird things you have to learn by heart. Everything is following if you if you keep these two recursions in mind, the rest follows.

11:53 It has all the good properties of treaps, which have all the good properties of binary search trees. You can do insert, you can do delete, you can do rank-based operations, uh everything you may may want um with clean and simple code.