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.