Transcript


00:50
but today we're going to continue our
00:53
discussion of tries if you recall we
00:56
started with a discussion of a fairly
00:59
simple data structure called a digital
01:01
tree and we noted that the digital tree
01:05
had a deficiency when you were dealing
01:07
with large keys in that you had to
01:09
perform a comparison at every node you
01:11
went through to overcome this problem we
01:14
came up with a data structure called a
01:16
try in which you had to perform only one
01:20
comparison now the try had a problem in
01:24
that the number of nodes needed could be
01:28
potentially large relative to the number
01:30
of keys that you have because you can't
01:34
really control the number of branch
01:37
nodes too well so then we came up with a
01:41
refined version of a try
01:43
called a compressed try in a compressed
01:47
try the number of branch nodes was
01:49
always one less than the number of
01:52
element nodes now today we're going to
01:58
look at a refinement of the compressed
02:02
binary tree that we saw in the last
02:04
lecture and this refinement is a data
02:08
structure called patrícia
02:10
where the name Patricia is actually an
02:15
acronym for a for practical algorithm to
02:18
retrieve information coded in
02:20
alpha-numeric so it's a data structure
02:23
that was developed to store large pieces
02:27
of text and it's really you could think
02:36
of it as a compressed binary try or
02:38
really as a refinement of the compressed
02:41
binary try as we discussed last time
02:46
yeah unlike the compressed binary tried
02:51
that we discussed the last time which
02:53
had two different types of nodes we had
02:56
branch nodes and we had element nodes in
02:58
patricia you have only one kind of node
03:03
and that turns out to be a useful
03:09
property if you're implementing in
03:10
certain programming languages they don't
03:13
permit you to have a pointer that goes
03:15
to two different types of nodes and it's
03:20
also advantageous from the storage
03:22
management point of view when you have
03:24
only one kind of node the storage
03:27
management techniques are a lot simpler
03:28
than when you have multiple kinds of
03:31
nodes all right the first thing to note
03:43
is that this data structure is going to
03:45
employ a header node which we didn't
03:48
really have in a compressed binary try
03:53
the remaining nodes in an instance of
03:57
patricia will actually form a tri
04:01
structure which will be developed as the
04:05
left subtree of the header node so the
04:08
right subtree of the header node is
04:09
going to be empty there's going to be
04:11
nothing out there okay the left subtree
04:15
of the header node it's a try and really
04:19
that try is going to be identical to the
04:22
branching structure of the compressed
04:24
binary tree so looking at an example
04:32
okay let's just take a look at the node
04:34
structure that would go to the employee
04:35
each node is going to have four fields
04:39
in it okay of these correspond to the
04:42
fields of a branch node in a compressed
04:44
binary tribe bit number left child and
04:46
right child okay the fourth field is the
04:50
single field that was present in an
04:52
element node okay so in some sense a
04:55
node of patricia is going to be used to
04:58
represent one branch node of the
05:01
compressed binary try and also one
05:04
element node of the compressed binary
05:07
tree
05:13
right the interpretation of the fields
05:16
are the same as what we had looks like
05:20
this TVs gonna die
05:22
maybe we need to start looking at a
05:24
different one okay all right we will
05:27
look at this one here
05:29
all right so each field right has the
05:34
same meaning as it did in the case of a
05:38
compressed binary try okay let's look at
05:48
the transformation when it's come back
05:51
okay now look at the transformation from
05:54
a compressed binary try to an instance
05:56
of Patricia okay but here's our
06:00
compressed binary try okay
06:03
so basically what we're going to do is
06:07
we're going to replace each of the
06:10
branch nodes okay so each of the branch
06:15
nodes will get replaced by one of the
06:18
patricia nodes in addition there's going
06:22
to be a head node okay and that head
06:26
node as its left subtree is going to be
06:28
this collection of branch nodes
06:36
for the elements okay right so these
06:40
nodes are really going to vanish okay so
06:43
all of the yellow nodes the element
06:45
nodes are going to vanish and what's
06:49
going to happen is wherever there's an
06:52
element right now we're going to move
06:55
that into an ancestor node of the
06:58
instance of Patricia so an ancestor node
07:01
for example zero zero zero one could
07:03
move to this node which is an ancestor
07:06
of the original element node it could
07:08
move into the root it could also move
07:11
into the header node okay all right so
07:18
for zero zero zero one you have three
07:21
options move it into its parent into the
07:23
grandparent or into the header node four
07:25
one zero zero zero you have four options
07:28
you could move it into the parent
07:30
grandparent great-grandparent or the
07:32
header all right so here is a one result
07:42
of doing that okay I have a header node
07:46
okay and then the remaining nodes in the
07:50
instance of Patricia represent one of
07:53
the branch nodes of the compressed
07:55
binary try all of the yellow or element
07:59
nodes are vanished okay where we
08:03
previously had a yellow or element node
08:05
I have taken the element and moved it
08:09
into an ancestor of that yellow element
08:11
node the pointer that went to the
08:15
element node now goes to whichever
08:19
ancestor node contains the element okay
08:22
so if you look back to an earlier slide
08:26
that you have the left child pointer
08:28
here previously pointing to an element
08:30
node that contains zero zero zero one
08:33
okay so that pointer now points to the
08:36
header node because the header node
08:38
contains zero zero zero one okay so
08:42
really what you've done is you folded
08:44
those element nodes into nodes of
08:48
Patricia
08:50
okay so each element node gets folded
08:52
into an ancestor note this tri is not
09:04
basically a tree okay it's a tree if you
09:08
look only at the black pointers okay
09:10
once you factor in the red pointers
09:12
which are the backward pointers then you
09:15
really don't have a tree yeah you're
09:18
right okay all right so to summarize
09:27
Patricia is a compressed binary tree in
09:31
which the element nodes and branch nodes
09:35
have been folded into a new class of
09:38
node to make things work you throw in a
09:41
header node because in the original
09:44
representation of a compressed binary
09:46
try the number of element nodes is one
09:49
more than the number of branch nodes so
09:54
once you throw in a hello node you now
09:56
have enough nodes to represent all the
09:58
elements the folding is done in a
10:02
reasonably systematic fashion element
10:05
nodes get folded into an ancestor all
10:13
right now that you have two it seems
10:18
that what you have done is you have
10:20
converted the two different type of node
10:24
representation into a two different type
10:27
of edge representation okay previously
10:31
we had information or we had element
10:33
nodes and branch nodes now we have these
10:36
black pointers which are downward or
10:39
three pointers and these red ones which
10:41
are backward pointers pointing to where
10:44
the element node got folded now it's
10:50
easy to distinguish between a black or
10:53
downward pointer and one of these red
10:55
pointers if you look at black pointers
10:58
okay they go from a node with a small
11:02
bit number
11:03
to a node with a higher bit number okay
11:06
that's always the case as you go down
11:08
the original compressed binary try but
11:11
numbers always increase the red nodes on
11:15
the other hand start at a node with a
11:19
given bit number for example here bit
11:22
number three and they go to a node with
11:24
a smaller bit number zero or they
11:27
started a node with a bit number like
11:29
three and go to a node with the same bit
11:31
number okay so if you look at all of the
11:35
red pointers the red pointers have the
11:38
property that the start bit number is
11:41
greater than or equal to the finish bit
11:44
number the black pointers have the
11:46
property that the start bit number is
11:49
smaller than the finish bit number okay
11:54
so by comparing the bit numbers at the
11:55
ends of the pointer you can tell whether
11:58
you're moving down the tree or you are
12:00
taking a backward pointer to an element
12:02
node okay all right so for example if
12:08
you're searching for let's say you're
12:13
searching for zero zero zero one okay
12:15
the way you would perform that searches
12:18
you start at the header node you would
12:20
follow the left child pointer to enter
12:22
the tree okay so you follow the left
12:28
child pointer to enter the tree whenever
12:31
you follow a pointer you check the bit
12:33
number of the start against the bit
12:35
number of the finish okay if it turned
12:38
out that the victim wouldn't increase
12:41
then you would know that you were
12:43
following one of these red pointers and
12:44
you've reached an element node and now
12:46
it's time to compare with the element in
12:48
that node right here the bit number
12:51
actually increases so it's not time to
12:53
do any comparison okay we use the bit
12:56
number field one see the sample bit one
12:58
of your search key that's a zero recall
13:00
we're looking for zero zero zero one
13:02
okay so you follow the left branch again
13:05
the bit number field increases along the
13:07
pointer so you're not reaching an
13:10
element yet you're still reaching
13:12
another branch node this says use bit
13:15
number three
13:16
so you use bit three which is also a
13:18
zero so now you follow this red pointer
13:21
you know it's a red pointer because you
13:24
look at the start and finish bit numbers
13:26
and they decrease so once you follow a
13:29
red pointer you know it's now time to
13:31
compare so now you compare your search
13:34
key zero zero zero one with what's in
13:36
there you find a match and you're done
13:52
all right questions about about the
13:56
structure before we look at how to
13:58
insert and delete all right let's take a
14:10
look at insert we're going to start with
14:13
an empty instance of patricia an empty
14:18
instance means there are no elements and
14:20
so there will be no nodes not even a
14:24
header node okay the total number of
14:29
nodes including the header node will
14:31
always be equal to the number of
14:32
elements so if you have zero elements
14:35
you're going to have zero nodes no
14:37
header node that's kind of different
14:39
from how you represent say empty chains
14:42
with headers or empty binary trees with
14:44
headers where the header is always
14:46
present here the header is not present
14:48
when you have zero elements all right so
14:53
we start with an empty instance and
14:55
let's say we want to insert this seven
14:58
bit key okay so when you start with an
15:02
empty instance you're going to end up
15:04
with an instance that has one element
15:06
such an instance will have only the
15:07
header okay so you create a header place
15:11
the key in there and then in the header
15:15
the left child pointer is supposed to
15:19
point to the root of the reel compressed
15:22
binary try over there but since that
15:24
part is empty it just points back to
15:26
itself
15:27
okay all right so this tells you that
15:29
it's a backward pointer the starting bit
15:32
number is zero the finished bit number
15:33
is zero so this is really a backward bit
15:36
pointer going to the element
15:45
alright next let's insert the key with
15:50
all seven bits equal to zero to make
15:53
this insertion you need to first perform
15:55
a search you need to make sure that the
15:57
element isn't already present and of
16:00
course the search also tells you where
16:02
to put the new element okay all right so
16:05
you perform a search which means from
16:11
the header okay you follow the left
16:13
child pointer into the Tri whenever you
16:17
follow a pointer you check to see if you
16:19
are following a blank or a red pointer
16:22
so in this case we know it's a red
16:24
pointer start and finish bits are the
16:26
same when it's a red pointer or a
16:29
backward pointer you then compare you
16:31
find they're not equal okay so now you
16:37
know that you really have to insert this
16:38
element which means you go to increase
16:40
the number of nodes by one okay so
16:43
you're going to get a new node and into
16:45
that node you're going to place this key
16:50
the bit number field for this new node
16:53
is determined by finding the first bit
16:56
on which these two keys differ and that
16:59
is bit number five so I'm going to
17:04
create a new node this will be the root
17:07
of the tree and it's going to differ on
17:10
bit five okay so bit number field there
17:13
will be a five in terms of where to
17:18
place it in a general situation as was
17:20
the case in a compressed binary try you
17:22
really take a look at the path that you
17:24
followed you know that on the path that
17:26
you follow okay all the black links in
17:29
this case there are no black links but
17:31
in a general situation there would be
17:33
black pointers so you could take a look
17:35
at all those black pointers and you have
17:37
to place this bit number five so that
17:41
all of those bit numbers are an
17:42
increasing order okay and in this
17:45
particular case bit number five just
17:48
means you break this red pointer out
17:50
here and have it point to the new root
17:54
of the Tri
17:56
so you break the pointer it points to
18:02
the new node that you've created in the
18:04
new node you place the key the branch or
18:06
bit number field is going to be five now
18:10
you have to set the two children
18:13
pointers of this newly created node the
18:17
left child pointer is going to go to a
18:22
subtree which has all of the keys whose
18:25
bit five is zero and the right child
18:28
pointer has to go to where you have the
18:30
keys with bit five equal to one okay
18:34
this particular key that you put in has
18:36
a bit five equal to zero that means that
18:39
all the other keys you have must have a
18:41
bit five equal to one okay so the left
18:43
pointer is going to come back to this
18:44
node and the right pointer is going to
18:47
point to wherever you previously pointed
18:50
to because everybody else has bit five
18:54
equal to one okay all right so this one
18:58
comes back to this node okay so whenever
19:01
you create a new node one of the
19:03
pointers is going to come back to the
19:05
node we just created the other pointer
19:09
will actually go to wherever the pointer
19:11
you broke went
19:26
okay let's try a few more inserts I'll
19:28
give you a better feel for how this
19:30
thing works all right this is our
19:35
current state we're now going to insert
19:39
five zeros and a one zero so first we
19:46
perform a search to search you follow
19:51
the left pointer in the header node okay
19:56
the big number field increases so we
19:58
know we've reached a real root we
20:00
haven't followed a backward pointer this
20:03
fellow says branch on bit five bit five
20:06
is a zero
20:08
so you follow this red pointer okay we
20:12
know it's a red pointer because the bit
20:14
number field did not increase along the
20:16
pointer okay so this time we compare the
20:19
key in this node with this we find
20:22
they're not the same that tells us that
20:24
there is no key equal to this in
20:27
patrícia at this time so I sample these
20:32
two keys to find out the first place
20:34
where they differ and they differ on bit
20:38
six so I'm going to get a new node and
20:43
in that new node I'm going to place this
20:45
key and the big number field is going to
20:48
be six the new node is going to get
20:53
inserted along this search path okay
20:57
starting from the header moving to this
20:59
node here and then following this red
21:01
pointer defines the search path that we
21:03
took so somewhere along this path we're
21:06
going to insert the new node and it's
21:09
done such that the bit number fields
21:11
increase along that path so here are our
21:13
since the bit number field is going to
21:15
be six we're going to break this pointer
21:18
and place it down here okay all right so
21:24
this pointer gets broken and it's going
21:26
to point to the new node with bit number
21:30
equal to six
21:35
the task that remains is to figure out
21:38
the left and right child pointer of the
21:40
new node one of those pointers is going
21:43
to come back to this new node and the
21:45
other one is going to go to wherever the
21:47
broken pointer went to determine which
21:53
one comes back to this node we need to
21:55
know where the bit six of this fellow is
21:58
a one or a zero which six is a one which
22:01
means the right point is going to come
22:02
back here and then the other pointers
22:05
are going to go to wherever the broken
22:07
pointer went so the broken pointer
22:11
previously went to this node so now your
22:13
left pointer is going to go there and
22:15
your right point is going to come back
22:17
to you
22:37
all right let's try three zeros a one
22:40
followed by three zeros again you start
22:44
at the header you follow the left child
22:47
pointer verify that the bit numbers
22:49
increased so long as the bit numbers
22:53
increase you keep branching okay so you
22:56
look at bit five bit 5 is a zero so you
23:00
follow the left child pointer the bit
23:02
numbers increase so now you look at bit
23:05
six which is also a zero so you follow
23:08
the left child pointer and now the bit
23:10
number decreased so it's a backward
23:13
pointer that's your cue there is now
23:15
time to do a comparison so you compare
23:18
the two and you find they're not the
23:20
same we know that we're now going to do
23:24
a real insert which means we're going to
23:26
add a new node into that new node will
23:31
place the insert key the bit number
23:34
field for the new node will be the first
23:36
bit on which these two keys differ okay
23:40
so the first bit on which they differ is
23:42
bit number four so one here and so zero
23:46
over there you find the place to insert
23:51
the new node you examine the bit numbers
23:54
on this path zero five six and it has to
23:59
go in such a way that after the insert
24:01
is still increasing so it's going to
24:03
come over here okay between the zero and
24:05
the five so then along the path it will
24:13
become zero four five six
24:19
okay all right so the new node is going
24:22
to be inserted along your search path so
24:24
that the bit numbers are still in
24:26
ascending order this is the pointer that
24:31
gets broken so the broken pointer now
24:34
comes to the new node to get the
24:37
children of the new node okay this is a
24:42
branch and bit four so look at bit four
24:44
of this insert key is a one which means
24:47
that the right child pointer is going to
24:49
point back to this node and the left
24:52
child pointer is going to go to whatever
24:53
that broken pointer went before namely
24:56
here
25:18
okay I think I still have some more
25:22
examples of insert so let's go through
25:24
these all right 4 zeros 1 0 0
25:35
you start at the header moving to the
25:38
left child the big number field has
25:40
increased
25:41
this says branch and bit for bit 4 is a
25:47
0 so you follow the left child pointer
25:50
again the bit number field increases you
25:53
have to keep moving so you look at bit 5
25:56
but 5 is a 1 so now you follow the right
25:59
child pointer okay the big number field
26:02
has gone down so we don't move anymore
26:05
instead you do a comparison you find
26:08
that these two are not the same so we
26:11
get a new node we insert this fellow
26:13
into the new node the bit number field
26:15
will be the first bit on which the
26:16
insert key differs from the found key
26:18
and the first place that they differ is
26:21
in bit 7 so the bit number field for the
26:26
new node is 7 then you have to find out
26:30
where does this new node go in the
26:32
search path your search path was 0 for 5
26:35
and then back up over there okay it has
26:38
to be in ascending order so it would be
26:40
0 for 5 and then 7 so it's going to
26:42
break this pointer here yeah
26:55
right so if you look at this again okay
26:59
we start at the header we move over here
27:01
then you look at bit four and you move
27:04
over there then you look at bit five and
27:06
that gets you to the header then you
27:09
compare the fellow in the header with
27:11
this and find they're not the same okay
27:14
right yeah so you're right we did
27:17
compare this with the fellow in the
27:18
header and then we found that the person
27:21
in the header differs from this the
27:24
first place it differs is bit seven that
27:26
gave us the bit number field for the new
27:27
node once you know that you can then
27:30
reexamine this path and find out exactly
27:33
where to put somebody with a bit number
27:36
seven and and that's exactly where's
27:39
just so that your bit numbers are still
27:42
increasing along that path all right so
27:47
I break the red pointer that was
27:49
previously the right child of five and
27:53
the broken pointer now points to the new
27:56
node then I have to get the two children
27:59
for the new node one of the children is
28:02
going to go back to the new node and the
28:06
other one will go to wherever that
28:08
broken pointer went to before so I look
28:12
at bit seven bit seven is a zero that
28:15
means that the left child pointer is
28:17
going to come back to this node the
28:21
other pointer the right child is going
28:23
to go to whatever the broken pointer
28:25
went before it was going to the header
28:27
so the right child is going to go to the
28:29
header
28:42
all right yet another insert all right
28:50
this time it's three zeros one zero one
28:53
zero you start at the header follow the
28:58
left child pointer the bit number is
29:01
increased so you follow a pointer based
29:04
on bit for bit four is a one so we're
29:09
going to follow this red pointer this
29:13
time the big number field does not
29:15
increase when you follow the pointer so
29:18
you stop following pointers instead II
29:19
do a compare when you do a compare you
29:23
find the two keys are not the same so we
29:26
are actually going to increase the
29:27
number of notes by one I get a new note
29:31
into that note I place the insert key I
29:34
sample the insert key and the found key
29:37
that's the one in this node with bit
29:39
number four you find the leftmost place
29:42
where the two keys differ and that's bit
29:45
number six so I'll be placing the new
29:49
node along the search path I used zero
29:52
four and then back to four in such a way
29:55
that your bit number fields increase
29:57
okay so your choices really are you
29:59
could have done it there but then it
30:00
wouldn't increase or you have to break
30:02
this pointer in that case it will
30:04
increase okay so we're going to be
30:06
breaking this red pointer here
30:14
okay so once you break the pointer the
30:16
broken pointer now comes to the new node
30:18
and then you need to determine the left
30:23
and right child pointers of the new node
30:25
for that you look at bit six of the
30:32
insert key okay
30:35
so bit six of the insert keys of one
30:38
that tells you that the right child
30:40
pointer of this node is going to come
30:42
back to itself and that in turn tells
30:45
you that the left child pointer is going
30:47
to go to whatever the broken pointer
30:49
went the broken pointer was going back
30:52
to this node with bit number four so the
30:54
left child pointer will now go to that
30:56
node and the right child pointer comes
31:00
back to itself
31:19
aren't any questions about the insect
31:50
right by the comment is suppose you want
31:55
to research for the item in the header
31:56
in this case four zeros one zero one
31:59
that search is not going to be
32:01
terminated
32:03
until you have followed a path you
32:06
follow a red link back and then you do a
32:08
compare okay and it's important to note
32:10
that you do not perform comparisons
32:13
while you are still following black
32:15
pointers so you may go past the thing
32:18
you're looking for but you don't know
32:20
that okay and the reason you don't
32:23
perform comparisons on the way down is
32:26
we want to limit the number of compares
32:29
to b1 and we want to do that because
32:32
we're making the assumption that the
32:33
keys we're dealing with a rather long
32:44
all right so the time to perform an
32:48
insert is order of the height of the
32:50
structure the height is limited by the
32:53
number of bits though if you have very
32:59
long keys the height would normally not
33:01
be large in fact there are some studies
33:05
done on on the expected height of these
33:08
in the face of long keys and the
33:10
expected height is actually logarithmic
33:12
in the number of keys oh right
33:21
it is a compressed try okay and it's
33:25
just a you might look at it as a cute
33:27
way of representing a compress try as we
33:30
discussed last time basically all you
33:33
have done is you've taken the element
33:34
nodes and folded them back into one of
33:36
the branch nodes okay so if you wanted
33:41
to you could probably take a very strict
33:45
view of this and say oh it's really not
33:46
a different data structure it's the same
33:48
thing is just a coding trick that you
33:50
performed and that's probably your
33:53
correct assessment
34:01
now something to note is that even
34:04
though whenever you insert a node one of
34:08
the pointers is always a red pointer
34:10
coming back to that node after a while
34:13
if you look at the nodes you find that
34:15
some of these fellows don't really have
34:17
a red pointer okay so this guy here when
34:23
it was created it had a red pointer
34:25
coming back to it but now it doesn't
34:28
similarly this fellow doesn't have a
34:30
pointer coming back to it so as you do
34:31
inserts some of these pointers get
34:34
broken and are no longer red pointers
34:45
let's take a look at delete all right so
34:53
to perform a deletion you need to first
34:54
find the node that contains the element
34:58
that you're trying to throw out so you
35:02
perform a search we know how to do the
35:03
search and let's suppose the search gets
35:06
you to a node P and that's got the
35:09
fellow you want to remove the delete
35:15
breaks down into two cases one when the
35:19
node P that's the fellow that contains
35:22
the the element you're trying to delete
35:23
it contains a self pointer okay so a
35:27
self pointer is a red pointer coming
35:28
back to you as I said when a node is
35:34
newly created it always has one self
35:36
pointer but after a while nodes with
35:40
zero self pointers appear in your tree
35:43
okay so if you have one self pointer
35:46
that's case one if you have no self
35:50
pointer that's case two
35:57
now let's look at the case of oneself
36:00
pointer so oneself pointer it could
36:05
happen that the element you're removing
36:09
is in the header okay so if the header
36:15
has a self pointer the header has only
36:17
one pointer a left child pointer if
36:19
that's a self pointer that means that
36:21
after they delete you have an empty
36:22
structure there are no notes okay so if
36:30
the element you're trying to remove is
36:32
in the header and the header has a self
36:34
pointer then following the delete you
36:37
have an empty try zero notes all right
36:47
so you just changed the pointer that
36:48
went to the header and make it no all
36:56
right so let's assume that the element
36:58
you're trying to remove is not in the
37:00
header in this case what we're going to
37:06
do is we're just going to take the note
37:07
P throw it away and update the pointer
37:11
that is coming to P from its parent okay
37:13
so P is not the header so it has to have
37:15
a parent okay let's see what this means
37:18
okay all right so here's a possible
37:21
configuration you're trying to remove
37:23
this element three zeros one another
37:27
three zeros it's in a note that has one
37:30
self pointer the right child pointer is
37:33
a self pointer P is not the header note
37:37
okay so since it's now the header it's
37:40
got a pointer coming to it from its
37:41
parent that's got to be a black pointer
37:45
this other pointer has also got to be a
37:47
black pointer no node has two red
37:50
pointers all right so here is a possible
37:57
configuration what we're going to do is
38:02
we're going to simply change the pointer
38:05
okay we're just coming to this node from
38:07
its parent and have it point two
38:10
this other pointer goes
38:19
all right so this takes this node P and
38:23
removes it from Patricia and what you're
38:31
left behind with is a correctly
38:33
structured instance of Patricia
38:46
but here's another possible
38:49
configuration you have a node P it's not
38:53
the header so there is a black pointer
38:55
coming to it from its parent it has one
38:58
self pointer okay and in this case the
39:02
other pointer is a red pointer or a back
39:04
pointer okay we can do exactly the same
39:08
thing the pointer from the parent is
39:10
changed so that it points to whatever
39:13
the other pointer is going to okay where
39:15
the non self pointer is going to once
39:21
again the node P is now removed from
39:24
your tree this that this new pointer is
39:33
pointing to the same element that this
39:34
one was previously pointing to
39:48
or any questions about this case
39:58
all right so let's then move on to the
40:02
second case in this one the node P this
40:08
is the node that contains the element
40:10
you're trying to remove has no self
40:12
pointer okay again keep in mind there
40:16
are only two cases the node P either has
40:19
one self pointer or it has no self
40:23
pointer you can't have two self pointers
40:29
all right in this case what we're going
40:32
to do is we're going to find a node Q
40:42
that has this red pointer coming to P
40:49
okay all right so somehow we're going to
40:52
find the node Q that has the red pointer
40:54
to P and actually that somehow is not
40:56
difficult you must have already followed
40:58
that red pointer that's how you got to
41:00
pee the way you get to the node that
41:04
contains a key where you do a comparison
41:06
is you follow a red pointer to it okay
41:12
so you actually already know Q that's
41:14
the node you saw just before you saw the
41:18
node P
41:35
okay so the note key was determined
41:38
actually just before you reached the
41:39
node that contained your search key k
41:41
you followed a red pointer in queue and
41:44
he ended up in P now what we're going to
41:52
do is instead of deleting the node P
41:57
okay deleting the node P is going to be
42:00
kind of hard it's like if you think back
42:02
to a deletion from a binary search tree
42:05
if you have a node that has two children
42:08
well then we don't really delete that
42:10
node we find an easier node to delete so
42:13
we're going to do the same thing here
42:15
instead of physically deleting the node
42:17
P we're going to find a node that is
42:20
easier to delete and in this case the
42:22
easier no to delete is going to be the
42:24
node Q okay so we're going to delete the
42:28
node Q but to delete Q we know that Q
42:32
contains an element okay so we're going
42:35
to take that element and promote it into
42:36
P okay just like you would in a binary
42:41
search tree deletion from a node of
42:44
degree two you'd find this easier node
42:46
to delete from and the element in that
42:48
easier node is moved into this degree 2
42:51
node all right so when I was searching
43:00
for the delete key K you started at the
43:03
header you kind of moved down okay and
43:05
along this path you actually passed the
43:08
key K but we didn't know that we don't
43:11
do searches on the way down okay so you
43:13
always pass the key you want to delete K
43:16
so you already passed it you came down
43:19
here and then you followed this red
43:22
pointer and that's what said now do a
43:25
search right so the node Q is this node
43:33
that contained that red pointer that you
43:35
followed
43:40
okay so rather than attempt to remove
43:45
this node P we're actually going to
43:47
remove this node Q and this is an easier
43:51
no to remove because this fellow has a
43:53
red pointer in it so to remove this node
44:02
this element here is going to get
44:04
promoted and moved in here okay so once
44:09
you move this element in there
44:11
this red pointer of course this red
44:13
pointer serves no purpose after you've
44:14
taken the key out of this node the
44:16
original key okay once you've moved Y
44:19
out there this node itself doesn't serve
44:21
any purpose because the red pointers
44:23
have no use and the key is gone okay the
44:28
only thing you need to worry about
44:29
before you actually throw this node Q
44:31
away is that somewhere down here there's
44:35
a fellow with a red pointer coming to Q
44:37
that's the red pointer that helps you
44:39
find the element Y which you have now
44:41
moved away from here to there okay so
44:44
you got to find this node that is
44:46
somewhere down there that points to Q
44:49
and change that pointer so that it goes
44:52
to the new place of Y okay so we'll call
44:57
the node that contains that pointer
44:59
coming back to Q R all right so this is
45:09
our current situation okay I'm going to
45:12
find the node R okay so somewhere down
45:18
here there is a node R which points back
45:21
to Q okay to find our I will use the key
45:26
that's presently in Q namely Y okay so
45:33
you continue now branching based on the
45:35
bits and Y and that will eventually get
45:38
you to this red pointer that points back
45:40
to Q
45:49
now it's quite possible that Q&R; may be
45:53
the same node okay it's possible that
46:00
this left child pointers are self
46:02
pointer coming back to queue right so so
46:08
you want to be careful that that's
46:10
possible our diagrams kind of assume
46:12
that they're different but you don't do
46:14
anything substantially different if our
46:16
happens to be the same as Q all right so
46:22
now I've got everything I need to
46:23
complete the deletion peas the node that
46:26
contains the element you want to remove
46:28
Q is the fellow who has the back pointer
46:31
coming to P R is the fellow who has the
46:33
back pointer going to Q you can find P Q
46:39
and R all in time order of height of the
46:42
tree all right so now the things we're
46:47
going to do are we're going to first
46:52
take the pair that is sitting in this
46:55
node and move it here
47:06
all right then we'll take the back
47:10
pointer in our okay which is going here
47:14
and we're going to have a now point to
47:16
the new location of the element
47:27
okay
47:29
all right so now this is what things
47:31
look like the last thing we're going to
47:38
do is what's actually going to remove
47:40
this node from the tree and that is the
47:43
pointer coming from the parent of q2
47:45
this fellow is going to get changed so
47:47
that it points to the child of Q
48:08
and that really takes care of this case
48:20
or any questions about deletion again it
48:28
shouldn't be too hard for you to see
48:30
that this runs in order of height time
48:39
yeah which which red point are you
48:47
looking at this one no well what the
48:52
pointer is there but you can't get to
48:54
this node starting from the header okay
48:58
so if you start from the header there's
48:59
no way to reach this node so the node is
49:01
no longer part of the tree okay so you
49:06
don't really have to go and physically
49:07
change this to no or something because
49:09
the node is not reachable from your
49:12
header node okay typically what you'll
49:16
do is after you've done all this you'd
49:18
probably go and do a delete queue put it
49:21
back into the storage pool or something
49:26
all right any other questions
49:41
the space occupied by Q hasn't been
49:44
released but once there are no what it
49:47
depends on the kind of language you're
49:48
working in if you're working in
49:50
something like C++ which requires you to
49:53
explicitly free the space then after
49:55
you're done all this you'll have a line
49:56
of code which says delete Q and that
49:59
would free the space okay you're working
50:01
in a language like Java you would do
50:03
nothing because Java has a garbage
50:05
collector and the garbage collector will
50:07
come around and find that there's no way
50:09
for your program to get to this node and
50:11
then it will put it back in the storage
50:13
pool okay okay we'll stop here Thanks
51:40
you