Transcript


00:20
okay in our last lecture we took a look
00:25
at two three trees and we saw that two
00:29
three trees had a nice height property
00:31
compared to AVL trees was still
00:33
logarithmic but the worst case height
00:36
over two three three corresponding to
00:38
the best case height of an AVL tree now
00:43
two three trees still have some
00:46
deficiencies that we want to address so
00:49
let me start by talking about some of
00:52
these and then what we will do is after
00:58
we look at these deficiencies we will
01:01
move in a seemingly wrong direction
01:03
by looking at two three four trees which
01:06
will have even greater deficiencies but
01:09
then we will see that two three four
01:11
trees can be easily mapped into binary
01:14
trees which will overcome some of these
01:16
problems okay so the problems with two
01:23
three trees first of course is in terms
01:25
of the amount of space wasted we would
01:29
typically implement these using nodes
01:31
large enough to represent three nodes
01:34
and in the worst case all nodes that get
01:37
used as two nodes so you have a couple
01:41
of fields in each node that are not in
01:43
use okay another problem even though the
01:49
height is small as a result of that the
01:52
number of cache misses could be expected
01:54
to be small smaller than if you were
01:57
using an AVL tree the work that you do
01:59
for a node is potentially larger because
02:03
when you insert for example you have to
02:05
shift things from the say leftmost
02:08
fields if you're using it as a two node
02:10
you're using these three fields and if
02:12
you want to change the parent pair one
02:14
you end up having to shift a whole bunch
02:16
of things towards the right when you
02:17
transform this into a three node
02:19
similarly in a remove you may be
02:22
changing three nodes to two nodes and so
02:24
on okay so the overhead per node is
02:29
larger here than in an AVL tree
02:32
and therefore unless the cache miss
02:35
advantage is sufficiently great this
02:37
could end up taking more time okay
02:42
another deficiency which is also a
02:46
deficiency with respect to AVL trees
02:49
when you perform inserts and deletes the
02:53
number of nodes that get split say in an
02:57
insert okay oh you end up splitting
03:01
three nodes into which you add a new key
03:03
and these splits can go all the way up
03:05
from the bottom from a leaf all the way
03:07
up to the top of the tree okay similarly
03:10
the number of nodes from which you do
03:12
Barros in a remove will you borrow from
03:16
a sibling or the number of combines that
03:19
you might do not remove these could all
03:21
be order of height which is order of log
03:23
n now in the case of a simple
03:29
application of two three trees and red
03:34
black trees this isn't a problem because
03:36
each of these splits borrows and
03:38
combines takes order one time similarly
03:41
if you look at an AVL tree when you do a
03:44
delete or remove you have to perform
03:47
order of log n rotations whereas there's
03:50
only order one rotation in an insert
03:53
okay so a problem with AVL trees is log
03:56
end rotations in a delete a problem here
03:59
is log n splits borers and combines
04:02
during inserts and deletes and though
04:04
this is not a problem with the simple
04:07
application we're seeing at this point
04:09
this becomes a problem when you go into
04:12
embedded structures where for example in
04:16
a binary search tree you may build a new
04:20
structure called a binary search tree on
04:22
top of a binary search tree which would
04:25
mean that inside every node you have a
04:27
binary search tree okay so you have a
04:29
binary search tree and in each node
04:31
you're keeping a binary search tree and
04:33
then when you do inserts and deletes
04:35
since the content of a node isn't order
04:38
one the amount of work needed for the
04:40
rotation ends up being log of the number
04:43
of items stored in a node
04:46
if you're doing log and rotations then
04:49
each rotation no longer costs the order
04:51
one because each node has order n
04:53
elements an order log n height of its
04:56
own and so the rotations end up costing
04:59
you log n per rotation giving you log
05:01
square n okay and the same thing happens
05:05
here if inside each of these nodes you
05:08
aren't just keeping simple elements but
05:10
each element happens to be say a two
05:11
three tree in its own right and then
05:13
when you start splitting and things the
05:15
cost becomes high so what we'd really
05:20
like to have is we'd like to have a
05:22
balanced tree structure where the number
05:25
of rotations or splits and combines is
05:28
order of one and the AVL tree kinda
05:33
comes halfway there because the insert
05:35
has only order one rotation but the
05:37
delete has order log n so it doesn't
05:39
satisfy the needs for embedded
05:41
structures structure inside structure
05:43
that gets used in certain applications
05:46
okay
05:47
and we'll see one example of that later
05:50
when we look at priority search trees
05:51
where we will build a well it'll
05:55
simultaneously represent two data
05:57
structures okay so we don't like the
06:01
fact that its guard log n splits borrows
06:03
and combines okay alright so to overcome
06:06
some of these problems the problem of
06:09
wasted space and having logarithmic
06:11
operations which in more complex
06:13
situations cannot be done in order one
06:16
time each we would first extend this to
06:20
a 2 3 4 3 and that extension will
06:24
actually only make this problem worse
06:26
there'll be even more space wasted and
06:27
more overhead and moving things around
06:28
and we'll still be log n splits borrows
06:31
and combines but then we will see in our
06:34
next lecture the two three four trees
06:36
can be easily represented as binary
06:38
trees which we'll call red black trees
06:41
and red black trees or two three four
06:45
trees in the red black representation
06:47
can be managed so that the number of
06:51
rotations is order one for operation
06:54
okay okay so
06:57
so first may be a step in the wrong
07:00
direction oops
07:06
all right these not works okay all right
07:19
so two three four three is a fairly
07:21
natural extension of a two three tree
07:23
we basically add one more category of
07:26
permissible node you can now have a four
07:28
node and a four node okay
07:36
would be a node where you can have three
07:39
keys and four children okay and then the
07:42
keys are in ascending order if you look
07:50
into the sub trees well let me skip the
07:55
text that's probably easier to describe
07:56
it in terms of a picture okay so you
08:01
have two nodes three nodes and four
08:02
nodes and then all external nodes are on
08:05
the same level okay
08:07
the only new kind of node is a four node
08:09
a four node has three keys the three
08:12
keys are in ascending order
08:13
and all the keys in this subtree have to
08:20
be smaller than the ten the keys in the
08:23
subtree here have to lie between 10 and
08:26
30 in the next one between 30 and 35 and
08:30
then here they need to be bigger than 35
08:34
okay all right so that's the only
08:36
difference you can now have four nodes
08:38
and four nodes have this property the
08:44
minimum number of pairs you can store in
08:45
a two three four tree well that happens
08:48
when every node is a two node we've seen
08:51
that it's the same as for a two three
08:53
three and that's just two to the H minus
08:58
one nodes each node has one pair so you
09:01
have two to the H minus one
09:04
looking for the maximum for a two three
09:06
tree it occurred when all nodes with
09:08
three nodes now it's going to occur when
09:10
all nodes the four know
09:12
the equations look very similar
09:15
previously we were summing up powers of
09:17
three now you sum up powers of for each
09:20
node in a four node has three keys so
09:23
you multiply the number of nodes by
09:24
three to get four to the H minus one as
09:28
the maximum number of pairs that can be
09:31
stored the height pounds you just
09:38
reverse the bounds we just had so now
09:41
the height lies between log base four
09:42
and log base two right so that's pretty
09:47
much similar to what we had four to
09:49
three trees the node structure we just
09:54
extend our old node structure to allow
09:56
for one additional pair and one
09:57
additional pointer so we now refer to
10:03
this one as the left middle child and
10:05
the right middle child okay so you got
10:07
two middle children if you have a two
10:10
node you use the first three fields if
10:14
you have a three node you use the first
10:17
five fields and if you have a four node
10:21
you use all seven feet okay so clearly
10:25
here the spaceways stage is a lot more
10:26
in the worst case they're all two nodes
10:28
and are using only three of the seven
10:31
rather than three of the five fields
10:36
again you could have a parent field the
10:43
insert and remove or delete algorithms
10:46
they're very similar to those four to
10:48
three trees if you want to insert you
10:53
move down from the root to a leaf you'd
10:55
reach a leaf and that's where you do the
10:57
insert if you are inserting into a two
11:03
node or a three node there's no problem
11:05
it just becomes a higher degree node the
11:07
powernow occurs when you insert into a
11:09
three node and that node becomes so you
11:12
insert into a four node and now it's
11:14
capacity has been exceeded okay so you
11:17
do the same thing as you're doing before
11:18
you logically put it in so that the keys
11:21
are in ascending order okay you have one
11:24
more
11:25
kela and can hold and he also have more
11:28
children than the node can have in the
11:33
case of a three node we split off the
11:34
right key here we're going to split off
11:36
the two right keys along with the
11:40
associated pointer C D and E okay so
11:47
we'll split off the two right keys and
11:49
the associated pointers the original
11:52
node will contain only the leftmost key
11:54
that's the same as in a two three tree
11:56
the remaining key the twenty is then one
12:00
that's going to get inserted into the
12:02
parent node together with a pointer to
12:04
this new node all right so the strategy
12:12
is really the same as that used to
12:13
insert in a two three tree the only
12:15
difference is that when you do the split
12:17
you now take two keys and three pointers
12:19
and put them into the new node instead
12:21
of one key and two pointers and this of
12:25
course can propagate up towards the root
12:31
if you look at the delete again it's
12:37
similar to what happened in a two three
12:39
tree you are deleting from an interior
12:43
you transform it into removal from a
12:46
leaf node same strategy as before when
12:52
you're taking it out of a leaf if you're
12:55
taking it out of a leaf there's a three
12:57
node it becomes a two node you take it
12:59
out of a leaf that's a four node it
13:00
becomes a three node it's not a problem
13:02
okay the problem remains when you're
13:05
taking it out from a two node that's a
13:07
leaf then it becomes deficient so the
13:13
strategy to fix that deficiency is the
13:16
same you check one of the siblings if
13:19
one of the siblings is a three node you
13:21
can borrow from there like you borrowed
13:22
before the sibling will become a two
13:24
node and you would become a two node if
13:26
the sibling is a four node you can still
13:28
borrow the leftmost or rightmost
13:30
depending upon which side the sibling is
13:33
the sibling would then become a three
13:35
node and you would become a two node and
13:37
everything is of
13:40
if you can't borrow okay if you can't
13:46
borrow then you will combine so if you
13:51
can't borrow then your sibling has to be
13:53
a two node so you would combine with the
13:57
sibling together with the in-between key
14:00
in the parent and since there are no
14:04
keys in your node you will end up with a
14:07
node that has two keys or a three node
14:14
all right so the the insert and delete
14:17
are really the same minor differences
14:21
from the case over to three tree okay so
14:27
a two three four tree is really an
14:32
extension of a two three tree to the
14:34
case where you allow four nodes inserts
14:36
and deletes can be done in essentially
14:38
the same manner as they were being done
14:39
in two three trees we refer to those
14:42
algorithms as two pass algorithms
14:43
because in an insert for example you
14:46
first started the route you go down to a
14:49
leaf and then you have a backward pass
14:51
where you're doing the splits in a
14:54
remove you start at the top you go down
14:57
to the bottom and then you have a
14:58
backward pass where you doing combines
15:00
and Barros okay now what is interesting
15:05
for some applications is that in a two
15:08
three four tree you can actually perform
15:11
the insert and delete using a single
15:14
pass from the top to the bottom with the
15:18
exception of removal from a non leaf if
15:21
you're removing from a non leaf you have
15:22
to first transform it into removal from
15:24
the leaf and so you have to go somewhere
15:27
near the bottom to find something and go
15:29
back up and put it in but except for
15:34
that move something from a leaf back to
15:36
a node in the interior everything else
15:39
can be done so that you start from the
15:42
root and move downwards
15:48
you know that's something you can't do
15:51
with a two three three okay so we can
15:53
avoid the second or the bottom up pass
16:01
what that means is that you could
16:04
pipeline operations
16:05
okay so if you're doing an insert once
16:08
the insert passes down from the root
16:11
level to the next level you could start
16:13
another insert which starts at the root
16:15
level okay so you don't have to wait for
16:17
operations to finish if you have
16:20
hardware to support pipelining you could
16:22
do pipeline operations getting better
16:24
throughput alright so you can pipeline
16:30
inserts but the deletes can only be
16:31
pipelined if they are restricted to
16:35
we're done from leaf nodes okay yeah
16:40
since these are single pass top to
16:43
bottom algorithms if you don't have
16:46
parent pointers you still don't need to
16:49
stack nodes on the way down go for the
16:52
two pass out with them without parent
16:53
pointers you have to stack the path you
16:54
take on the way down okay so you can
16:58
avoid the stacking all right so we're
17:03
going to spend the rest of today's
17:05
lecture looking at how to perform the
17:08
top-down insert on the top-down delete
17:12
and then in the next lecture we'll take
17:15
a look at mapping to 3/4 trees into a
17:19
binary representation the red-black tree
17:23
alright so let's look at top-down insert
17:30
in order to avoid the backward pass we
17:35
need to identify what triggers the
17:37
backward pass and having identified what
17:40
triggers the backward pass on the way
17:42
down we need to ensure that that trigger
17:44
is not going to occur so in an insert we
17:51
start at the root you go down to the
17:52
bottom you reach your leaf you insert
17:54
into that leaf if that leaf was a two
17:57
node or a three node you don't have a
17:58
problem if that leaf is a four node then
18:01
got a big problem you got to start
18:03
moving back up okay so to avoid the
18:06
backward pass what you need to do is
18:08
make sure that when you reach that leaf
18:10
it's not a phone ode okay so you need to
18:16
study two three four trees and see how
18:19
on the way down you can ensure that you
18:22
will never end up at a phone ode okay
18:28
and a strategy that ensures this is as
18:36
you're moving downwards okay
18:38
whenever you see a four node you convert
18:41
that into a node of smaller degree so
18:44
you're not just converting leaf nodes
18:45
but you're ensuring that all of the
18:47
nodes you go through from the top to the
18:50
bottom are converted into smaller degree
18:53
nodes okay and you end up doing that
18:57
because as we'll see if you if you
19:04
convert every node you see on that
19:06
search path from a four node to
19:08
something else you can ensure that the
19:10
conversion can be done if you avoid
19:13
converting some of them you cannot
19:15
ensure that the next conversion need to
19:16
do you'll be able to perform all right
19:23
so basically if they look before you
19:24
leap strategy before you move to a four
19:27
node or before you move to the next node
19:29
take a look at it if it's a four node
19:31
take corrective action and then move
19:50
okay so let's take a look at the
19:52
different cases where in the downward
19:55
pass you may be trying to move to a foe
19:58
node alright this is what happens right
20:03
at the beginning when you step onto the
20:06
tree you could be stepping on to a root
20:09
there's a four node and that's something
20:11
you don't want to do it could happen as
20:18
you're moving down from the root to
20:22
lower levels you could be moving to a
20:25
four node that's a child of a two node
20:28
you could be moving to a four node
20:31
that's a child over three node okay but
20:36
you can't be moving to a four node
20:38
that's a child of a four node because
20:40
the strategy says will never be sitting
20:42
at a four node okay so really all we
20:49
need to be concerned about is we need to
20:51
have a way to fix the tree in case the
20:54
root is a four node we need to have a
20:58
way to fix a four node that you're
20:59
trying to move to when you're sitting at
21:01
a two node and another way to fix a four
21:04
node you're trying to move too when
21:05
you're sitting at a three node okay we
21:07
don't have to worry about this case
21:09
because we'll never be in that case all
21:16
right so let's take a look at the three
21:17
cases we have to be concerned with
21:21
all right so if the root is a four node
21:23
well that's what it looks like before
21:26
stepping on to it okay I'm going to
21:29
transform it into three two nodes and
21:36
this transformation will increase the
21:39
height of the tree by one
21:44
alright and once I make this
21:46
transformation then I'll take the insert
21:50
key in this case I guess the insert key
21:53
is not specified whatever the insert key
21:56
is you'll compare it with Y if the
21:58
insert key is smaller than Y you'll come
22:00
to X if it's bigger than why you come to
22:02
Z okay and then sitting here you'll
22:05
again apply the rule which says well I'm
22:07
sitting at a two node am I trying to
22:08
move to a four node if you're not moving
22:12
to a four node we just move if you're
22:14
trying to move to a four node well then
22:16
you have to perform a transformation on
22:17
the four node before you move to down
22:20
one level okay all right so the first
22:24
case is something could go wrong right
22:27
on the first step stepping onto the tree
22:30
and if the root happens to be a four
22:33
node you first make this transformation
22:34
and then you step onto the tree and then
22:36
you compare with Y and I do move here up
22:38
there all right the next case is you're
22:47
sitting at a two node and you're trying
22:50
to move to one of its children and that
22:52
child happens to be a four node so in
22:54
this case I'm trying to move to a left
22:55
child so I'm inserting something that's
22:57
smaller than C instead of moving to this
23:03
node I'm going to perform a
23:05
transformation which is going to split
23:08
this node up and the transformation I
23:12
will perform will take this four node
23:14
and split it up into two two nodes okay
23:17
W and Y and the in-between key is
23:20
stuffed into the node you're currently
23:23
sitting at so the the node you're
23:25
sitting at becomes a three node and the
23:27
two children down here drop down to two
23:29
nodes
23:32
alright this transformation does not
23:35
change the height of the tree okay which
23:37
is fortunate because if we change the
23:38
height of the tree you'd no longer have
23:40
a two three four tree because external
23:42
nodes would not be the same level since
23:45
the height of this subtree has gone up
23:46
at the height of other sub trees hasn't
23:52
all right so the item we're inserting is
23:56
known to be smaller than Z that's why
23:58
you are trying to move down here before
24:00
we move one level down we compare with X
24:03
if it's smaller than X you move to W if
24:05
it's bigger than X you move to Y ok so
24:10
again your position that a two node
24:22
all right if you were trying to move to
24:24
a four node out here that's similar you
24:27
perform a similar transformation okay
24:37
all right the last case to consider is
24:40
you're sitting at a three node and
24:44
you're trying to move to a child that is
24:46
a four node okay the child you're moving
24:49
to could be the left child it could be
24:51
the middle child it could be the right
24:53
one okay
24:54
this example here is for the case when
24:56
you're trying to move to the left child
24:59
so our strategy forbids us from moving
25:03
here because it's a four node I'm going
25:07
to fix this problem by splitting this
25:08
four node into two two nodes splitting
25:14
strategies are the same the middle key
25:15
gets absorbed into the parent and the
25:17
parent becomes a four node the item
25:25
you're inserting is known to be smaller
25:27
than why that's why you were trying to
25:29
move there you compare with W if it's
25:32
smaller than W you move to V if it's
25:34
bigger than W you move here and you move
25:38
down one level that way right again the
25:43
height of the sub tree doesn't change to
25:49
move down one level after the transform
25:51
you compare with W and once you move
25:59
down here again guaranteed that you're
26:01
not sitting at a phone
26:09
all right the case where the four node
26:12
is a middle child or a right child a
26:14
similar to this all right you can see
26:25
here that if you try to consider the
26:29
case that we said cannot arise moving to
26:33
a four node which is a child of a four
26:35
node okay so if this fellow already had
26:37
three keys in there
26:39
our splitting strategy would not work
26:41
our splitting strategy moving from a
26:44
three node converted this three node
26:46
into a four node the previous scheme on
26:49
the previous slide we had moving from a
26:51
two node the two node became a three
26:53
node if you tried to use the same
26:55
strategy to do the split of this fellow
26:58
you'd have to absorb one fellow here and
27:00
that four node would become a five node
27:02
which is not legal and then that could
27:05
propagate back up the tree when you try
27:08
to fix it okay
27:11
so for that reason you really have to
27:13
split all of the four nodes you
27:15
encounter on the way down because our
27:17
transformation strategy cannot handle
27:19
the case moving from four node two
27:21
followed all right so if on the way down
27:29
you split every four node E and counter
27:32
using the three transformations we saw
27:36
then you're guaranteed that when you
27:38
reach that leaf into which you need to
27:40
make the insertion that leaf would
27:42
either be a two node or a three node and
27:45
so the backward pass is not triggered
27:55
or any questions about the top-down
27:58
strategy
28:07
Yeah right that the tree itself can have
28:15
a whole bunch of four nodes in fact as
28:17
we know even the path that you took
28:19
could have four nodes because this
28:22
transformation okay
28:24
leaves a four node on the path that you
28:25
took okay so all it guarantees is the
28:30
leaf node you end up at is not a foe
28:32
node okay but if you go back and
28:36
re-examine the path you took several
28:38
nodes there might have been converted
28:40
into four nodes after you moved away
28:42
from them yeah
28:49
all right again the strategy works in
28:52
logarithmic time all right also the
29:00
number of nodes that could get
29:02
transformed is order of the height at
29:06
each level you that you move down you
29:08
could be transforming a four node in
29:10
into to two nodes okay so you could be
29:14
doing a lot of these splits okay let's
29:19
take a look at the one path delete and
29:26
this of course is only for the case
29:28
where you're removing from a leaf so
29:32
again we examine the to pass delete
29:35
algorithm to figure out what triggers
29:38
that second upward pass and we see that
29:42
the upward pass is triggered when the
29:44
leaf from which you're removing happens
29:46
to be a two node so following the same
29:50
strategy that we had for insert we need
29:53
to ensure that in your top to bottom
29:56
pass you don't end up at a two node leaf
30:01
okay so while you're making that
30:03
top-to-bottom pass you have to ensure
30:05
that when you're done the leaf you end
30:07
up with is not a two node and what that
30:13
means is that you again use the look
30:16
before you leap strategy if you're
30:18
trying to move to a two node
30:20
have to somehow transform it into a
30:22
three node or a four node and then move
30:24
to it okay yeah a slight difference here
30:31
from the insert strategy is that the
30:35
strategy permits you to start at a two
30:38
node root in the case of an insert you
30:44
could not start at a four node root you
30:46
have to first split that four node root
30:47
okay so here we have a slight difference
30:51
when you start the operation if the root
30:54
happens to be a tuner it's okay you can
30:55
move there the transformations will take
30:58
care of that case but other than being
31:09
at a two node root the strategy would
31:11
never leave you at the two node
31:23
all right so let's look at the cases
31:25
that we need to examine all right you
31:30
can move to a two node root you can't
31:33
move to any other two node if you're
31:36
moving to any other two node then we
31:39
have to fix that other two node
31:40
transform it to a three or four node and
31:42
the case is to look at our the two node
31:47
that you're trying to move to okay right
31:51
first the to note that you're trying to
31:52
move to cannot be the root okay but
31:54
that's permitted so that's case is taken
31:56
care of here so we're sitting in the
31:58
tree and we're trying to move to a child
31:59
two node and therefore that child two
32:01
node must have a sibling and so it must
32:03
have a nearest sibling so if it's near a
32:07
sibling and if it's got two of them just
32:09
look at one of them this near a sibling
32:11
is also two notes that's one case if the
32:19
nearest sibling is a three node that's
32:20
another case and if the nearest sibling
32:23
is a four node that's the third case
32:36
and when you're looking at these three
32:40
cases the note that you're currently
32:42
sitting at it could be a two node in
32:46
which case it has to be the root or it
32:49
could be a three node or four node and
32:51
those need not be the root they could be
32:54
but they need not okay
32:56
so the no D are presently at maybe a two
32:58
node a three node or a four node if it's
33:00
a two node it must be a root you're
33:02
trying to move to a child which is a two
33:04
node and that two node sibling could be
33:07
a two node or three node or four node
33:12
okay so let's look at the case first
33:17
where you only have a root okay so the
33:27
tree the two three four tree has only
33:29
one level the root level and of course
33:34
if the root is a three node or a phone
33:37
or is no problem you just take an item
33:38
out if the root is a two node okay so
33:41
this is the case where you have only one
33:45
level so the root has to be a leaf okay
33:47
and the interesting case won't look at
33:51
here is it's a two node okay so in that
33:56
case you just take the item out and
33:58
throw it away and you end up with an
33:59
empty two three four tree
34:07
okay alright so we're sitting at a node
34:16
we're trying to move to a two node and
34:19
the first case you want to look at is
34:21
the to know that you're moving to it's
34:25
near a sibling is also a two node and
34:31
that breaks down into sub cases the
34:34
current node is a two node in which case
34:37
it must be the root or the current node
34:39
is a three node or the current node is a
34:41
four node okay so here we are current
34:46
node is a two node it must be the root
34:49
you're trying to move to a child which
34:53
is a two node so you could be moving to
34:54
X you could be moving to Y and the nura
34:58
sibling of the child you're moving to is
35:00
also a two node so if you're moving to
35:02
exits near a sibling is a two node if
35:04
you're moving to Z as near as siblings
35:05
are too numbed so in this case we'll
35:17
simply combine all three nodes to create
35:19
a foe node kind of the reverse of one of
35:25
the transformations we had for insert
35:33
and the height of the tree goes down by
35:35
one okay so once you do the combining
35:42
you then have to decide which way to go
35:47
okay so we had already compared with Y
35:51
and if you're trying to remove something
35:52
that is smaller than X well then I'm
35:55
sorry smaller than Y we would have been
35:58
trying to move to X with the discovered
35:59
it's a two node okay so we're looking
36:02
for something we know it is smaller than
36:04
Y we now compare with X if we're smaller
36:06
than X we're gonna try and move here if
36:08
it's bigger than next we're gonna try
36:09
and move here okay because before you
36:13
move okay so you're gonna try and move
36:16
the node down here maybe a two node so
36:19
you'd have to apply the transformation
36:20
again before you can actually move down
36:25
all right so that's the first case any
36:28
questions about the first case alright
36:34
so the next case is the node you're
36:41
moving - it's still - no there's nearest
36:44
siblings a two node but now the current
36:45
node your aunt is a three node right so
36:52
that's a possible configuration you're
36:54
sitting at a three node you're trying to
36:56
move to a two node it could be this guy
36:57
it could be that guy the nearest sibling
37:00
is a two node right in this case the
37:07
let's assume we're trying to move to W
37:09
okay the transformation we're going to
37:11
apply again as the reverse of the insert
37:16
transform we'll take the in-between key
37:21
this two node and that two node combine
37:23
them all into a single node to get a
37:25
four node
37:31
right this transformation does not
37:34
change the height of the subtree so it
37:36
leaves all the external nodes at the
37:37
same level and having applied the
37:41
transformation okay
37:43
then we need to move either to a or to
37:46
be okay but before moving we'll apply
37:50
the same rules
37:51
okay so we'll compare with W if you're
37:56
smaller than W will check whether that's
37:58
a two node if so you have to do a
37:59
transformation if it's bigger than W
38:02
you're going to try and move here if
38:03
that's a two node here you'd have to
38:05
apply the transformations
38:16
all right the other case is where you're
38:18
trying to move to a two node that's a
38:20
middle child or a two node that's a
38:21
right child of the three node they're
38:24
pretty much the same or any questions
38:28
about that case
38:35
if you're sitting at a four node in
38:38
you're trying to do it so again it's all
38:40
the same you just take the in-between
38:42
key and combine it with the two two
38:44
nodes all right the final case you look
38:51
at is the nearest sibling of the two
38:56
node you're trying to move to is it is a
38:59
oh I guess we have a three node then we
39:03
have a four node which is probably the
39:04
same also okay all right so there a
39:07
sibling of that two node you're trying
39:09
to move to is a three node okay so the
39:13
sub cases are the current node is a two
39:15
node in which case it must be the root
39:19
so again we assume that you're trying to
39:22
move to W the nearest sibling is a three
39:26
node the transformation here is you move
39:35
the Y up to the root and you move the X
39:38
down here and you take that right
39:41
subtree along with you okay so you
39:45
transform the node that you're trying to
39:47
move to from a two node into a three
39:49
node and then you can move here okay and
39:57
once you move to this node okay you can
40:02
then perform your compares to decide
40:04
whether you should be moving to a or to
40:06
be okay you can't be moving to C so you
40:08
don't have to worry about trying to
40:10
compare with X you've already done that
40:13
comparison up here okay again this
40:17
transformation doesn't change the height
40:19
of the tree
40:22
we doesn't really matter if I change the
40:24
height it already decreased it but that
40:26
would have been okay because you're
40:29
playing around at the root level
40:30
okay all right if the two node had been
40:37
on this side is the same
40:45
all right the other cases you're sitting
40:48
at a 3-node and you're trying to move to
40:51
a two node again the two node could be
40:53
the left child the middle or the right
40:54
all the cases are really symmetric the
41:00
transformation that you apply is very
41:02
similar to the previous one from the
41:05
sibling three node you take the leftmost
41:09
key move it up take the in-between key
41:12
move it here and take the leftmost child
41:14
of the sibling node into yourself so
41:18
that transforms that two node into a
41:20
three node and now it is safe to move to
41:22
this three node and then from here you
41:24
can decide whether to move into the left
41:26
subtree of a a V or into this middle
41:29
subtree right again the transformation
41:34
doesn't change the height of the tree so
41:37
it doesn't matter that this was not the
41:38
root of the tree whether your 2 node was
41:45
the middle of the right doesn't matter
41:47
the transformation will be the same if
41:55
the current node was a four node it
41:57
wouldn't make any difference we'll do
41:59
exactly the same thanks okay the final
42:05
case is you're moving to a two node and
42:09
the nearest sibling is a four node so
42:13
again you have if the current node is a
42:16
two node it has to be the root okay
42:19
that's what things look like you perform
42:23
a very similar transformation from the
42:27
phone old you take out the leftmost
42:28
fellow move it up and move in between
42:30
key down here okay
42:32
that's really very similar to the case
42:34
where the the nearest sibling was a
42:36
three node properties are the same
42:39
there's no change in the height and it
42:42
doesn't matter whether this two node was
42:45
the left or the right child of your
42:47
current two node
42:51
okay you're a 3-node it's very similar
42:57
to the previous cases properties are the
43:03
same and again it doesn't matter whether
43:07
the two node is the left child the
43:09
middle child or the right child the case
43:17
where the current node is a four node
43:18
again it's the same as all of this it's
43:21
really nothing new there okay all right
43:30
any questions about the top-down version
43:32
yeah right the the primary advantage
43:53
would come for example if you wanted to
43:56
pipeline operations otherwise it looks
44:01
like you're doing a whole lot of work on
44:03
the way down a lot of unnecessary work
44:04
whereas in the two paths scheme you do
44:08
that extra work only when it's necessary
44:12
okay yeah okay
44:35
[Music]