For this final video on binary search trees I want to talk a little bit about implementation, implementation details for the red black tree data structure in particular the insertion operation. As I've said in the past it really doesn't make sense for me to spell off all of the gory details about how this is implemented. If you want to understand them in full detail. Detail You should check out various demonstrations readily available on the web, or a comprehensive textbook, or an open source implementation. Red black trees, you'll recall satisfy four invariants and the final two invariants in particular ensure that the red black tree Always has logarithmic height and therefore all of the supported operations run in logarithmic time. The problem is we've got to pay the piper. Whenever we have a operation that modifies the data structure, it potentially destroys one or more of the invariants, and we have to then restore that invariant. Without doing too much work. Now amongst all of the supported operations there are only two that modify the data structure insertion and deletions. So from thirty thousand feet the approach to implementing insert and delete is to just implement them as if it's a normal binary search tree as if we didn't have to worry about these invariants and then if an invariant is broken we try to fix it with minimal work and two tools that we have our disposal to try to restore an invariant are first of all. Recoloring, flipping the color of nodes from to black and second of all left and right rotations as covered in the previous video. My plan is to discuss the insertion operation not in full detail but I'll tell you about all of the key ideas. Now deletion you got to remember that even in a regular binary search tree deletion is not that trivial and in a red black tree its down right painful. So, that I'm not going to discuss onto for you to text books or online resources to learn more about deletion. So here's how insert is going to work. So suppose we have some new node with the key x. And we're inserting it into a red black tree. So we first just forget about the invariance, and we insert it as usual. And remember, that's easy. all we do is follow left and right shot pointers, until we fall off the end of the tree until we get to a null pointer, and we install this new node with key x, where we fell off the tree. That makes x a leaf in this binary search tree. Let's let y denote x's parent, after it gets inserted. Now in a red-black tree every node has a color. It's either red or black. So we have a decision to make. We just added this new node with key x and we gotta make Get either red or black. And we're sort of between a rock and a hard place, whichever color we make it we have the potential of destroying one of the invariants. Specifically, suppose we color it red. Well remember what the third invariant says, it says you cannot have two reds in a row. So if Y, X's new parent is already red, then when we color X red, we have 2 reds in a row. And we've broken invariant number 3. On the other hand, if we color this new node, X, black, we've introduced a new black node to certain root null paths in this tree. And remember, the 4th invariant insists, that all the root null paths have exactly the same number of black. Notes, so by adding a black note to some but not all of the paths, we're in general, going to destroy that invariant, if we color x black. So what we're going to do is, we're going to choose the lesser of two evils, and in this context the lesser of the two evils is to color x red. Again, we might destroy the third invariant, we'll just deal with the consequences later. So why you ask, is coloring x red and destroying the third invariant, the lesser of two evils? Well, intuitively, it's because this invariant violation is local. The flaw in our not quite red black tree is small and manageable, it's just a single double red and we know exactly The word is it's x and y. So.this sort of more hope in squashing it with minimal work. I can't trust if we coated x black then we violated this much more global type of property involving all of the route in all paths and that's a much more intimidating violation to try to fix. Then just as local one of having a double red between x and it's parent. Indeed some of the time we'll just get lucky and it will just so happen that x is parent y is colored black and then we're golden. This new node x that's colored red, it doesn't create a double red, there's no other violations of the other invariants and so boom, we've got a new red black tree and we can stop. So, the tricky case then is when x's parent y is also red in this case we do not have a red, black tree we have a double red and we have to do some more work to restore the third invariant. So suppose y is red. What do we then know? Well remember, before we inserted x, we had a red black tree, all 4 of the invariants were satisfied. So therefore Y, by virtue of being red, it could not have been the root. It has to have a parent. Let's call that parent W. Moreover by the third invariant there was no double red in this tree before we inserted X so by virtue of Y being red, it's parent W must have been black. So, now the insertion operation branches into 2 different cases and it depends on the color, on the status of w's other child. So in the first case we're going to assume that w's other child that is not y but the other child of w exists in its colored red. In the second case, we're going to treat when w either doesn't have a second child. Y is its only child or when its other child is colored black. So let's recap where things stand. So we just inserted this new node, and it has the key x. And our algorithm colored this node red. So x is definitely red. Now, if it's parent y was black, we already halted. So we've already dealt with that case. So now, we're assuming that y. X's parent is also red, that's what's interesting. Now by virtue of y being red, we know that y's parent, that is x's grandparent w, has to be colored black. And, for case two of insertion, we are assuming that w has a second child, call it z, and that z is colored red. So, how are we going to quash this double red problem? We again, we have 2 tools at our disposal. One is to re-color nodes. The second is to do rotations. So for case 1, we're only going to actually have to do re-coloring. We're not even going to have to bust out per rotations. In particular what we're going to do is, we're going to recolor z and y black and we're going to recolor w red. So, in some sense we take the reds that are at z and y and we consolidate them at w. The important property of this recovering is that it does not break the fourth invariant, remember the forth invariant says that no matter which path you take from the root to a no pointer you see exactly the same number of black nodes. So why is invariance still true after this recoloring, well for any path from a route to a no pointer which doesn't go through the vertex w its relevant. None of these nodes are on that path, so the number of black dots is exactly the same. So think about a path which does go through w. Well if it goes through w to get to a no pointer has to go through exactly one of z or y. So before we did the recoloring this path picked up a black node via w and it did not pick up a black node via z or y both of those were red. Now any such path does not pick up a black node w that's now red but it does pick up exactly one black node either z or y. So, for every single path in the tree, the number of black nodes it contains is exactly the same before or after this recoloring, therefore since the fourth invariant held previously, it also holds after this recoloring. The other great thing is that it seems like we've made progress on restoring the third invariant. The property that we don't want any double-reds at all in the entire tree. Remember, before we did this recoloring, we only had a single double-red. It involved x and y. We just recoded y from red to black. So certainly we no longer have a double reded walling x and y and that was the only one in the tree. So are we done, do we now have a bonafied red black tree? Well the answer depends, and it depends on the core of W's parent. So remember W just got recolored from black to red. So there's now a possibility that W being this new red node participates in some new double red violation . Now w's children, z and y, are black. So those certainly can't be double reds. But w also has some parent, and if w's parent is red, then we get a double red involving w and its parent. Of course, if w's parent was black, then we're good to go. We don't get a double red by recoloring double. W red, so we have no w reds in the tree, and we can just stop. Summarizing, this recoloring preserves the fourth invariant, and either it restores the third invariant, or if it fails to restore the third invariant, at least it propagates the double red violation upward into the tree, closer to To the root.. We're perfectly happy with the progress represented by propagating the double red upward. Why? Well, before we inserted this new object x, we had a red black tree. And we know red black trees have logarithmic height. So the number of times that you can propagate this double red upward is bounded above by the height of the tree, which is only logarithmic. So we can only visit case 1 a logarithmic number of times before this W is propagated all the way to the top of the tree, all the way of the root. So we are not quite done, the one final detail is what happens when this recoloring procedure actually recolors the root. So, you could for example look at this green picture on the right side and ask, well what if w is actually the root of this red black tree and we just recolored it red? Now notice in that situation where the, we are dealing with the root of the tree we're not going to have a double red problem. So invariant three is indeed restored when we get to the top of the tree, but we have a violation of invariant number two which states that the root must always be black. Well if we find ourselves in this situation, there's actually a super simple fix which is this red root, we just recolor it black. Now clearly that's not going to introduce any new double reds. The worry instead is that it breaks invariant four. But, the special property of the root for text is that it A lies exactly once on every route on all path. So if we flip the color of the roof from red to black it increases the number of black nodes on every single routinal path by exactly 1. So if they all have the same number of black nodes before, they'll have the same number of black nodes now, after the recoloring. That completes case 1 of how insertion works. Let's move on to case 2. So case 2 gets triggered when we have a double red and the deeper node of this double red pair, call it X, its uncle, that is if it has grandparent W, parent Y and W's other child, other than Y either. Doesn't exist or if it exists it's labeled it's colored black. That is case 2. I want to emphasize you might find yourself in case 2 right away when you insert this new object x it might be there immediately it has some uncle which is covered x or it might be that if already visited case 1 a bunch of times propagating this double red up the tree and now at some Point. The deeper red node X has a black uncle. Either way, as soon as that happens, you trigger case 2. Well it turns out, case 2 is great in the sense that, with nearly constant work, you can restore in variant number 3 and get rid of the double red without breaking any of the other invariants. You do have to put to use both of the tools we have available in general. Both recolorings and rotations, left and right rotations, as we discussed in the previous video. But, if you do just a constant number of each, recolorings and rotations, you can get all four of the invariants simultaneously. There are unfortunately a couple of sub cases depending on exactly the relationships between x, y, z, and w. For that reason I'm not going to spell out all the details here, check out a textbook if you're interested, or, even better, work it out for yourself. Now that I've told you that two to three rotations plus some recolorings is always sufficient in case two to restore all of the In variance, follow your nose and figure out how it can be done. So let's summarize everything that we've said about how insertion works in a red black tree. So, you have your new node with key x, you insert it as usual. So you make it a leaf, you tentatively color it red. If it's parent is black, your done. You have a red black tree, and you can stop. In general, the interesting case is this new. And you know that x's parent is red. That gives you a double-red of violation of invariant three. Now, what happens is you visit this case 1, propagating this double red upward imagery. This upward propagation process can terminate in one of three ways. First of all, you might get lucky and at some point the double-red doesn't propagate, you do the recoloring in case 1. And it just so happens you don't get a new double red. At that point you have a red black tree and you can stop. The second thing that can happen is the double-red propagation can make it all the way to the root of the tree, then you can just recolor the root black and you can stop with all of the invariants satisfied. Alternatively at some point when you're doing this upward propagation you might find yourself in case 2 as was discussed on this slide. Where the lower red node on the double red pair x has a black or non-existent uncle, Z. In that case, with constant time, you can restore all of the Fourier theories. So the work done overall is dominated by the number of double red propagations you might have to do, that's bounded by the height of this tree and that's bounded by O of log n. So in all of the cases you restore all 4 invariants, you do only a logarithmic amount of work, so that gives you a logarithmic insertion operation for red black trees, as promised.