Transcript


00:11
okay yeah well you have any questions
00:16
you want to ask on past material or any
00:18
issues that may be bothering you or you
00:21
want to talk about no okay so today
00:30
we're going to talk about an alternative
00:35
to AVL trees for the representation of
00:38
dictionaries we're going to talk about
00:39
red black trees red black trees
00:45
historically were really derived from
00:48
another kind of search tree called a two
00:51
three four tree and the red black trees
00:54
were really developed as a binary
00:56
representation of two three four trees
00:58
now the development of red black trees
01:01
and the book kind of follows that
01:02
historical trends so there's a section
01:05
in the book first on two three trees
01:07
then two three four and then how you
01:09
represent two three four trees as red
01:11
black trees we're not going to be
01:13
following that development here in class
01:15
but going to essentially take a shortcut
01:18
and go straight into red black trees now
01:21
if you're interested in following the
01:23
development under additional
01:26
supplemental lectures on the website you
01:30
can get access to lectures on two three
01:35
trees and two three four trees and then
01:37
how you go from two three four to red
01:39
black if you're interested in that line
01:42
of development also there's a new I
01:49
guess section if you want to call it
01:52
that on red black trees that I posted to
01:55
the website yesterday it's a PDF file
01:57
which kind of bypasses the 2/3 to 3/4
02:02
route and goes directly into red black
02:04
trees and so that corresponds more
02:06
closely to what we're going to be doing
02:08
in class today so you may want to
02:10
download that PDF and
02:13
look at red black trees from there okay
02:16
alright so a red black tree is basically
02:21
a binary tree and for the application
02:25
that we're going to use it it's going to
02:29
be a binary search tree the nodes in
02:32
this binary tree will be colored so some
02:36
nodes will be red some will be black
02:38
hence the name red black alternatively
02:40
you may color the edges of pointers so
02:44
some pointers are red in some are black
02:46
okay so you have a definition of red
02:49
black trees based on coloring the nodes
02:53
and you have a parallel definition based
02:56
on coloring the edges and both these
02:58
definitions are essentially the same so
03:02
let's start by first taking a look at a
03:05
definition of red black trees in which
03:08
the nodes are colored and then we look
03:10
at the definition in which the edges are
03:13
or the pointers are colored okay all
03:17
right so it's a binary search tree now
03:19
it doesn't really have to be a search
03:21
trees just because we're talking about
03:22
dictionaries as far as the structure
03:25
goes you can throw the search tree
03:27
requirement out of it okay all right so
03:31
it's a binary search tree for our
03:33
purposes each node is assigned a color
03:40
and in this definition we'll actually
03:43
assume we're working with the extended
03:44
version of the binary tree so we also
03:46
have external nodes so even the external
03:48
nodes have colors in reality external
03:51
nodes are not represented all right so
03:55
the route has to be colored black as
03:58
must all of the external nodes the
04:04
remaining nodes could be black could be
04:07
red but the root and external nodes must
04:09
all be black then you have a requirement
04:12
which says that if you travel on any
04:15
path which starts at the root and ends
04:18
at an external node you should not cross
04:20
to red nodes in a sequence so you
04:22
shouldn't have two consecutive red nodes
04:25
okay a red node has always to be
04:28
preceded by a black node and followed by
04:30
a black node all route to external node
04:38
paths must have the same number of black
04:40
nodes on them alright so we look at an
04:46
example in a moment where I'll point out
04:48
all of these things but before looking
04:50
at the example I want to bring out the
04:52
parallel colored edges definition okay
04:55
so it's a binary tree in our context is
04:59
a binary search tree and each node has a
05:02
color okay colors either red or black
05:05
root in external nodes all of those have
05:08
to be black remaining nodes could be red
05:10
or blank no path from the root toward
05:14
going to an external node should meet to
05:17
red nodes one after the other okay
05:20
should always be broken up with a red
05:22
has to be followed by a black and then
05:25
if you count the number of black nodes
05:26
on any root to external node path all
05:29
such paths must have the same number of
05:31
black nodes write a corresponding
05:34
definition based on coloring the edges
05:37
again it's a binary search tree so we're
05:40
covering the pointers the child pointers
05:44
may be red or black the pointers that go
05:48
into a black or into an external node
05:50
those must be black no route to external
05:55
node path may have two consecutive red
05:58
pointers that kind of corresponds to the
06:00
requirement that no two consecutive
06:03
nodes can be read so instead we say yeah
06:05
no two consecutive pointers can be read
06:09
all route to external node paths must
06:12
have the same number of black pointers
06:14
so that's corresponding to the
06:16
requirement that in the previous
06:18
definition all such paths must have the
06:20
same number of black nodes all right so
06:23
the definitions are very similar and as
06:27
we will see when you look at the example
06:30
if you go the colored nodes route then
06:35
you can figure out what the colors on
06:37
the edges should have been
06:38
and if you go the colored edges route
06:40
you can figure out what the colors on
06:42
the note should have been to satisfy the
06:43
notes definition of the colored notes
06:45
definition okay so they're really in
06:48
some sense equivalent definitions
06:52
alright so here's an example and
06:55
actually have colored and here both the
06:59
nodes and the edges if you're working
07:03
with the colored notes definition only
07:05
the nodes would have been colored the
07:07
edges would not if you're working with
07:09
the colored edges definition only the
07:11
edges would have been colored and the
07:12
nodes would not open okay so for a
07:20
moment think about colored nodes get the
07:23
colored nodes definition so the route
07:24
has to be black the external nodes must
07:27
all be black Kasich got external nodes
07:29
at different levels they're all black
07:30
the remaining nodes can be red or black
07:34
but you can't have two red nodes on any
07:36
path back-to-back okay so if I start
07:40
from the roots and I go down I hit one
07:42
red node here okay but the red node is
07:46
followed by a black node okay if I take
07:49
this path here you get black black red
07:51
black red black okay but you don't get
07:55
black black red red okay so two Reds in
07:59
a sequence is not allowed but a red
08:02
followed by a black is fine okay so we
08:05
satisfy the property that no root the
08:09
external node path has two consecutive
08:11
red nodes on it the last property was
08:15
that every root two external node paths
08:17
must have the same number of black nodes
08:18
okay so if I look at the leftmost path
08:21
one two three four black nodes you look
08:25
at some path down here one two three
08:29
four black nodes
08:31
one two three four black nodes no matter
08:35
which path you take the number of black
08:38
nodes on it is the same
08:44
the same is true if you know the colors
08:46
and the nodes and look at the edges the
08:50
edges into external nodes are all black
08:54
other edges can be red or black you
08:57
can't have two consecutive red edges on
08:59
any route to external node path so if
09:02
you take this one here black edge red
09:05
edge black edge red edge black edge okay
09:08
so that's okay you can have as many red
09:11
edges as you want on a path you just
09:13
can't have two of them back-to-back the
09:19
number of black edges on any route to
09:21
external node path must be the same one
09:23
two three you take a path out here
09:26
one two three or one two three one two
09:32
three okay
09:34
so whichever path you take is the same
09:37
number of blank edges all right so this
09:43
tree satisfies the definition of red
09:46
black tree regardless of whether you use
09:48
the colored nodes or colored edges
09:51
definition now you can induce the color
10:01
of nodes from that of edges and vice
10:03
versa
10:04
a black edge always goes into a black
10:09
node a red edge always goes into a red
10:12
node okay so with that property and the
10:18
property that the root has always to be
10:19
black you can go from coloring nodes to
10:21
coloring edges and backwards all right
10:28
so
10:31
if you look at the notes definition a
10:33
red black tree is simply a binary tree
10:35
in which the nodes are colored red and
10:37
black including external nodes root is
10:42
black external nodes are black on any
10:45
path you can't have two consecutive
10:47
black nodes as sort of two consecutive
10:49
red nodes and the number of black nodes
10:52
and every root two external node paths
10:53
must be the same right so that's the
10:57
definition any questions about the
11:01
definition okay all right so let's take
11:08
a look at properties before we try to
11:11
use this to represent dictionaries we'd
11:14
like to verify that the height of red
11:15
black trees is logarithmic in the number
11:18
of nodes in the tree if it's not
11:21
logarithmic we're not going to be able
11:23
to search our dictionary in logarithmic
11:24
time and of course there's no hope of
11:27
doing inserts and deletes in logarithmic
11:29
time in addition to verifying the height
11:36
there's some other things we'd like to
11:38
verify but that may come as a
11:40
consequence of the algorithms when we
11:44
look at AVL trees so I mentioned that a
11:47
deficiency of AVL trees is that when you
11:49
do a delete you have to the number of
11:53
rotations can be as much as log n the
11:56
height of the tree and that becomes a
12:00
problem in advanced applications of
12:02
search trees so we also want to be able
12:06
to do inserts and deletes in the
12:08
structure but performing at most one
12:10
rotation all right so first let's verify
12:18
the first day where I said okay high
12:21
Heights gotta be right if if the height
12:23
is not right there's no way you can get
12:24
anything else to work in logarithmic
12:27
time so the claim is that the height of
12:30
a red black tree which has n internal
12:33
nodes of course external nodes are only
12:36
there for definition purposes they're
12:38
not really represented
12:41
so the height is going to lie somewhere
12:43
between log n plus one base two at the
12:48
lower end and two times that at the
12:51
upper end
12:52
okay now this pound is easy to see
12:56
because that's a bound on every binary
12:58
tree okay any binary tree with n
13:01
internal nodes has got to have a height
13:04
that's at least log of n plus 1 ways too
13:06
so red black tree has to satisfy that
13:08
okay because the arbitrary binary trees
13:11
could have a height that's n and so this
13:13
is the one that we need to establish
13:15
that you can't be more than two times
13:17
log n plus 1 ways to you know you'll
13:22
notice that this is not as good as the
13:24
height bound for AVL trees AVL trees
13:27
have a height bound that's one point for
13:28
four of this ok so these fellows can
13:31
have a height that's quite a bit more
13:36
maybe about 40 50 percent forty percent
13:40
more than that of AVL trees in the worst
13:42
case okay to prove the bound of 2 times
13:53
log n what I'm going to do is I'm going
13:57
to take any red black tree you give me
13:59
and I'm going to collapse it but
14:02
throwing away not really throwing away
14:04
the red nodes but by merging the red
14:06
nodes into the parent black node okay
14:09
every red node is got to have a parent
14:11
because the root is black and the root
14:13
is the only fellow that doesn't have a
14:15
parent okay so every red nodes got a
14:17
parent so you can merge it into the
14:19
parent and since you can't have two red
14:22
nodes in a sequence you don't get this
14:23
property that a node is merging into its
14:27
parent while its parent is merging into
14:28
the grandparent okay so what you will
14:34
see a picture will merge or collapse the
14:37
red nodes into their parents which have
14:39
to be black nodes and when you do that
14:41
collapsing the height can be reduced to
14:44
it was half of the original height
14:47
because you can't have two red nodes in
14:48
a sequence okay so if you started with
14:52
the height of ten the height might
14:53
become five
14:54
but it may remain 10 because you didn't
14:57
have any red notes and when you do the
15:02
collapsing the degree of the nodes goes
15:04
up the no degree could be anywhere
15:09
between 2 and 4 so if you take a node
15:17
and it collapse it into its parent now
15:19
the parent will have two keys so it will
15:21
need to have three child pointers if you
15:22
collapse and a node and two of its
15:25
children you'll get three keys in there
15:28
and four sub trees hanging off of it
15:30
okay we see that in a picture in a
15:31
moment okay all right so let's look at
15:33
this picture here but here's my red
15:35
black tree I'm going to do the
15:36
collapsing I just said okay so red nodes
15:41
get collapsed into the parent okay so
15:43
collapsing means you just merge this sub
15:46
structure into one node so now the node
15:48
has a 1 a 3 and a 5 minute and these
15:51
four sub trees hang off of it so you get
15:54
it node of degree 4 okay I do a
15:59
collapsing here so this red node
16:02
collapses into that node so I get a node
16:06
that has two keys 30 and 40 but it's
16:08
about three sub trees rooted at 20 35
16:11
and 45 hanging off of it
16:12
so this degree becomes three I collapse
16:17
this red node into its parent and again
16:20
you get a node whose degree is 3 you got
16:22
3 sub trees hanging off of it and it's
16:25
got two keys 20 and 25 and then I
16:28
collapse that red node into its parent
16:30
and you get again get a node whose
16:32
degrees 3 okay so when you do the
16:35
collapsing the red nodes kind of
16:37
disappear okay and you end up with a
16:40
tree whose height may be half of what
16:42
you started with okay but it can't be
16:45
less than half the height may be the
16:48
same as what you started with maybe had
16:50
no red nodes and the degree of the nodes
16:54
could be 2 3 or 4
17:01
okay or any questions about that okay so
17:10
now I want to find okay what is the
17:23
smallest number of nodes I can have in
17:24
this collapse tree okay the smallest
17:27
number of nodes will happen when each
17:29
node is of degree two because if you
17:32
have some nodes of degree three or four
17:33
just throw off some of their sub trees
17:34
you get a smaller number of nodes okay
17:39
so the smallest number of nodes you can
17:42
have in this collapse tree is when every
17:44
node is of degree two okay all right so
17:50
the height of the collapse tree is at
17:53
least half of the original height okay
17:58
the smallest number of nodes happens
18:00
when every node is of degree two if
18:05
every node is of degree two then the
18:09
maximum then you can have at least this
18:11
many nodes in it okay to see this let me
18:14
go back to a previous picture all right
18:25
since the number of black nodes in every
18:27
path is the same okay and you collapse
18:30
red nodes into black what's going to
18:33
happen is that in the collapse tree no
18:37
matter which path you take to get to an
18:39
external node they all have the same
18:40
length okay so really what you have is
18:43
in some sense if you look at the degree
18:46
two version you have a full binary tree
18:49
of that height because all of these
18:51
nodes external nodes are now the same
18:53
level so you have a full binary tree of
18:55
that height so in this case when you do
18:58
the collapsing the height would be one
19:00
two three okay so if you mentally
19:03
collapse everything in it will be a
19:05
height three full binary tree take away
19:07
the nodes of degrees three and four
19:09
throw off some of their sub trees to
19:11
make them all degree two
19:13
okay so when you do the collapsing you
19:16
will end up and throw away subtrees of
19:20
nodes whose degrees three or four so you
19:22
end up with binary nodes you'll end up
19:24
with a full binary tree of that height
19:26
and if a full binary tree has height H
19:29
the number of nodes in it is 2 raise to
19:31
H minus 1 all right so the so if the new
19:38
height is H prime which is at least H
19:40
over 2 the smallest number of nodes you
19:42
can have is when the degree of every
19:45
node is 2 and at that time you'll have 2
19:48
to the H prime minus 1 nodes but since
19:52
you could have had nodes of degree 3 and
19:54
4 the number of internal nodes is only
19:57
bounded below by 2 to the H prime minus
19:59
1 okay and what that tells you is that
20:04
the number of nodes is okay at least
20:08
that but H prime is H over 2 so if you
20:13
put that in you get that the height is
20:16
at most 2 times log of n plus 1 all
20:24
right so you can prove that the height
20:25
is at most 2 times log of n plus 1 by
20:29
collapsing red nodes into the parent
20:31
black nodes now in the in the notes that
20:40
you have that this minus 1 that messed
20:43
up into the superscript so you want to
20:45
drop it back down the minus 1 here and
20:47
there is not supposed to be part of the
20:48
superscript it's the lower level okay
20:59
all right a property that I stated
21:05
that's important is that insertions and
21:07
deletions can be done using at most one
21:09
rotation but there will be other
21:14
operations that could be logarithmic
21:15
these are called color flips which you
21:18
will see in a moment and in some sense
21:22
in the case of AVL trees you adjust
21:27
balanced factors and you may do log in
21:28
balance factor changes here you don't
21:31
have balanced factors you have colors so
21:33
you may do log and color changes an
21:38
example where this property is going to
21:42
be very important is later when you come
21:45
and look at private research trees at
21:47
that time we'll see that each node in
21:50
our binary tree that we have is going to
21:54
have two keys in it okay and the
21:59
structure is simultaneously going to be
22:01
a search tree on one of these keys and
22:03
it's going to be a priority queue on the
22:05
other one okay and so when you do the
22:13
color flip that's just changing colors
22:16
so changing colors of nodes does not
22:18
affect the search tree property and it
22:20
doesn't affect the priority queue
22:22
property because you're not moving
22:23
anything around but when you do a
22:26
rotation rotations are designed to
22:29
preserve the search tree property
22:31
okay so rotations preserve the search
22:34
tree property but they mess up the
22:35
priority queue property on the other
22:38
keys on the second key and so you have
22:42
to rectify that mess up and rectifying
22:45
that mess up takes logarithmic time okay
22:49
and if you're going to do log end
22:53
rotations then fixing the log n mess ups
22:57
from the rotations at log n per time
23:00
would make your complexity of the insert
23:03
and delete log Square and on the other
23:05
hand if you're doing only one rotation
23:08
then it's only once that you have to fix
23:11
that mess up in the pratik you part and
23:13
so it's only login additional work to
23:15
fix that okay all right so that's one
23:21
place where it's essential that you use
23:22
red black trees and not AVL trees to get
23:26
logarithmic performance these complex
23:32
kinds of binary trees also get used in
23:34
data structures for packet forwarding
23:37
where inside each node of the binary
23:41
tree you may actually store a large
23:44
number of keys and those keys are stored
23:47
also by having a binary search tree
23:50
embedded inside of each node of the
23:52
overall binary search tree so again when
23:56
you do this rotation it messes up the
23:59
properties of that internal structure
24:02
and to fix the properties of the
24:04
internal structure takes logarithmic
24:06
time and if you do only one rotation
24:08
then the added work to fix up the
24:11
structures inside the nodes is log n if
24:13
you do multiple rotations it becomes log
24:16
square n so that's another place where
24:19
this essential that you use red black
24:21
trees are not AVL to guarantee
24:23
logarithmic performance another property
24:32
that they have is that even though an
24:35
individual insert or delete may change
24:39
the color of log n nodes in an amortized
24:43
sense the amount of bookkeeping work
24:46
that's done the bookkeeping being the
24:48
rotation and the color changes is only
24:51
order one for insert and delete so the
24:57
overhead over unbalanced binary trees is
25:00
constant from the amortized point of
25:03
view it's an additive constant rather
25:06
than a multiplicative right so the extra
25:10
work is order one
25:17
red-black trees you can find them if you
25:20
look in the standard templates library
25:21
there's an implementation of red-black
25:23
trees she go into java there's a class
25:25
called tree map they use red black trees
25:29
out there to represent dictionaries so
25:33
it's a structure that is in fairly wide
25:36
use and certainly has been implemented
25:39
in commercial systems now let's take a
25:43
look at the insert and delete operations
25:45
the ideas are very similar to what
25:48
happens in AVL trees you rotate when you
25:51
get into trouble okay all right so we're
25:56
going to insert the new elements you get
25:59
a new node you stick it and you have to
26:00
choose what the color is going to be
26:04
okay you can put it in as a black node
26:08
if you put it in as a black node then
26:10
you you're guaranteed you have a problem
26:12
because there's one route to external
26:14
node path that has an extra black node
26:16
in it from the others okay so if you put
26:19
in as a black node you're always going
26:22
to be fixing a problem you guaranteed
26:24
there will be a problem in terms of
26:26
imbalance and number of black nodes in
26:27
different paths and also it's a little
26:32
bit difficult to rectify that problem if
26:35
you put it in as a red node you may or
26:38
may not have a problem okay if the
26:41
parent of the new node is black you just
26:42
leave what you find if the parent of the
26:44
new node is red then you got to fix the
26:45
problem so sometimes you got to fix a
26:48
problem sometimes you don't okay but
26:52
when you do have to fix it we can fix it
26:54
with color flips and rotation and a
26:56
single rotation okay and so a new node
27:00
is always put in as a red node and then
27:02
if you have two red nodes in a sequence
27:04
we'll fix the problem by doing flips and
27:07
a rotation okay all right so that's the
27:10
first decision
27:14
all right so you put in your new node
27:16
comes in as a red node and then you
27:18
check to see if the parent is also right
27:19
if so you got a two red node in a
27:22
sequence problem and you got to fix that
27:23
okay so we clap so for the fixed thing
27:28
we say that's a let's say initially P is
27:31
the newly inserted node okay in which
27:33
case a and B are null then it's got a
27:37
parent which is also red if it it has a
27:44
grandparent there's got to be black
27:45
otherwise you have two red nodes in a
27:47
sequence before you did the insertion if
27:49
it doesn't have a grandparent then we
27:53
can just change the color of this fellow
27:55
to black okay so so you've got two red
28:05
nodes in a sequence as guaranteed so P
28:07
and P P exists if P P is red but is the
28:12
root okay then I'll just change it to
28:14
black that will increase the number of
28:16
black nodes and all paths by one which
28:18
is okay and we'll fix the two red node
28:21
in a sequence problem okay so we will
28:22
assume that the grandparent exists now
28:25
what will happen is that subsequently we
28:27
will be propagating this situation
28:29
further up the tree okay so in one cycle
28:32
I'll do something to fix this problem
28:33
and then this will become my P its
28:36
parent will become P P and the
28:38
grandparent we come GP when you do that
28:40
we have a node P which is potentially
28:44
red and it may not have a parent you
28:46
can't leave a red root so you have to
28:49
change the color to black all right so
28:55
we assume that G P exists and we don't
28:58
assume it has to exist otherwise we just
29:00
change the color of P P if P P doesn't
29:03
exist I just change the color of P to
29:05
black okay so all three of those fellows
29:08
exist we classified the problem very
29:11
similar to how we do for AVL this is the
29:15
old LR scheme based on GP looking like
29:18
the a node okay so if you go into the
29:20
left subtree of GP x is L so in this
29:24
case it will be L if you go
29:27
further into the left subtree of P P
29:30
then Y will be L if you go into the
29:32
right subtree of P P Y will be R okay so
29:38
if P is the right child of P P Y is our
29:40
in our case P is the left child so in
29:42
our case Y will be L and then I have
29:46
this n sub classifier which is based on
29:50
the color of this node here okay so if
29:54
that node is black or if it doesn't
29:55
exist then I'll say that Z is little B
30:01
if that node is red then Z is a little
30:04
while okay
30:06
so I would say a little finer
30:08
classification than you do in an AVL
30:10
tree let's look at the cases okay
30:18
suppose you're an X Y R okay so the
30:21
color of D is red and then it doesn't
30:24
really matter whether your ll allow our
30:26
RoR L it's all the same as I've just
30:30
shown a picture here which is an LL our
30:34
situation but it doesn't really matter
30:36
what you have okay in this case I'll do
30:39
a color flip okay so in a color flip
30:46
okay what you do is you change the color
30:49
of well I guess if you're looking at it
30:53
from the node point you change the color
30:55
of PP and it change the color roof GP
30:57
okay so you flip their colors this
30:59
becomes black that becomes red okay so
31:05
that's what I do and I'm going to do
31:06
that independent of what x and y are
31:08
okay now when you do a color flip okay
31:16
this route becomes red okay and at least
31:23
at this level we've solved the two red
31:28
node in a sequence problem okay because
31:30
now you no longer have two red nodes in
31:32
a sequence there you don't have it here
31:34
and you don't have it out there because
31:39
I'm going to change the color of that
31:40
red node to blah
31:41
okay so this is changed from red to
31:43
black that's changed from red to black
31:45
and that one has changed from black to
31:46
red okay but when I do this I might
31:52
create a problem because the
31:53
great-grandparent might be red so you
31:55
may have two red nodes in a sequence but
31:57
it's two levels further up the tree so
31:59
this becomes my new P and then its
32:02
parent becomes PP and as a grandparent
32:04
becomes GP and I continue the process
32:07
okay so my three fellows PPP and GP move
32:13
up two levels and I continue rebalancing
32:17
alright so in a color flip you change
32:20
the color of two children nodes and
32:24
their parent right
32:33
when D is B that's when you have to look
32:36
at all of the different cases for x and
32:37
y so if you have an ll be kind situation
32:43
okay so ll and then the color up there
32:46
is black or it's no okay then we'll just
32:51
do an LR so we do an ll rotation okay
32:55
and when you do this rotation the
33:04
rotation does not affect the number of
33:06
black pointers on paths from the root to
33:08
an external node okay in this case here
33:11
to get to the external nodes in a B say
33:14
a and B you go through a black node here
33:18
or if you want to count pointers you go
33:20
through a black pointer here we go
33:22
through a black point of that so - black
33:23
pointers or 1 in to 1 into 1 & 2 okay
33:29
same thing is true here 1 and then 2 1 &
33:33
2 1 & 2 1 & 2 so the number of black
33:36
pointers and paths to external nodes in
33:38
the subtrees ABC and D is unchanged as a
33:41
result of this rotation so we don't
33:44
affect the property that number of black
33:47
pointers and all paths should be the
33:48
same they're still the same if it was
33:49
the same before
33:52
also when you make this rotation we have
33:58
fixed the two red nodes in a sequence
34:00
problem here and we couldn't possibly
34:02
have propagated it further because to
34:07
propagate it further you have to change
34:08
the color of the node at this position
34:10
to read but that's still black okay so
34:13
we can't have two red nodes in a
34:14
sequence so we've solved the two red
34:17
nodes in a sequence problem that we
34:18
started off with okay so in this case
34:21
you've finished
34:22
so this rotation solves the problem it's
34:26
the same as the ll rotation for AVL
34:28
trees right the other case is a similar
34:36
you have an LR B case and we'll perform
34:43
an lr rotation so you do the LR rotation
34:49
again you can count the number of black
34:52
pointers and all paths into the subtrees
34:54
ABC and D they're the same on this side
34:56
as they are on that side so you don't
34:58
affect the number of black pointers
35:00
property also the root here is black so
35:06
you can possibly propagate the two red
35:08
nodes sequence problem further up the
35:10
tree okay so in this case two you're
35:14
done it solves the problem and that's
35:17
the same as the LR rotation
35:26
the RR b and the RLB of the asymetric do
35:31
these so as far as insertion goes some
35:38
of the time you just doing color flips
35:41
and sometimes the color flip
35:43
may solve the problem sometimes it may
35:45
propagate it further up the tree
35:47
whenever you do a rotation the problem
35:49
is not propagated up the tree terminates
35:53
okay let's take a look at delete so
36:01
again you do a delete much like you
36:02
would do it in an ordinary binary search
36:05
tree and then you check to see if you
36:08
have a to read node in a sequence
36:10
problem so I guess in this case you
36:15
won't have to read nodes in a sequence
36:16
we will see that you may have a black
36:19
node deficiency all right so if you have
36:25
one to remove a red node okay whenever
36:29
you do a deletion is one node is thrown
36:30
out if that node that you threw out is
36:32
red well you're okay because the number
36:33
of black nodes and all paths remains the
36:35
same and by throwing out a red node you
36:37
can't possibly create two red nodes in a
36:39
sequence right so if a black node is
36:48
deleted then the subtree or which it is
36:54
root becomes one black node deficient
36:56
okay and so we need to rectify that
37:00
problem so let's take a look at how we
37:03
identify the source of the problem okay
37:05
so it's a get in different cases for
37:06
deletion so the note that is physically
37:12
removed could be a leaf it could be a
37:16
notice degree as one or the other case
37:19
is notice degree two because the degree
37:21
two case if you recall can't arise the
37:23
way deletion works we will see that
37:25
again okay so suppose you're deleting
37:27
the eight okay then this fellow goes
37:30
away and essentially what you left
37:34
without there is an external node some
37:36
at least okay so the subtree rooted out
37:39
here is one black node deficient to get
37:43
two external nodes here takes you one
37:45
less black node or black edge than
37:47
everybody else so the root of the
37:50
deficient subtree we'll call that Y and
37:53
we'll call its parent okay
37:56
py if the deficient subtree doesn't have
38:01
a parent then this Y must be the root of
38:04
the whole tree in which case every path
38:07
has become one black node deficient
38:09
which is okay right
38:11
so we assume that the parent exists all
38:18
right so if you're deleting a node of
38:21
degree one okay right black nodes say 45
38:28
then the way that's done is you kind of
38:32
change the pointer from the parent 42 go
38:34
to the 60 so in this case this is the
38:42
root of the deficient tree okay and its
38:46
parent is 40
38:59
well the third possibility finally lists
39:01
all cases the node you delete if it has
39:05
a parent it could so and then the no d
39:09
delete could have zero children one
39:11
child or two children so we did the case
39:15
of zero children and one child the other
39:17
case you might want to think about is
39:18
two so for example here if somebody asks
39:26
you to delete a seven that's really
39:27
transformed into one of the previous
39:29
cases so to delete the seven you'll
39:31
actually take the five and put it in
39:32
here and then this is the node that's
39:34
physically thrown out so the new
39:35
external node here would become Y and
39:37
this would be py okay so this is really
39:41
not a case the previous two cases cover
39:43
everything the node that is physically
39:45
deleted is always either a leaf or of
39:48
degree one all right so you got all the
39:51
cases covered so we now know what Y is
39:58
if Y is a red node as it was in a second
40:02
example here we just change its color to
40:04
black then that subtree is no longer a
40:07
black node deficient okay so this would
40:10
solve the problem so in this particular
40:12
case here okay Y is red make it black
40:16
get up okay doesn't matter it could have
40:19
a whole bunch of children down there
40:20
okay you're done all right so the case
40:30
you have to consider well I guess
40:33
another case Y is a black root okay then
40:39
the entire subtree is a black node
40:41
deficient doesn't matter you're done
40:49
all right so we assume that Y is black
40:53
but it's not the root of the whole tree
40:56
okay so in that case is going to have a
40:58
parent P Y so Y has a parent P Y and
41:05
since it's a black node deficient its
41:11
sibling has to exist okay if it didn't
41:14
have a sibling
41:15
we'll then the number of paths going
41:19
this way okay through black the number
41:22
of black nodes on these paths cannot be
41:24
one more than the number of black nodes
41:25
on those paths okay so there's got to be
41:28
a node out here it doesn't have to be
41:31
black it could be red because the black
41:33
nodes may be further down okay but
41:34
there's got to be a node out here
41:36
otherwise Y cannot be a black node
41:39
deficient okay all right so this know it
41:44
exists and then we don't really know the
41:46
colors of those edges that could be
41:48
anything
41:48
simply the color of this node and that
41:50
node could be anything okay all right so
41:57
we classify the problem using a three
42:03
tuple scheme the first one here tells us
42:09
whether the Y node is the left or right
42:11
child of its parent P Y so in our case Y
42:15
is the right child so X will be our then
42:25
we look at the pointer coming into the
42:28
node V to the equivalent of looking at
42:31
the color of the node V okay so if the
42:33
point R coming into the node V is black
42:35
equivalently we is a black node then
42:38
we'll say that C is B otherwise C is R
42:44
then I look at the number of red
42:46
children that V has okay so if we has
42:52
one red child and it's one otherwise it
42:55
could be zero it could be two of course
42:58
if the color of V itself is red then it
43:00
can't have any red
43:03
all right so I classify in that way and
43:06
then for each of the cases I have a
43:09
remedy let's go through some of the
43:13
cases I don't think we can go through
43:14
all of them but we'll go through some of
43:16
them all right it'll be the case of rb0
43:22
okay so why is the right child of its
43:26
parent the pointer coming in here is
43:29
black and it's got no red children this
43:34
is case one because this node itself
43:36
could be black or it could be red okay
43:38
so in case one this node is black so in
43:44
this case what I'll do is I'll change
43:50
the color of this black node to red
43:52
since it has no red children I don't
43:55
have two red nodes in a sequence since
43:58
this is black I don't have two red nodes
44:00
in a sequence okay so I don't create a
44:02
two red node in a sequence problem but
44:05
by changing this node from black to red
44:07
what I've done is that now the one black
44:13
node deficiency has moved from here to
44:15
this level okay so every external node
44:18
in this bigger subtree is one black node
44:20
deficient so I can propagate the
44:22
deficiency further up and hopefully in
44:24
the end it will reach the root and just
44:26
leave the tree okay right so I do a
44:30
color change the deficiency is
44:34
propagated one level up and now this
44:38
becomes my Y node and its parent becomes
44:41
my P Y and I reapplied the
44:42
classification second case was this node
44:50
is red okay this is still black because
44:54
it's got to be black by definition got
44:55
to have zero red children all right so
45:01
in this case I again change the color of
45:07
some nodes from black this goes to red
45:09
that one goes from red to black
45:15
when I do this the number of black nodes
45:18
and paths to external nodes in Y goes up
45:21
by one with the number and paths to
45:23
external nodes and a and B is unchanged
45:25
so I've solved the problem all right now
45:36
suppose you have one red child here I
45:44
don't care about the color of this guy
45:46
it could be red it could be black so in
45:53
this case I'm going to do a rotation
45:56
okay and this is really an LL type of
46:00
rotation so I do a rotation as shown and
46:09
if you count the number of black nodes
46:11
and paths to external nodes and a B and
46:15
Y see that the number one path to a and
46:17
B is unchanged from before with those in
46:20
paths to Y go up by one and so you solve
46:23
the problem so this rotation solves the
46:30
problem
46:38
I'll bury one case two is where the red
46:42
child of V is the right child instead of
46:44
the left child okay so in this case - I
46:48
will perform a rotation this is more of
46:53
the LR variety so if you do an LR
46:56
rotation again if you count the number
47:00
of black nodes on paths to a B and C
47:03
they're unchanged from here to there but
47:06
those into Y go up by one so that solves
47:09
the deficiency problem the RB 2 case so
47:24
both children are red again I perform
47:35
that transformation which is again an LR
47:38
rotation again if you count the number
47:47
of black nodes and paths to external
47:50
nodes in ABC they're unchanged but in Y
47:53
it goes up by one and so it solves the
47:55
deficiency problem
48:05
all right the case where the node V was
48:08
read then we have a further
48:12
classification in terms of the number of
48:15
red children of V's right child W okay
48:20
so V is red okay then it's going to have
48:26
a black child okay and then we just look
48:32
at the number of red children that that
48:35
fellow has but again the node W has to
48:43
exist because this is one black node
48:45
deficient from parts out here so they've
48:48
got to be black nodes on this side in
48:49
order for this to be one black node
48:51
deficient okay so they have to be black
48:53
nodes if that's right then the children
48:54
have to be black so you don't have to
48:57
worry about the existence of W rights in
49:03
this particular case there are two red
49:05
children of W you call that an RR to
49:07
case you could have an RR 0 or R 1 and R
49:11
2
49:14
all right so the RR 0 okay you got a
49:18
black node here it's got no red children
49:19
I don't really need to know what that
49:22
node looks like okay in this case I
49:27
perform an ll rotation okay and if you
49:34
look at that ll rotation you'll see that
49:37
the number of black nodes and paths into
49:39
a and B is unchanged from before but
49:42
into y there's one extra black node from
49:45
before so this solves the problem
49:56
the RR one case so W has one red child
50:01
it could be this one it could be that
50:03
one so you got two sub cases to look at
50:05
here so I perform a rotation this is an
50:11
LR rotation again if you count the
50:16
number of black nodes in two paths
50:17
getting into a B and C they're unchanged
50:20
but into y it goes up by one so it again
50:23
solves the problem and then there are
50:31
two more cases to look at the our our
50:34
one case two where the red child is over
50:38
here instead of here and then the our
50:40
our two case when both of these are red
50:42
children okay so the the the the the
50:46
PowerPoint notes that you have have got
50:48
the diagrams for both of those cases
50:50
again it's a rotation and once you do
50:53
the rotation you can verify that the
50:55
number of black nodes and paths into a B
50:57
and C is unchanged and into y it goes up
51:00
by one and so that rotation fixes the
51:02
problem okay alright so the nice thing
51:06
about red black trees is that regardless
51:09
of whether you doing inserts and deletes
51:10
the number of rotations needed to fix
51:14
any problem that arises as a result of
51:17
the insert or delete is always limited
51:19
to what also the amortized cost of this
51:23
fix up process after you do the real
51:25
work to do the insert or the delete to
51:28
get you back into your red black tree is
51:30
order 1 instead of order of log n the
51:32
extra rebalancing work whereas in an AVL
51:36
tree that's not the case yeah
51:47
the arrow from from V to be let me see
51:55
I've got one too no I need it to be
52:03
black because I need to go through two
52:04
black nodes to get into the subtrees I
52:06
got to go to this one and that this was
52:08
previously a red node okay if this is
52:11
still a red node I got two red nodes in
52:12
a sequence I got a problem and so I make
52:15
that route black that's why I've got a
52:18
black if you have a black edge black
52:21
edges go into black nodes this guy so
52:23
the route out here's got to be black so
52:24
now to get him to external nodes here I
52:27
got two black nodes which is what I had
52:29
before
52:29
also I don't have two red nodes in a
52:31
sequence okay alright any other
52:36
questions
52:39
okay so we'll stop you