0:00

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.

Â 2:36

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.

Â 4:53

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.

Â 6:45

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.

Â