Transcript


00:08
okay all right we're going to continue
00:12
our discussion of red-black trees today
00:15
in our last lecture we saw the principal
00:19
operations that are done on red-black
00:21
trees or dictionaries and today we want
00:24
to look at how to perform two additional
00:26
operations namely joining two red-black
00:30
trees into one and splitting a red-black
00:33
tree okay but these two operations find
00:37
application in several places one that I
00:43
could mention right now is in data
00:45
structures for for dynamic packet
00:50
routing tables in the internet so one of
00:55
the first log n structures proposed out
00:57
there to handle packet forwarding and
01:00
insertion and deletion of new and old
01:03
rules involved red-black trees and there
01:06
was extensive use of joins and splits
01:09
but there's certainly many other
01:11
applications and we mentioned another
01:13
one when we take a look at B trees later
01:15
okay all right so the objective is to
01:19
end up with algorithms to split and join
01:25
red-black trees in logarithmic time and
01:29
for that purpose we will need to
01:31
introduce a new term on red-black trees
01:36
okay so the new term is rank so with
01:40
each node in a red-black tree I will
01:42
associate a rank so the rank of the node
01:45
X is the number of black pointers on the
01:48
path from X to an external node and if
01:51
you recall the correlation between
01:54
pointer colors and node colors you will
01:57
see that this is really the same as the
01:59
number of black nodes from X to an
02:01
external node but in this count we don't
02:04
count the node X whether it's black or
02:06
red okay so
02:10
the number of black nodes excluding X
02:12
from X to an external node that's the
02:14
same as number of black pointers if
02:17
you're sitting at an external node okay
02:20
then the number of black pointers needed
02:23
to go from an external node to an
02:25
external node is zero similarly the
02:28
number of black nodes on the path from
02:30
this external node the external node
02:31
itself is colored X is colored black but
02:34
we can't include that node in the count
02:36
okay so there are no black nodes other
02:40
than itself on the path from an external
02:42
node okay all right so so can example
02:46
out here okay so here's a red black tree
02:49
okay all of the external nodes have a
02:52
rank that is zero and if I look at this
02:57
node here the number of black pointers
02:59
on a path from here to an external node
03:03
it doesn't matter which external node
03:04
you go to number of black pointers is
03:06
always the same given the definition
03:09
that we had last time for a red black
03:10
tree okay so there's one black pointer
03:13
so it's rank is one same thing here
03:16
there's one black pointer if you come
03:21
out here number of black pointers from
03:24
here to an external node is one
03:26
regardless of which of these four
03:28
external nodes you go to also the number
03:30
of black nodes on the path from here to
03:33
an external node excluding itself okay
03:35
you go through a red node and the black
03:37
nodes it's only one okay all right the
03:41
rank out there is one number of black
03:45
pointers is one if you come over there
03:48
the rank of this node is one okay rank
03:53
of that node is one there are three
03:55
black pointers and it's three external
03:57
nodes in the subtree regardless of which
04:00
one you go to you go through exactly one
04:02
black pointer here there are two
04:08
external nodes in the subtree you go
04:10
through one black pointer over here two
04:14
external nodes in the subtree go through
04:15
one black pointer okay from here okay
04:19
you got one two three four five external
04:22
nodes
04:23
independent of which one you go to
04:24
you'll have to go through two black
04:26
pointers to get to it okay currently had
04:30
to go through two black notes excluding
04:33
the origin at rank of this node is to
04:40
number of black pointers is to to an
04:42
external node over there their rank is 2
04:45
and then for the root the rank is 3 all
04:52
right so the rank of a node is the
04:53
number of black pointers from that node
04:55
to any external node in its subtree
04:57
that's the same as the number of black
05:00
pointers priority exclude the node you
05:02
start at in the count same as number of
05:05
black nodes priority exclude the node
05:07
you started or any questions about rank
05:16
all right so all right the rank is zero
05:20
for an external node ok if you look at
05:29
the parent of an external node ok it's
05:32
rank will be one because the pointer
05:36
that goes into an external node is black
05:40
if you look at a node X and if it has a
05:44
parent ok then the rank of X will be
05:51
less than equal to the rank of its
05:52
parent ok so as you go up the tree ranks
05:55
go up but when you go from a node to its
05:59
parent the rank may go up by at most one
06:02
ok so the rank of the parent is at least
06:07
as big as the rank of the child and
06:10
isn't more than one more than the rank
06:13
of the child
06:17
if you have a grandparent when you go
06:21
from one node to the grandparent the
06:22
rank has to change okay if the rank
06:28
doesn't change then you must have two
06:29
red pointers in a sequence or two red
06:33
nodes in a sequence okay so since when
06:36
you go from a node to the grandparent
06:38
you have to go through at least one
06:42
black pointer maybe two the rank has to
06:46
increase either by one or by two now you
06:56
can prove that any binary tree to which
07:04
you can assign ranks to satisfy the
07:07
properties that are just listed is a red
07:10
black tree so if you forget about colors
07:14
if you can assign integer ranks to the
07:16
nodes so that the rank of an external
07:20
node is zero the rank of the parent of
07:23
an external node is one as you go up
07:26
ranks increase when you go from a node
07:29
to its grandparent the rank has to go up
07:31
when you go from a node to a parent the
07:34
rank may or may not go up but may go up
07:36
by at most one okay so if you satisfy
07:38
those properties then you have to have a
07:41
red black tree okay and actually once
07:45
you have placed ranks on nodes according
07:47
to those properties you can figure out
07:50
the color of each node okay you so the
07:54
rank doesn't change that pointer has to
07:57
be red if the rank changes that pointer
07:59
is black
08:05
okay alright so if you look at a pointer
08:09
from a parent to a child it's a red
08:12
pointer if the rank doesn't change it's
08:16
a black pointer if the rank changes and
08:18
if the rank changes can only change by
08:20
one okay and then if you know the color
08:27
of the edges you can figure out the
08:28
color of the nodes for the route you
08:31
have this constraint the route is always
08:33
black alright so using ranks is
08:40
equivalent to using colors now if you
08:48
know the rank of the root of the tree
08:51
and you know the color of the nodes the
08:52
color of the edges then starting from
08:55
the root as you go down you can compute
08:56
the rank of every node so you don't
08:59
really have to store the rank of every
09:01
node you just store the rank of the tree
09:04
altogether and then store the colors and
09:06
then as you go down you can compute
09:08
everybody's rank if you have an
09:10
algorithm that requires knowledge of
09:11
rank and that's really what we'll do we
09:16
store ranks with the root and then
09:18
colors on the nodes or colors on the
09:20
edges right using the rank definition
09:29
one can prove the same bounds we had the
09:30
last time that the height of a red black
09:34
tree lies between log n plus 1 and 2
09:37
times log n plus 1 we know that the
09:44
height is going to be at most 2 times
09:46
the rank okay every time you go said
09:51
downwards or you go upwards it's only
09:54
when you go to the from a node to its
09:56
parent the rank may not change but once
09:58
you get to the grandparent the rank has
09:59
to change so the worst that can happen
10:02
to you is that the height is 2 times the
10:05
rank of course the height can also be
10:09
equal to the rank so somewhere between
10:10
drank in 2 times right
10:17
you know since the rank gives you the
10:23
number of black pointers it tells you
10:27
that you can truly have an external node
10:29
at the first so many levels if you had a
10:35
if you had an external node at say level
10:40
two okay
10:41
then you only need one black pointer to
10:43
get to that external node if you had an
10:47
external node at level three you only
10:49
need two black pointers to get there if
10:50
you had an external node at level six
10:52
you only need six black pointers but
10:54
since the rank is the number of black
10:55
pointers needed from the root to the
10:57
external node and all of them are
10:59
equidistant you can't have an external
11:02
node at levels one two up to rank of
11:04
root you can have an external node one
11:08
level after that okay so those levels
11:13
are populated by internal nodes so if
11:15
you count only the number of nodes on
11:17
those levels you get a lower bound on
11:19
the number of nodes okay so we count
11:23
only the nodes and those levels that
11:25
works out to to raise to rank minus one
11:30
okay so the number of internal nodes is
11:33
at least 2 raised to rank minus one
11:35
alternatively the rank is no more than
11:37
log of n plus one and being the number
11:40
of internal nodes and then coupling this
11:48
with this thing here you get that the
11:50
height is at most two times log of n
11:53
plus one okay so you get an alternative
11:57
proof that the height of a red black
12:00
tree is at most two times log of the
12:03
number of internal nodes
12:12
or any questions about that proof
12:20
alright so one can derive the properties
12:24
of red-black trees without resorting to
12:26
colors by simply having ranks associated
12:30
with every node and you can do
12:31
everything based on ranks and you can
12:34
infer the colors from the ranks yeah
12:39
it's cheaper to store colors than ranks
12:42
as colors you only got red and black so
12:45
you need two bits if you're trying to
12:48
store the colors of pointers so left
12:53
pointer can be stored color can be
12:55
stored with one bit
12:56
zero being red one big blank and soonly
12:59
the right child pointer color can be
13:01
stored with one but or if you're storing
13:03
node colors you only need one bit to
13:05
store the color of that node but ranks
13:08
can range up to log events you need more
13:11
bits to store ranks with nodes as
13:13
cheaper Deusto colors than ranks but we
13:15
just throw the rank of the route instead
13:20
of ranks of all of the nodes all right
13:24
so let's take a look at the two
13:25
operations that were of interest today
13:27
one is joined the other is split the
13:31
joins are really constrained in terms of
13:35
the input that is permissible to the
13:37
joint okay so the joint operation takes
13:40
three inputs s m and B s is a dictionary
13:49
where the keys are what we'll call small
13:52
keys B is a dictionary that has large
13:58
keys and what's small and large mean is
14:01
really with what is the relationship to
14:05
this additional pair that's going to be
14:08
in the resultant dictionary M ok so all
14:12
of the keys and s are smaller than the
14:15
key of M all of the keys and B are
14:19
bigger than the key
14:22
okay so that's what we mean by small and
14:25
big so it's not that you have to
14:28
arbitrary dictionaries that are being
14:29
joined one all of the keys in one
14:32
dictionary s are smaller than all of the
14:34
keys in the other dictionary B alright
14:40
so this would be a three-way join we're
14:41
given three things which you could do a
14:43
two-way joint where you're not given an
14:45
M okay and that's similar to a three-way
14:48
joint
14:53
all right the result of the join is a
14:55
single dictionary that contains
14:57
everybody in s everybody in B and the
15:00
additional there M the join is a
15:05
destructive operation in that after you
15:07
have done the join s and B do not exist
15:10
as independent dictionaries okay so you
15:15
can alter them any way you like while
15:17
you are creating your new dictionary
15:29
all right so let's first take a look at
15:33
how you could do a join if you didn't
15:35
really care about red black trees if all
15:38
you had were binary search trees and he
15:40
said well do a three-way join on binary
15:43
search trees not necessarily red black
15:48
well in that case the join is pretty
15:51
simple you just get a new node stick the
15:55
new pair into it make s the left subtree
15:58
of that new node and be the right
16:00
subtree of that new node and you get a
16:02
new binary search tree that contains
16:04
both the dictionaries as well as the
16:06
pair yeah so a join in an unbalanced
16:13
binary search tree is a simple operation
16:16
takes order one time all right this of
16:24
course will not work if you're dealing
16:25
with red black trees because maybe down
16:29
here the number of black pointers and
16:32
paths to an external node of four and
16:34
maybe here it's 40 so once you do this
16:37
even if you make this a black node and a
16:41
black pointer okay so the root will be
16:43
black so if you've got a black pointer
16:44
here well then you have five pointers on
16:49
route to external node paths there and
16:51
41 out here which doesn't satisfy the
16:54
red black property so this simple thing
16:57
doesn't work for red black tree joining
17:04
all right so when you're joining red
17:07
black trees the joint splits into three
17:11
different cases depending upon the
17:12
relationship between the rank of the
17:14
small tree in the big tree when the
17:17
ranks of the two trees are the same then
17:19
of course the simple thing works okay so
17:23
for example if the rank here had been
17:24
four and there it was four well then if
17:28
I create a new node M the number of
17:31
black pointers from here to an external
17:33
node going this way will be five and
17:35
will be five that way too
17:37
so the rank of that node is five in your
17:38
okay so when the rank of s and B are the
17:46
same its order one you do the same thing
17:49
that you were done for in balanced
17:50
binary search trees second case is when
17:56
the rank of the small tree is more than
17:57
that of the big tree okay so in that
18:02
case what we'll do is we'll start at the
18:04
root of the small tree and make right
18:10
child moves until I reach a node whose
18:13
rank is the same as that of the rank of
18:16
the small of the big tree we know that
18:21
as we go downwards at worst every two
18:25
moves you make the rank will drop by one
18:29
you never see big drops and rank so if
18:32
you go from a node to its child the rank
18:34
may be the same or it may go down by one
18:36
was not going to go down by six or ten
18:38
or something okay so if you start with
18:40
somebody here whose rank is forty at
18:42
some point you reach someone well after
18:46
at most two moves you read somebody's
18:47
rank is thirty nine and then after at
18:49
most two moves somebody's rank is 38 37
18:51
36 35 and so on okay so we make write
18:56
child moves until you reach the first
18:59
node X whose rank is the same as that of
19:03
B and we're guaranteed that we're going
19:06
to reach such a node
19:12
the pointer into this node will have to
19:16
be black okay because if the rank of B
19:22
is let's say 10 and the rank out here is
19:25
15 well then this nodes rank is 10
19:28
that's where you stop
19:29
which means this nodes rank must have
19:31
been 11 okay if this nodes rank was 10
19:35
we'd stop out here okay we're going to
19:36
stop at the first node whose rank is 10
19:38
so this nodes rank is 10 this knows rank
19:41
has to be 11 so you go to have a black
19:42
pointer here
19:43
because you've got one more black
19:44
pointer from here to an external node
19:46
then from that okay so you have X has to
19:49
be a black node okay alright so we
19:53
stopped at the first node whose rank
19:55
equals that of B that has to be a black
19:57
node call that node X okay that node is
20:01
going to have a parent it can't be the
20:04
root if it was the root then we would be
20:07
in the previous case okay so this node
20:10
has a parent call that px the color of
20:14
the parent is not known okay the color
20:18
of the parent could be red it could be a
20:20
red node it could be a black node okay
20:25
so that's all you got this broken
20:27
pointer here indicating if we don't know
20:29
the color of that pointer and I don't
20:31
know the color of that node the time
20:37
required to move from here to there okay
20:41
the number of moves you make is at most
20:44
two times the rank difference for every
20:47
two moves the rank has to drop by at
20:49
least one okay so the rank difference is
20:51
five after ten moves you got to reach X
20:56
so it takes you time which is two times
20:58
the rank difference at most to get here
21:01
once we get here I will then do my
21:05
construction into this point okay I will
21:09
insert that middle pair as well as the
21:12
big tree I'll create this configuration
21:16
here so get a new node into which I
21:19
stick the middle pair down here I've got
21:22
this entire subtree
21:24
okay so this entire subtree becomes the
21:26
left subtree of em and the big tree
21:30
becomes the right subtree of em all
21:37
right so the first thing to note with
21:39
that construction is that you have a
21:42
properly configured binary search tree M
21:52
is bigger than the key there in fact M
21:56
is bigger than everything in the whole
21:58
tree okay
21:59
so M is bigger than that fellow
22:01
everybody down here is smaller than M in
22:04
fact everybody in that whole tree is
22:05
smaller than M everybody down here is
22:08
bigger than M okay all right so you've
22:11
got a properly structured binary search
22:14
tree of course it may not be right back
22:17
all right so first we verify that we've
22:19
got a binary search tree
22:20
okay this node comes in as a red node as
22:28
a result of that the number of black
22:32
pointers on paths from the root to
22:33
external nodes has not changed okay so
22:39
previously to get to the external nodes
22:43
in a and B okay down here okay
22:46
we came to px we followed a black
22:49
pointer got to X okay now you come to P
22:52
X you follow a red pointer and then a
22:54
black to get to X okay so it's the same
22:57
as before and then to get to the
23:00
external nodes here okay the number of
23:03
black pointers is the same as on this
23:06
side because the rank of X is the same
23:08
as rank of B so all route to external
23:12
node paths have the same number of black
23:14
nodes same number of black pointers
23:20
the problem that we may have is we don't
23:23
know the color of this fellow okay if
23:25
this fellow is black you're okay if this
23:28
fellow is red
23:29
you have to read pointers in a sequence
23:31
and so you violate the red black
23:33
property all right so if it's a black
23:41
node you're finished if it's a red node
23:44
you have two consecutive red nodes or
23:46
two consecutive red pointers and we need
23:49
to rectify that and we saw how to
23:51
rectify that when we did an insert so
23:56
when you have two of these fellows you
23:58
have that's P P X GPU classify the type
24:02
you either do a color flip or a rotation
24:04
and you okay color flips require you to
24:08
move up two levels a rotation terminates
24:11
okay so we perform exactly the same task
24:18
that were being performed during an
24:20
insert to fix the two red pointer in a
24:22
sequence problem okay going back up the
24:25
tree and the time required okay since
24:33
the distance you moved down is two times
24:36
the rank difference at most the distance
24:38
you have to move back up is the same at
24:40
most okay and it takes the only one
24:43
intuitive time for every two levels you
24:45
move up okay so the total time to do the
24:48
join is linear in the rank difference
24:56
and that difference can at most be log
25:01
of the total number of elements so you
25:04
can do the join in logarithmic time
25:11
okay aren't any questions about how a
25:14
joint works
25:24
all right so let's turn our attention
25:26
well I guess we have one other case this
25:29
works the same as the other case okay so
25:33
if the rank of the small tree is less
25:35
than that of the big tree well then on
25:37
the big tree you start by making left
25:39
child moves until you reach the first
25:42
node X whose rank equals that of s and
25:44
then you perform the same operation out
25:47
there
25:54
all right so let's turn to split so the
25:58
split operation you're given a key and
26:00
then based on that you need to split the
26:04
tree into three parts okay so it's kind
26:07
of the inverse of the joint so we'll
26:12
split the tree into a dictionary of
26:14
pairs whose key is smaller than the
26:16
split key a dictionary of pairs with key
26:21
bigger than the split key and then the
26:24
middle pair whose key equals the split
26:27
key of course the dictionary may not
26:30
contain a pair with this key in which
26:33
case M would be null or any questions
26:44
are what we want to do we just want to
26:47
reverse what took place in a joint
26:51
though one exception is that this split
26:55
key may not have a corresponding pair
27:05
all right first let's see how we would
27:08
do a split in an unbalanced binary
27:11
search tree all right suppose this is an
27:17
unbalanced binary search tree and these
27:22
locust letters represent sub trees and
27:25
the caps represent pairs all right so
27:31
I'm going to do a split and the split
27:33
key corresponds to the key in this node
27:35
so to do the split I'm going to traverse
27:38
a path from here my split key is bigger
27:41
than this I'll come here split key
27:42
smaller than this I come here it's
27:44
bigger than this smaller than that
27:46
bigger than e I come here and I find a
27:48
match okay now what I'll do is on their
27:51
way down while I'm trying to find the
27:53
location of the split key and if the
27:55
split key is not there I'll fall off the
27:57
tree somewhere okay so follow a path
27:58
dictated by the split key on the way
28:01
down
28:01
I will partition the tree into the small
28:04
and big trees
28:07
okay so for that purpose I'll start with
28:09
two header nodes one for the small tree
28:12
and one for the big tree okay all right
28:17
so when you come from here to here okay
28:21
we know that the split key is bigger
28:23
than this key and so it's bigger than
28:26
everybody down here okay so a and this
28:30
subtree little a belong in the small
28:32
tree so I will set up a pointer here to
28:36
this node okay conceptually that's what
28:39
I'm doing okay so set up a pointer in
28:44
the head a node make the right child at
28:45
the pointer a and then this whole thing
28:47
comes for free all right so now I'm at
28:52
this node okay I compare my split key
28:55
with the key out here my split key is
28:57
bigger than my split key smaller than
29:00
that that's what I'm going to come this
29:01
way so this guy is bigger than the split
29:03
key and everybody here is bigger than
29:05
the split key so this whole thing
29:07
belongs in the big tree and to affect
29:11
that I'll make the left child of the
29:12
head a node this node here okay so
29:15
effectively I'm doing this all right
29:20
then I'm here my split key is bigger
29:22
than see Sam come here so C is smaller
29:27
than the split key and everybody here is
29:28
smaller so this whole thing belongs in
29:30
the small tree okay but everything here
29:33
is also bigger than a because of the
29:36
path that I took so this whole stuff can
29:39
be made the right subtree of a so I
29:41
changed the right child pointer here
29:43
okay so I do that all right now I'm here
29:49
and I'm going to move this side so my
29:51
split key is smaller than D so D belongs
29:55
in the big tree together with this right
29:56
subtree but the stuff in here is smaller
30:01
than B because of the path that I took
30:05
this is in the left subtree of B so
30:07
attached this now as the left child of B
30:12
so I keep track of the last node that
30:17
was attached and if I find anything else
30:19
it'll become the right child here
30:21
if I find anything in this street will
30:22
become the left child over there all
30:26
right so now I look at this guy my split
30:28
key is bigger than that so this belongs
30:30
in the small tree so he becomes the
30:34
right child of C but then I reach this
30:39
node I get a match so it's left subtree
30:43
is smaller so it's left subtree belongs
30:46
in the small tree its right subtree is
30:49
bigger its right subtree gets attached
30:51
into the big tree and then I throw away
30:59
the two header nodes and I've got my
31:02
small tree my big tree and the element
31:10
all right so if you didn't care about
31:12
balance we could split a binary search
31:14
tree in time proportional to the height
31:16
of that search tree we just follow a
31:18
path dictated by the split key and move
31:20
sub trees into s and B as you go down if
31:26
you did this on a red-black tree you may
31:29
not end up with the red black tree you
31:33
can check that out on your own because
31:35
the sub trees that you're attaching
31:37
don't preserve the rank property
31:47
all right so something you can verify at
31:52
home is that this strategy doesn't work
31:54
for red black trees so we need a
31:58
different strategy and the strategy that
32:01
we're going to adopt is really going to
32:03
be a two pass strategy in the first pass
32:07
we'll trace the path to the node that
32:09
has the split key if such a node exists
32:13
without partitioning the tree on the
32:16
second pass we will back up the tree
32:18
going back to the root and at that time
32:21
we will split the tree when we split the
32:27
tree we will need to attach parts of
32:30
trees to a currently built small tree or
32:34
big tree in the case of one balanced
32:39
search trees we did that simply by
32:40
changing one child pointer here the
32:44
attachment is really going to be done by
32:46
the use of the join operator that we
32:47
just looked at so the joint will ensure
32:50
that you can take two red black trees of
32:52
any rank and create a new red black tree
33:02
okay so let's look at the example right
33:05
so in the first pass will you start from
33:08
here travel down and come there okay I'm
33:13
not going to split the tree
33:24
all right so once I have reached this
33:26
fellow the left sub-tree is known to be
33:30
a red black tree and the right subtree
33:31
is known to be a red black tree these
33:33
will be my initial small and big trees
33:40
so small begins with F in that with G
33:44
and so it's known to be a red black tree
33:46
and every time I add things to s and B I
33:50
will show that the result is a red black
33:52
tree and so when I finish s and B will
33:54
be guaranteed to be red black trees now
34:05
at times the key that you're searching
34:07
for will not be presence you will fall
34:09
off somewhere okay
34:10
so at that time you can start with an
34:13
MTS and an MT B and then retrace your
34:16
path back up the tree so if M is present
34:24
then we'll start with F and G like that
34:28
or s and B like that if M is not present
34:30
we fall off here then we can start with
34:32
an MTS and an MTB and then go back up
34:37
all right
34:38
so I retrace the path I come to the node
34:43
II okay I've come here from the right
34:48
subtree so I know that E is smaller than
34:52
the split key and everybody here is
34:55
smaller than the split key so this stuff
34:57
belongs in the small tree okay so I'm
35:03
going to do a three-way join of this
35:05
stuff with the small tree okay now
35:16
see there's no way to go back from here
35:18
go back yeah okay so if you look at the
35:30
setup we're coming from the right
35:32
sub-tree okay so when you're coming from
35:35
the right sub-tree everything that
35:37
you've seen so far
35:38
okay it's going to be bigger than this
35:41
guy okay doesn't matter where it got
35:44
placed everything you've seen so far
35:46
because we're starting from the bottom
35:48
it's going to be bigger than this guy
35:50
okay so when you do the three-way join
35:52
we've got e everybody here is smaller
35:57
than this middle key and everybody in s
36:01
is bigger than that so that's a valid
36:03
configuration for our three-way joint
36:05
okay so when we're here okay we're going
36:10
to do a join of this fellow everybody
36:13
here is less than this middle key and
36:15
everybody in s so far is bigger than
36:18
that okay so that's a valid joint I run
36:22
my joint operation and construct a new s
36:29
alright so now I'm finished with
36:31
everything that was down here I'm going
36:33
to back up here since I'm coming from
36:35
the left okay since I'm coming from the
36:39
left the split key is smaller than D so
36:43
D and everybody here belongs in the big
36:46
tree since I'm coming from the left
36:50
everybody I've seen here okay it's
36:53
smaller than that guy in particular
36:57
everybody you've accumulated in B so far
36:59
is smaller than this guy okay so when I
37:03
do the join with B I know that the
37:05
current B has think smaller than thee
37:07
and so I can use my three-way join which
37:12
is small items the middle item big items
37:35
all right so then from here I I'm going
37:38
to come out here you're coming from the
37:40
right sub-tree so everything you've seen
37:42
so far is bigger than that also the
37:49
split key is bigger than that so this
37:51
fellow belongs in the small tree so does
37:53
that belong in the small tree I do a
37:55
join with the small tree everybody so
38:01
far in s is bigger than Big C so so the
38:08
joint that we looked at a little while
38:09
ago works all right then we're going to
38:12
back up to B and you're coming from the
38:15
left so everybody you've seen so far is
38:18
smaller than that guy the split key is
38:21
smaller okay so B and it's right
38:26
sub-tree going to the big tree so we'll
38:28
do a join so these items are known to be
38:35
smaller than the item in B and everybody
38:39
in little B is bigger than the item in
38:41
that root note all right then we're
38:50
going to back up over there to do a join
38:52
okay so again you're coming from the
38:55
right subtree so this guy belongs in the
38:57
small tree so does that guy belong the
39:00
small tree everything you've currently
39:02
put into the small tree is bigger than
39:04
this guy
39:21
all right so when you're done you're
39:24
small and big trees are guaranteed to be
39:26
red black trees are questions about how
39:33
that split works so it's a two pass
39:39
split top-to-bottom is used to locate
39:41
the split element and then bottom-to-top
39:44
to actually create the split the small
39:47
in big trees all right if you analyze
39:52
the complexity of this cur they're large
39:54
number of joints taking place in fact
39:57
there could be log n joints taking place
39:59
because you're starting the height of
40:01
this thing could be up to two log n so
40:02
you're starting somewhere down here and
40:04
each time you move back up one level you
40:06
do a join so potentially you could be
40:08
doing two log n joints yeah one could
40:13
say that a joint takes log n time you do
40:15
to log in of those two that's log square
40:17
n but if you do a more careful analysis
40:21
which says the complexity of a join is
40:24
the difference in the ranks of the two
40:25
trees that you're joining okay and then
40:29
what happens is if you take the rank
40:32
difference here plus the rank difference
40:33
there plus the rank difference here and
40:35
similarly do those ones separately for
40:38
their rank differences you'll find that
40:40
most of the ranks cancel out and the
40:42
only thing that remains is the rank of
40:45
the final result and the rank where you
40:47
started and that rank difference is
40:50
logarithmic okay so if you work with the
40:56
complexity as rank difference then you
41:00
add up the complexities of the different
41:02
things and you'll see that you end up
41:06
with something like a telescoping sum
41:08
and the only thing that remains is the
41:09
final rank and the initial rank and
41:11
that's that difference is at most log n
41:14
okay so the complexity of the split is
41:18
actually log N and we're not going to go
41:22
through the analysis here but you can
41:24
read it from the book they've done the
41:27
analysis over there
41:32
all right any questions
41:38
okay so we'll stop here