Transcript


00:16
okay all right in the last lecture we
00:21
saw two three four trees which were a
00:24
generalization of two three trees and
00:28
today what we're going to do is we're
00:30
going to first take a look at some of
00:32
the shortcomings of two three four trees
00:34
and then see how we can overcome these
00:37
shortcomings by simply mapping a two
00:40
three four tree into a binary tree and
00:44
the mapping is going to result in a very
00:46
popular balanced binary search tree
00:50
which is called a red black tree all
00:53
right so first let's take a look at some
00:58
of the problems with two three four
01:00
trees if you recall the node structure
01:03
that's employed and a two three four
01:05
tree is one that is large enough to
01:07
represent a four node as a result we
01:12
have four pointer fields the left child
01:15
left middle child right middle child
01:17
right child and in addition to these
01:20
four pointer fields we have three data
01:22
fields P 1 P 2 P 3 okay now if you're
01:26
representing a two node then it's only
01:29
this part of the node that gets used you
01:32
have only one day to feel that you need
01:34
and two pointers so more than half of
01:36
the node is wasted space if you're
01:40
representing a three node well then you
01:42
only need two point of fields and three
01:44
data fields so this part P 3 and our C
01:47
are not used so the space wastage is not
01:51
as much as when you're using this node
01:53
structure to represent a 2 node but
01:55
still you do have a couple of fields
01:56
that are not utilized ok so one problem
01:59
with the 2 3 4 structure is that in
02:05
order to get good efficiency by not
02:08
having to make too many calls to new and
02:13
delete methods so that when you go from
02:16
a to node to a 3 node you don't only get
02:18
different memory or when you go from a 3
02:20
node to a fro node okay you end up using
02:22
a node structure which looks like this
02:25
but that that means that
02:28
a fair amount of space gets wasted okay
02:31
so fall of the nodes you have in your 2
02:33
3 4 tree or 2 nodes then more than half
02:35
of the allocated memory is unused the
02:41
other problem with this node structure
02:44
has to do with time ok so if you look at
02:47
the overhead involved with certain
02:49
operations for example if you have a 2
02:51
node you're occupying these 3 fields and
02:53
then you do an insert into this node
02:55
which makes it a 3 node and if the
02:58
insert is a value that is smaller than
03:00
what's here then you've got to move
03:01
these ones further down ok so you've got
03:04
relocation involved okay similarly if
03:07
this is a 3 node which is growing to a 4
03:09
node and the new data field has to
03:10
occupy position p1 then you've got to
03:13
move p2 to that position p1 to that
03:15
position this child pointer there and
03:18
this child pointer over here ok so
03:21
you've got overhead involved as you go
03:23
from 2 nodes to 3 nodes three nodes to
03:25
four nodes and the reverse when you do a
03:27
delete safe from a four node to a 3 node
03:29
and 3 2 or 2 ok this lot of data
03:31
movement that's taking place within
03:32
these nodes so we'd like to overcome
03:35
these problems associated with a 2 3 4
03:39
tree and to overcome these problems
03:45
instead of representing a 2 3 4 tree in
03:49
its what you might call its native or
03:51
intuitive way using this kind of
03:54
structure we will instead map it into a
03:57
more efficient binary tree structure so
04:02
in the binary tree representation of a 2
04:05
3 4 tree we will have different
04:07
representations for 4 nodes three nodes
04:09
and two nodes as binary nodes or a
04:12
collection of binary nodes okay so if
04:15
using a binary tree then each node can
04:19
have one data field and we'll have two
04:21
pointers okay so for example if you take
04:24
a four node in our 2 3 4 3 well a 4 node
04:30
needs 3 data fields and for pointer
04:33
fields and we're trying to map this into
04:35
the binary world we're going to need to
04:38
use three binary nodes each binary node
04:41
has a
04:41
one day the field by using three binary
04:43
nodes we can get three data fields
04:46
needed for XY and Z so the mapping we're
04:50
going to employ is a four node is going
04:53
to represent is will be represented by
04:56
this configuration of binary nodes the
04:59
binary nodes will have colors on them so
05:01
we have black nodes and red nodes okay
05:04
each node has one data field and it has
05:08
two pointer fields okay in this picture
05:10
here the pointers themselves are colored
05:15
so XYZ gets stored in this fashion and
05:19
it preserves the binary search tree
05:21
properties that are needed this data
05:23
value here is smaller than Y and that
05:26
data value there is bigger than Y okay
05:31
all right so a four node can be
05:33
transformed or represented as a
05:35
collection of three binary nodes in this
05:37
fashion okay now in all of our
05:40
transformations it will be the case that
05:42
red nodes will have red pointers coming
05:46
in to them and you might think of red
05:51
nodes actually as being part of the
05:53
parent black node okay so if you were to
05:56
collapse these nodes the red nodes into
05:59
their parent which will always be a
06:00
black node then you'll get back your
06:03
original node right if you have a three
06:11
node okay then to represent this using
06:16
binary nodes we'll need to binary nodes
06:18
because we got two data fields here and
06:20
so are two binary nodes will be
06:22
sufficient so this is one way in which
06:26
we can represent this three node as to
06:30
binary nodes you have a black node and
06:33
then it has a red node as a child okay
06:36
the X shows up on the left subtree too
06:39
so that the resulting binary tree we
06:41
have will be a binary search tree again
06:46
red nodes will always have the property
06:49
that they are connected to their parent
06:50
by a red pointer they will always have a
06:53
parent
06:54
and if you collapse the red node into
06:56
its black parent you'll get back the
06:57
original three mode now for three nodes
07:02
there are two possible representations
07:05
one has y as the root structure of this
07:09
subtree the other one will have X as the
07:12
root structure as the root node okay so
07:17
we could also go this way here and this
07:19
will still give us the binary search
07:21
tree property or any questions about
07:29
mapping three nodes into two binary
07:31
nodes okay again if you look back at the
07:35
four node mapping there you don't have a
07:36
choice if you're going to use three
07:38
nodes you would end up going in that
07:41
fashion making the assumption that the
07:45
parent of the red nodes has to be a
07:47
black node
07:54
right so that leaves us with a two node
07:56
okay so if you look at a two node well
08:00
this looks like a binary node in any
08:02
case okay it's got only one data in
08:05
there and so this would be mapped into a
08:07
single binary node and that will be
08:10
mapped into a black binary node okay so
08:16
the mapping strategy simply it a 2 3 4
08:21
node whether it's a 2 node 3 node a four
08:23
node always gets mapped into one black
08:26
node plus additional red nodes the black
08:30
node is the root of that sub structure
08:32
the red nodes are the children of that
08:34
black node
08:43
alright so for example if I started off
08:47
with a two three four tree and performed
08:50
this mapping so wherever I saw two node
08:52
I put in a single black node wherever I
08:54
saw a three node I put in a black node
08:55
and a child red node and wherever I saw
08:58
a four node I put in a black node with
09:00
two red children then I could end up
09:03
with a tree that looks like this okay so
09:08
here for example if you look at this sub
09:11
structure here okay you have a black
09:14
node with two red children from our
09:16
mapping we know that these three nodes
09:18
together actually represent a four node
09:22
okay if you look over here okay a black
09:28
node with only one red child we know
09:30
that this represents a three node okay
09:34
similarly this one here represents a
09:36
three node it just took a different
09:38
orientation from that one this fellow
09:42
here is also a three node okay so
09:47
whatever you see red nodes they must
09:50
have a black parent and then if you
09:53
collapse the red node of the black
09:54
parent you'll get the original three
09:57
node or foe node okay again here you can
10:00
see that if you perform the collapsing
10:02
okay then these external nodes would
10:05
move up to this level okay
10:07
similarly out here if you did the
10:09
collapsing the external node should move
10:12
up and all of them should lie on that
10:14
level here and the same thing over there
10:17
to get back the original two three four
10:20
three
10:26
okay all right so we can start with a
10:28
two three four tree perform this mapping
10:30
on the two nodes three nodes and four
10:33
nodes and transform the two three four
10:37
native representation into a binary tree
10:40
representation in which the nodes are
10:43
colored red and black edges are colored
10:46
red black or any questions about how you
10:51
would transform okay all right so if we
10:58
look at this configuration we can notice
11:03
some properties of the transform red
11:06
black tree for example we know that
11:13
whenever you have a red node it has a
11:16
red pointer coming to it okay black
11:20
nodes if they're not the root black
11:22
nodes are black pointers coming in from
11:25
their parent if you travel along any
11:30
path from the root to an external node
11:34
okay the number of black nodes will be
11:37
the same because the number of black
11:38
nodes or each black node represents an
11:41
original node of the two three four tree
11:43
and the red nodes are just offshoots of
11:45
that original node so if you travel on
11:48
any path from the root to an external
11:50
node you should encounter the same
11:53
number of black nodes because in your
11:55
two three four tree the number of nodes
11:57
and any route to external node path was
11:59
the same also since since red nodes are
12:06
kind of I guess red nodes don't really
12:13
represent original nodes in the two
12:15
three four tree and we said a red node
12:18
must always have a black parent so that
12:19
if you were to collapse it into his
12:21
black parent you would get an original
12:23
node of the two three four tree it
12:25
follows that you can't have two red
12:27
nodes in a sequence a red node always
12:29
has a black parent so if you follow any
12:33
path from the root towards the bottom
12:36
you will not
12:37
and do a red followed by red right has
12:40
always to be followed by a black alright
12:48
so some properties of these trees the
12:52
transformed binary tree the nodes and
12:55
edges are colored okay
12:57
the root node is always black if you
13:05
look at the other nodes then black nodes
13:07
of black edges coming into them red
13:09
nodes have red edges coming into them
13:14
and therefore if you know the edge color
13:17
you can figure out the node color if you
13:19
know that node color you can figure out
13:20
the edge color okay so you don't really
13:23
need to keep both of them in a computer
13:26
representation one is enough
13:39
okay so we can define red-black trees
13:45
independent of transformations from two
13:48
three four trees by simply making use of
13:50
the observations that we just saw we can
13:52
have a colored nodes definition and a
13:54
colored edge definition so the node
13:57
definition we say a red-black tree is a
14:00
binary search tree every node has a
14:07
color the root has to be black all the
14:13
external nodes have to be black can't
14:18
have two consecutive red nodes on any
14:21
root two external node path old root two
14:27
external node paths have the same number
14:28
of black nodes okay so these these are
14:31
all observations we'll already made
14:32
previously with respect to the
14:35
transformation but now what we're saying
14:38
is that anything that satisfies these
14:41
conditions is a red black tree
14:52
we can have an equivalent definition
14:54
based on coloring the edges still a
14:57
binary search tree now the edges are
14:59
colored so you either have red of black
15:03
edges the edges going to external nodes
15:08
have to be black you can't have two
15:13
consecutive red pointers when you travel
15:16
from the root to an external node
15:17
corresponds to can't have two
15:20
consecutive red nodes have to have the
15:25
same number of black pointers in every
15:26
route to external node path corresponds
15:28
to having the same number of black nodes
15:30
in every route to external node path so
15:34
you can define red black trees either in
15:37
terms of coloring nodes in terms of
15:38
coloring edges the definitions are
15:41
pretty much the same either way now what
15:48
you can show is that if you start with
15:50
either of those two definitions then any
15:53
red black tree that you come up with is
15:56
actually a representation of a two three
15:59
four tree and it's not hard to show that
16:05
you simply say that whatever you have a
16:10
red node it's got to have a black parent
16:12
because you can't have two red nodes in
16:13
sequence so you can collapse the red
16:15
node into the black parent and that
16:20
gives you leaves you with some notes
16:22
that are two nodes some that are three
16:24
some thereof four and since only the
16:27
black nodes are left and the number of
16:28
black nodes and every due to external
16:30
node path is the same you satisfied the
16:34
requirement of a two three four tree
16:36
which says all external nodes are the
16:38
same level since all paths have the same
16:42
length from root to external node all
16:44
external nodes must be in the same level
16:46
and therefore once you do this inverse
16:48
transformation you have to get back a
16:50
two three four tree alright so every two
16:54
three four tree can be represented as a
16:56
red black tree every red black tree is
16:59
the representation over two three four
17:01
tree
17:04
or any questions
17:16
now we know that the height of a two
17:19
three four tree at worst it is log base
17:24
2 of the number of elements that happens
17:27
when every node is a two node so if you
17:33
start with a red black tree whose height
17:36
is roughly log of n base 2 and you
17:38
transform it into a red black tree okay
17:40
then the height could remain the same
17:43
because everybody was a two node or the
17:47
height could double because you had some
17:49
path that had all four nodes on it every
17:52
four node gives you a structure of
17:54
height 2 in fact every three node gives
17:57
you a structure of height 2 ok so if you
18:00
start with the worst case hype 2 3 4
18:02
tree you could end up with a red black
18:05
tree whose height lies between log of n
18:08
base 2 and log of n 2 times that you
18:11
height may double all right so the
18:17
height of a red black tree can't be any
18:20
more than two times this 2 times log of
18:23
n plus 1 ok the height cannot be
18:26
anything less than that that follows
18:28
from the properties of binary trees a
18:30
full binary tree with n elements has a
18:32
height that is log n plus 1 base 2 ok so
18:36
you get the lower bound from properties
18:38
of binary trees you get the upper bound
18:40
by starting with the worst case height
18:42
for a 2 3 4 tree and then multiplying
18:45
that with two alright so red black trees
18:51
have logarithmic height the height
18:53
property is not as good as that for AVL
18:55
trees AVL trees you can only go to one
18:57
point for for log n plus 1 ok so the
19:00
height here could be a little bit worse
19:02
actually was by almost 40% compared to
19:06
the worst case AVL tree
19:11
however as we will see red black trees
19:13
have interesting properties not shared
19:15
by AVL trees which makes them very
19:19
useful in a variety of applications the
19:23
most important property that makes red
19:25
black trees the choice over AVL is that
19:29
when you do inserts and deletes that
19:32
most one rotation is performed
19:35
whereas with AVL trees you can do log n
19:38
rotations red red black trees are
19:47
implemented in C++ standard template
19:49
library
19:50
they're also implemented in Java well
20:00
let's take a look today at how you might
20:04
do inserts in a red black tree and
20:08
today's discussion we're just going to
20:10
mimic how you would do top-down inserts
20:13
in a two three four tree from our last
20:15
lecture and this mimicking of the
20:18
top-down two three four insertion is not
20:21
going to give us the one rotation limit
20:25
Oh max on an insert we actually have to
20:29
do it
20:29
bottom-up the different strategy which
20:31
you look at in the next lecture but the
20:36
top-down will illustrate most of the
20:38
concepts involved in the bottom-up
20:40
scheme okay so we'll basically just
20:46
mimic the steps we went through the last
20:49
lecture and the strategy there if you
20:53
recall was that during the insert you
20:55
follow a path from the root toward the
20:57
leaves and anytime we encounter a phone
21:01
ode you split that into smaller degree
21:05
nodes so the cases that we looked at
21:10
then the first case was the root itself
21:13
as a for node then before stepping on to
21:15
the root we split the root into three
21:18
nodes in this fashion okay all right so
21:22
this diagram should be familiar from the
21:24
last lecture
21:25
now we'd like to do exactly the same
21:26
thing in the red/black world okay so in
21:31
the red/black world I would look at my
21:33
route and suppose I'm using the colored
21:39
edge representation then the node would
21:42
have two bits in there one says the left
21:46
child is a red edge or a right edge the
21:48
right child pointers left is red or
21:50
black so by looking at those two bits if
21:53
both of those bits are red then I know
21:55
that the route is a four node so you
21:59
have a route and then it's got two red
22:01
children so it's a four node okay so I
22:03
can detect this condition by taking a
22:06
look at the binary node which is the
22:09
root and that would contain Y and it
22:11
would have two colour bits in there one
22:13
for the left child pointer one for the
22:14
right and if both of those are red I
22:16
know that's a four node root
22:20
alternatively if you're using the
22:21
colored nodes representation well then
22:24
I'd have to follow the left child
22:26
pointer in the binary node for Y and see
22:29
if it's pointing to a red node or a
22:31
black node similarly follow the right
22:33
child pointer so either way you can tell
22:35
whether you're trying to move on to a
22:37
four node so if you're moving on to a
22:40
four node well then I want to make this
22:42
transformation the binary representation
22:45
of this should be transformed into the
22:48
binary representation of that now the
22:53
binary representation of this node is
22:55
this in the binary representation of the
23:02
transform structure is that okay so
23:06
structurally the before and after
23:09
configurations are the same the only
23:11
difference is in the color of nodes and
23:14
edges okay so if I'm attempting to move
23:19
to the root of my red black tree and the
23:22
route is a four node then I need to
23:24
change the color of the edges if you're
23:27
using the colored edge representation to
23:29
black or you need to change the color of
23:31
the children from red to black if you're
23:34
using the colored nodes representation
23:37
okay so I've got to do a color change
23:40
it's either change to bits in the root
23:43
here or change one bit there and one bit
23:45
that in this world here to make this
23:51
transformation I have to make two
23:55
invocations of new to get nodes for
23:59
these fellows I've got to then move a
24:01
whole bunch of data around and move a
24:02
whole bunch of pointers around here all
24:05
I've got to do is change two bits from
24:07
red to black so the time required for
24:12
this splitting of four node of four node
24:17
into three two nodes is much less all
24:26
right the other case we had was you're
24:29
sitting at a two node and you're trying
24:30
to move to a four node and then that
24:33
broke down into three sub cases the four
24:35
node you're trying to move to his a left
24:36
child
24:37
middle I saw into two cases is a left
24:42
child or a right child of the two no dia
24:43
currently sitting at so here's one of
24:47
the cases we're sitting at a two node
24:49
and we're trying to move to a four node
24:51
and this four node is the left child of
24:53
the two node then he have a symmetric
24:55
case where the four node is out here and
24:57
you're trying to move here so in this
25:01
case this was the before configuration
25:04
and then this was the after
25:06
configuration okay so we made this
25:08
transformation and having made this
25:10
transformation we then decided whether
25:12
to move to W or to Y and so you move to
25:15
a two node okay so again in our red
25:20
black world we would need to detect that
25:22
you're sitting here at the two node and
25:24
you're trying to move to a four node we
25:26
already know how to detect if you're
25:27
moving to a foe node and having made
25:29
that detection we want to make this
25:30
transformation so in the red/black world
25:35
this configuration is going to look like
25:37
this you're sitting at the two nodes
25:39
it's got two black children and then
25:42
you're trying to move here to a four
25:44
node so this node here is about to read
25:46
children
25:48
so this configuration looks like this in
25:52
the red/black world and then i want to
25:54
transform this into this configuration
25:58
here okay so you have a three node okay
26:04
this is one representation for a three
26:07
node okay and of course there's another
26:11
representation too which would have X at
26:14
the root and Z on the other side but
26:19
since I'm doing the transformation I can
26:22
decide which orientation I want to use I
26:25
have the freedom I can either transform
26:28
into this configuration or I can
26:29
transform into the alternative
26:31
configuration with X at the root and Z
26:33
as the right child of X since I have
26:36
that choice here
26:37
I will opt for this particular choice a
26:40
lot for this one because this looks
26:42
structurally the same as that okay so I
26:46
can transform this before condition to
26:48
this after condition without changing
26:50
any pointers without moving any data all
26:54
I need to do is a color flip in a color
26:58
flip you change the colors here and you
27:03
also change the color in the parent okay
27:07
so you can either look at this as
27:09
converting these two red nodes to black
27:12
in this black node to red or converting
27:15
these to red pointers to black and this
27:17
pointer to right alright so in this case
27:23
there are looks like three bits that
27:27
have to be changed
27:32
whereas in the original or native
27:35
representation mode there's a fair
27:37
amount of work involved
27:39
he started with two nodes you had to end
27:42
up with three so you have to make one
27:43
invocation of new to get that node and
27:46
then you've got to move data around and
27:49
pointers around it so again this
27:53
transformation is expected to take
27:55
considerably less time in the red/black
27:58
world as it does in the native two three
28:00
four world right the symmetric case
28:08
where the four node is the right child
28:10
of the two node works in a similar
28:12
fashion so we won't look at that picture
28:14
well let's go to the case where the four
28:18
node you are trying to move to is the
28:20
left child of a three node okay so
28:24
you're sitting at a three node and
28:25
you're moving to a phone ode now for
28:30
this case you actually have three
28:32
possibilities where your the phone
28:35
already moving to the left child it
28:36
could be the middle childhood could be
28:37
the right child as you might expect the
28:41
cases where it's the left child and the
28:42
right child has symmetric the middle
28:45
child may be different from whether
28:47
you're trying to move to the left or the
28:48
right
28:50
all right so sitting at a three node
28:55
moving to a four node to the left child
28:58
of the three node so again the strategy
29:02
was to split this four node up and then
29:05
move to one of the two nodes so you
29:09
start with this configuration you end up
29:11
with that the before configuration for
29:16
this isn't something you have any
29:21
control over you can only control the
29:23
after the before configuration this is a
29:26
three node and this three node could be
29:28
in any one of its two possible
29:31
configurations and whatever we do has to
29:34
work for both of those possibilities in
29:37
the previous case we said that we were
29:41
creating a three node which can have two
29:42
possible orientations
29:44
and so we have flexibility in deciding
29:46
which orientation we're creating okay
29:48
but here we are starting with this three
29:53
node and it could be in any one of its
29:55
two possible orientations so here's a
29:59
possibility for this three node okay so
30:04
this three node okay
30:06
might look like this okay y&z; why isn't
30:09
the root and then Z is the red child
30:12
okay
30:14
the other possibility for this three
30:17
node is that Z is the root and Y is
30:19
sitting out here and we need to have a
30:24
way to work with both of these before
30:27
configurations so let's look at this one
30:30
first okay right so if you're in this
30:34
configuration we need to then transform
30:38
it into the red black representation of
30:40
this configuration this thing here has a
30:43
unique red black representation because
30:45
there's no three node in it okay so the
30:49
after configuration whether you like it
30:51
or not has to look like this
30:56
okay you know here again we see that
31:00
structurally they're the same okay the
31:03
only difference is in the color of some
31:06
of the nodes and edges so if I perform a
31:12
color flip so in a color flip you change
31:15
the color of these nodes from red to
31:19
black and then the parent changes from
31:21
black to red okay so if I do a color
31:24
flip okay you're going to look like that
31:34
so if I do a color flip I can accomplish
31:39
that okay color flips either done on the
31:42
color of nodes if you have a node color
31:44
representation or on the color of edges
31:46
so these two red edges became black and
31:48
this black one became right all right so
31:53
this is again changing three bits
32:09
now this before configuration could look
32:13
like this in the red/black world okay
32:16
where Z was the root and then it had a
32:18
left child red node Y so this now
32:21
represents our three node from here so
32:27
this configuration also needs to be
32:30
transformed into that configuration so
32:35
at this time things don't look the same
32:36
and at this time you have to make some
32:40
pointer changes you don't have to create
32:43
any new nodes okay the number of nodes
32:45
is the same so no calls to new but you
32:50
do have to change pointers and colors
32:55
okay now to detect that you've got to do
32:58
all of this work will first perform what
33:01
is kind of the fundamental operation
33:03
here
33:03
the fundamental operation here is to do
33:06
a color flip so perform a color flip
33:10
okay whenever you're moving to a four
33:12
node you do a color flip okay so we do a
33:16
color flip so that will change these two
33:17
fellows to black and this one too red
33:19
okay so we have black and red okay let's
33:23
come back look let's look at this side
33:25
here so change the color here to black
33:27
change this one to red and then what you
33:29
see is you have two consecutive red
33:31
nodes okay that's when you know you have
33:35
a problem so whenever you're moving to a
33:38
four node you do a color flip and if the
33:41
color flip results in two consecutive
33:43
red nodes you have a problem okay so the
33:47
fellow whose color got changed from
33:49
black to red you check its parent and
33:51
see if that was already right if so you
33:55
have a problem you you classify the
34:01
nature of the problem okay so you have a
34:03
red node here you have a red node here
34:05
and this fellow here is the left child
34:07
of its parent okay so you look at the
34:11
two red nodes and you look at the parent
34:13
of the first red node and look at the
34:19
orientation of these edges of these sub
34:22
trees okay so
34:23
red node red node and then that's black
34:28
you've got from here you go to the left
34:30
child when you go to the left child so
34:31
this is an LL type problem so you
34:36
classify the two consecutive red nodes
34:38
as either LLL our our our our L and then
34:42
you perform the corresponding rotation
34:43
that was done for AVL trees okay so we
34:46
have an ll problem here so I'll end up
34:49
doing a clockwise rotation where Y will
34:52
become the root and Z will become its
34:54
right subtree to end up with this
34:57
configuration here okay
35:05
all right so moving to a four node do a
35:07
color flip a black node becomes red see
35:12
if that red node and its parent end up
35:16
giving violating the two red nodes in a
35:18
sequence problem okay if so classify the
35:21
nature of the violation and perform the
35:24
corresponding AVL tree rotation
35:39
alright 4-node is the middle child over
35:41
3-node again because we have this three
35:47
node here there are two possible before
35:50
configurations in the red/black world
35:54
one of these looks like this so we take
35:59
this three node and make Z the root and
36:01
then V becomes its left subtree the four
36:04
node has a unique representation so I
36:09
want to transform this into the red
36:12
black representation for this
36:13
configuration here this has a unique red
36:17
black representation because you only
36:18
have four nodes and two nodes involved
36:22
so I want to transform it into this
36:26
structure here alright so again the
36:31
strategy is you're sitting at a three
36:33
node you're moving to a four node do a
36:35
color flip okay
36:37
in a color flip these two nodes will
36:39
become black this node will become red
36:43
so now you have two red nodes in a
36:46
sequence so we know we have a violation
36:49
and at this time a rotation has to be
36:52
performed so to perform the rotation we
37:01
classify the nature of the problem this
37:04
is a from here you're moving to the left
37:06
and then to the right so you have an LR
37:09
type problem so we're going to perform
37:11
an lr rotation in the lr rotation X
37:14
moves up to the root okay and that's
37:18
what we need over here
37:56
okay so another case is you're sitting
38:03
at a four node and you're moving to the
38:05
three node we have to look at the other
38:07
orientation of this three node okay so
38:12
the other orientation for this three
38:14
node has V as the root and Z as it's
38:16
right child
38:26
and the after configuration still has to
38:30
look like that that doesn't change
38:32
that's unique so once again sitting at a
38:36
3-node moving to a four you detect that
38:39
you're moving to a four you perform a
38:41
color flip so when you do a color flip
38:43
these two nodes become black this
38:45
becomes red and you find that you have
38:47
two red nodes in a sequence so you
38:51
classify the nature of this problem
38:53
right left so this is an RL type problem
38:57
so I'll do an RL rotation and an RL
39:00
rotation moves X to become the root of
39:03
the subtree and then the other fellows
39:05
are placed wherever they fit okay so
39:08
you'll end up with that configuration
39:18
okay so once you've made this change
39:20
then you can move further down the tree
39:22
as you move further down the tree you
39:25
may encounter another phone ode and then
39:27
you may have to make another rotation or
39:29
a color flip okay so as you go down
39:35
every time we encounter a phone ode you
39:39
first do a color flip if it causes two
39:41
red nodes in a sequence you do a
39:43
rotation and then you continue to move
39:45
down every four node you encounter is a
39:48
place where you may have to do a
39:50
rotation and since the number of four
39:54
nodes is logarithmic in the number of
39:56
elements you could end up performing
39:58
logarithmic rotations if you use the
40:00
strategy okay the final case is you're
40:10
moving to a four node which is the right
40:13
child / three node so that's similar to
40:17
left child and if you look back at left
40:21
child depending upon the orientation of
40:24
the three node you either have to just
40:26
do a color flip in that case we have to
40:28
do an ll rotation but in this case it
40:31
would be an RR rotation so actually all
40:39
of the AVL rotation types get used here
40:44
but the efficiency comes from often
40:52
having to just do color changes which
40:54
are just changing bits then you aren't
40:56
doing any rotations it also comes from
40:59
not having to create new nodes like you
41:02
would have to do in a in in the native
41:05
red black - 3 sorry in the native 2 3 4
41:09
representation so you anticipate getting
41:15
a fair amount of runtime efficiency
41:19
using a red black representation versus
41:22
the native 2 3 4 representation also as
41:26
indicator as far as space goes you
41:28
expect to see space savings
41:31
two nodes and three nodes take less
41:36
space here than in the native two three
41:38
four but a two three four node actually
41:42
takes more space in the red/black world
41:43
because you've got all these bits
41:45
representing colors out there plus with
41:51
with the user three nodes you got six
41:52
pointer fields okay so four nodes end up
41:57
taking more space but you say when the
41:58
two and three nodes and if he had a
42:01
large number of two and threes you would
42:02
expect an overall saving otherwise you'd
42:04
expect a loss you know we've seen now if
42:13
you mimic the top-down approach we don't
42:16
get the order one rotation each time we
42:20
encounter a four node there's the
42:23
possibility of a rotation being
42:24
performed and since the number of four
42:27
nodes on the path from a root towards an
42:30
external node could be logarithmic you
42:32
could end up doing log n rotations okay
42:36
so in our next lecture we're going to
42:40
take a look at a bottom-up version for
42:42
insertion and there we will see that at
42:46
most one rotation can be done
42:51
now we could do a top-down delete by
42:57
simply taking a look at how we were
42:58
doing top-down deletes in two three four
43:00
trees in the last lecture just mimic all
43:04
of that and it would carry over here and
43:06
you would have the same things you
43:13
perform color flips and then if you have
43:16
two red nodes in a sequence you perform
43:18
a rotation and again there you could end
43:22
up doing logarithmic number of rotations
43:30
okay so as I said earlier we expect some
43:35
memory saving we expect some time saving
43:42
now in our next lecture we're going to
43:49
take a look at the bottom-up insert and
43:52
delete and that's when we'll get the
43:55
version of red-black trees that are most
43:57
useful where you have only one at most
44:01
one rotation for insert or delete all
44:07
right any questions okay