Transcript


00:09
okay all right in our last lecture we
00:15
took a look at party search trees and
00:16
there we basically saw what the
00:20
functions were that was supported by
00:22
such a data structure and we also saw a
00:26
number of applications for the data
00:28
structure but today we're going to take
00:30
a look at an implementation of a
00:32
priority search tree okay all right so
00:36
if you recall in a party search tree we
00:40
store pairs of the form X Y okay so you
00:45
can think of these as points in
00:46
two-dimensional space with the x and y
00:49
coordinates given the data structure is
00:55
going to simultaneously be a min tree on
00:59
the Y values okay so each node of our
01:03
priority search tree is going to contain
01:05
one element or one of these pairs and if
01:09
you look only at the Y values then you
01:12
will have a min tree okay if you look at
01:16
the X values you will have almost a
01:19
search tree on X we'll see what almost
01:22
means when we look at the structure
01:24
itself okay so in some sense it is
01:27
simultaneously am entry and a binary
01:31
search tree okay there are two varieties
01:38
of these search trees and that's kind of
01:43
consistent with the two varieties of
01:45
search trees in general that we've
01:47
looked at so far we've had those in
01:50
which you do key comparisons to decide
01:52
whether you move to the left or the
01:53
right things like red-black trees and
01:55
AVL trees and we have things like tries
02:03
where you decide which way to go based
02:06
on a bit okay and so here we have two
02:11
similar structures or two variants one
02:16
in which the search tree part is is a
02:21
binary search tree
02:23
so it could be a balanced search tree
02:26
you may base it on a red-black tree so
02:30
you have a red-black tree on the
02:31
x-values and then this red black tree
02:34
simultaneously am entry on the y-values
02:37
okay right so we'll call that a red
02:41
black priority search tree and the other
02:44
one is based on a radix so we take the
02:48
x-values and decompose it so using a
02:52
radix and then based on that we could
02:54
move in to the left or right subtrees
02:55
okay as we'll see the decomposition
02:58
isn't quite that close to looking at the
03:02
bits it's going to be actually closer to
03:05
what's done in a segment tree so each
03:09
node has a range or interval associated
03:11
with it and then if you overlap the x
03:13
range of the left subtree you moved the
03:15
left subtree if you overlap the range of
03:17
the right subtree then the point gets
03:19
stored in the right subtree okay but the
03:22
concept is very similar okay and that's
03:25
called a radix priority search tree now
03:29
today we're going to look at only the
03:31
radix priority search tree okay that's
03:34
simpler than the red/black version in
03:37
fact that we aren't really going to look
03:39
at the red black version in class at all
03:40
okay so we're going to study only the
03:43
radix motion okay all right so look at
03:50
the radix party search tree here we're
03:55
going to make the assumption that all
03:57
the X values are different so we can't
04:00
have two pairs that have the same x
04:01
value and in the applications looked at
04:09
this constraint it really isn't
04:10
satisfied we have multiple pairs that
04:13
have the same x value but since all the
04:16
pairs are different you can do a scaling
04:18
on the X values to ensure that everybody
04:22
has a different say X prime value in
04:25
fact we did that when we were looking at
04:28
the longest prefix match application we
04:33
had to do a scaling on one of the
04:34
coordinates to make sure that everybody
04:36
was diff
04:36
and they're so by scaling the x-values
04:40
and the scaling would take into account
04:44
probably also the y-value of that point
04:46
ensuring that everybody's different we
04:49
can satisfy this constraint and then of
04:53
course as was true in the segment tree
04:55
we had to know the range of the x-values
04:57
that were being represented by those
04:59
line segments so here we have to know
05:01
that in advance to set up our priority
05:05
search tree right these constraints are
05:08
not they're on the red black version
05:12
okay but certainly on this version we
05:15
have to place these additional
05:18
constraints all right so each node in
05:23
our radix priority search tree will
05:26
contain one of the pair's and as I said
05:32
earlier if you look at only the y-values
05:35
then you get a min tree on the Y values
05:37
so the red x priority search tree will
05:39
be a min tree on the Y values okay each
05:44
node will have an interval associated
05:46
with it like you have in a segment tree
05:48
so the root interval will correspond to
05:50
the entire range of X values okay so the
05:55
interval is the that is the range of X
05:57
values you can store in that in a
06:01
subtree so if you look at any node in
06:07
the red X priority search tree okay it
06:11
has an X interval associated with it say
06:13
a B then you can compute the X intervals
06:17
associated with the left and right
06:18
subtrees by just taking the midpoint of
06:21
this interval exactly the way you do in
06:23
a segment tree okay so the left child is
06:26
interval begins at the parents interval
06:29
and then you go half way through it
06:32
and the right child's interval begins
06:37
where the left one ended up to the end
06:41
of the parents interval now unlike a
06:44
segment tree at least the version of the
06:46
segment tree we looked at where the
06:49
right endpoint of the left
06:50
was the same as the left endpoint to the
06:52
right here we're dealing with open
06:54
intervals so there's no overlap in the
06:58
points covered by the left and right
07:02
children all right let's take a look at
07:08
an example so we start with an empty
07:12
radix private research tree we make a
07:15
few inserts in there and I'll give us a
07:16
feel for what a radix priority search
07:18
tree looks like all right so let's say
07:23
that the range of X values is from 0
07:26
through 15
07:27
okay so K is 16 okay so the X interval
07:33
for the root is then 0 16 and let's say
07:38
we're going to insert 5 8 okay so
07:43
starting with an empty private research
07:45
tree you put something in you'll end up
07:47
with a tree that has one node and that
07:49
node will contain this fat all right so
07:53
we end up with a single node radix
07:55
priority search tree it's X range is 0
07:58
16 and it contains the single pair in
08:01
our collection right next suppose you
08:05
want to insert 6 9 so to insert 6 9 I
08:11
have to first decide whether 6 9 should
08:14
be placed in the root okay so first
08:17
satisfy the mentary requirement and for
08:21
that I check the Y values so since the Y
08:23
value of the point in there is 8 and the
08:26
Y value of this fellow is 9 to maintain
08:29
a mentor e58 has to remain in the root
08:33
ok all right so I first resolve whether
08:37
it's okay to leave the 5 8 there or not
08:39
to satisfy them entry property then I
08:42
decide whether the element that's going
08:47
to move down the tree should that go
08:49
into the left of the right subtree okay
08:52
all right so 5 8 is going to remain in
08:54
the root because 8 is smaller than 9 and
08:56
that then means that 6 9 has to be
08:58
inserted below the root to insert below
09:02
the root I got to decide do you go into
09:04
the
09:04
to the right sub-tree and for that we
09:06
make use of the interval represented by
09:09
the left sub-tree and the interval
09:10
represented by the right subtree
09:12
so the interval represented by the left
09:15
subtree here is half of this okay so
09:18
it'll go from 0 to 8 and the interval
09:23
for the right subtree will begin at 8
09:26
and go up to 16 okay so that the left
09:35
interval begins at 0 and goes to 8 so
09:38
it's open at 8 the right one begins at 8
09:40
goes to 16 is open at 16 the point we're
09:44
trying to insert is 6 mine so 6 lies in
09:48
the range of the left subtree and so 6 9
09:52
will get inserted in the left subtree of
09:55
the root okay left subtree of the root
09:58
is empty so we just get a note and stick
09:59
6 8 6 9 into it
10:10
so as far as the y-values are concerned
10:14
you have a mentor e on the x-values you
10:17
don't quite have a binary search tree
10:20
because there's no relationship between
10:23
the x value here and the x value that
10:26
this x value could be less than that it
10:29
could be bigger than that okay the
10:31
relationship we have on the X values is
10:33
that all the X values on the left side
10:35
are smaller than the X values on the
10:37
right side okay but so if you take the
10:40
root out of a subtree then everybody
10:42
else has a nice X relationship left
10:45
subtree has small X's then the right
10:47
subtree alright any questions about that
10:52
insert we'll do a few more all right so
10:59
let's now insert a 7 1 okay so again you
11:03
start at the root and the first decision
11:05
to make is whether this fellow displaces
11:10
the follow currently in the root and
11:11
that's done based on the min tree
11:14
property okay so here one is smaller
11:19
than 8 so if you're going to end up with
11:21
a mentor e71 has to be in the root okay
11:25
so it's got to displace the 5 8
11:27
okay so 7 1 goes in and then 5 way it
11:30
comes out okay all right so we fixed the
11:34
root the roots going to have 7 1 5 8 has
11:38
been displaced I've got to decide
11:41
whether the 5 8 that was displaced from
11:43
here
11:44
should it be inserted into the left
11:46
subtree or should it be inserted into
11:48
the right subtree so that decision is
11:50
made by looking at the range of the left
11:52
and right subtrees the range the left
11:55
subtree is 0 8 5 belongs in this range
11:58
so 5 8 has to be inserted in here then
12:03
you repeat the process does 5 8 displace
12:05
the fellow here so you check the
12:07
y-values since 8 is smaller than mine 5
12:10
8 is going to displace the 6 9 okay
12:14
right so 5 8 is going to displace the 6
12:17
9
12:21
and so the 5/8 goes in okay so the 16 is
12:28
out of the tree and now the sixth line
12:30
has to be inserted into either they left
12:34
the right subtree of the 5/8 so to
12:38
figure that out you have to look at the
12:39
range of the left subtree and the range
12:41
of the right subtree the X range the
12:44
left subtree will be half of this will
12:46
be from 0 to 4 and the right range will
12:48
be from 4 to 8 we're trying to put in a
12:52
6 mine it goes into the right subtree
13:09
okay or any questions with that insert
13:18
well let's do another one star we go to
13:23
insert eleven five so again you started
13:27
the route since 5 is bigger than 1 11 5
13:31
does not displace the fellow in the
13:33
route then you have to decide whether 11
13:36
5 goes into the left or the right
13:37
subtree the X range hears from 0 to 8 so
13:41
11 does not fit in that range it's got
13:44
to fit in this guy's range so you put
13:45
into the right subtree right subtree is
13:47
empty you just add a node out there and
13:51
you get that
14:01
okay hopefully those few insert examples
14:05
are enough to give you a good feel for
14:09
the structure all right any questions
14:15
about the structure before we try to
14:17
analyze the insert and then we take a
14:19
look at the search delete and other
14:20
operations right so so long as all the X
14:26
values are different you will always be
14:28
able to place each item
14:38
all right so take a look at properties
14:42
of this structure so if the X range is 0
14:48
to K here then here's from at each level
14:52
the range of a node becomes half of what
14:55
it was at the parent level so the total
14:57
number of levels in the structure would
14:59
be like log of K so the height of this
15:03
tree is log K and that means that the
15:11
time to insert is also log K okay if you
15:15
think back at our strategy to insert at
15:18
each level we look at only one node okay
15:21
so you look at a node you do some
15:23
constant amount of work you either
15:24
displace what's in there or you just
15:26
move down okay so teach level you do
15:29
order one work and the number of levels
15:31
is order of log K so your total insert
15:34
time is log of K in the red/black
15:41
version the number of levels would be
15:44
the height of the red-black tree so
15:46
it'll be like order of log n instead of
15:48
log k so the red/black version the
15:51
complexity has become log n but in the
15:55
radix version the complexity is a log K
15:58
K being the overall range in X values
16:04
all right if you want to do a search all
16:12
right suppose you want to search for an
16:13
item so to search for an item you given
16:17
the x and y we're going to start at the
16:19
root if the y value of the root exceeds
16:24
the Y that you're searching okay then
16:29
there's no point going any further
16:30
because Y values only increase as you go
16:33
down so once a Y value becomes too big
16:36
you terminate the search okay so if the
16:42
Y value is not bigger than the Y value
16:45
here then you check to see if this is
16:47
the point that you're looking for so you
16:48
check for equality between the X and the
16:50
y if so you're done
16:53
otherwise you have to decide whether to
16:55
go into the left of the right sub-tree
16:56
you make that decision by looking at the
16:59
x range here and the x value that you're
17:02
looking for but you only have to move
17:05
into one of the two subtrees okay so
17:09
since you have to move into only one of
17:10
the two subtrees you can spend on a lock
17:13
a time okay so a search works in log K
17:18
time if you want to remove an item the
17:27
removing works a lot like a delete min
17:31
operation in inventory so for example if
17:39
you want to remove seven one you first
17:40
search for seven one you find it and
17:43
that leaves a vacancy in this case in
17:46
the interior of the tree if seven one
17:48
was in a leaf notice not a problem you
17:50
throw away the leaf node but if it's not
17:52
in a leaf as in this case you have to
17:55
replace you had to fill up the vacancy
17:58
you fill up the vacancy we look at the
18:01
two up to two children find out which
18:03
one has the smaller y value in this case
18:05
it's this guy we move this guy up here
18:09
okay and then you get a vacancy here if
18:13
this guy had children you look at the
18:14
children find out which one has the
18:16
smaller Y value move that one okay so a
18:20
delete works just like a delete month
18:26
from a let's say from a min heap it's
18:29
very similar to that so again the
18:32
complexity of this is log K you do
18:35
constant amount of work at each level or
18:40
any questions about how a delete works
18:50
now let's look at a look at the
18:53
rectangle operations right so the first
19:00
one was to find the leftmost point in a
19:02
rectangle all right so let's suppose the
19:09
rectangle that we're doing the qurían
19:12
it's left boundary is 6 right boundary
19:14
is 12 and the top is 7 all right so
19:20
we're going to start at the root
19:23
check the Y value here will examine the
19:27
Y value if the Y value is bigger than 7
19:30
we abandon the search so for example if
19:34
this had been 12 8 say okay there's no
19:38
point going down the tree no point
19:41
checking its x value either because as
19:45
you go down the tree the Y values only
19:47
increase so if the Y value is bigger
19:50
than the top of the rectangle the search
19:54
terminates if the Y value is not bigger
19:57
than the top of the rectangle then this
19:59
point may be the answer okay so we check
20:04
to see if this point is within the
20:06
rectangle and in this case it is
20:07
assuming that if you lie on the boundary
20:09
your part of the rectangle okay so this
20:12
becomes a candidate for the answer all
20:17
right then we have to decide whether to
20:19
check the left subtree and the right
20:22
subtree to make that decision we look at
20:26
the x range of the left subtree and see
20:28
if there's an overlap with this
20:30
rectangle so there is an overlap between
20:32
0 8 & 6 12 so it's possible there is a
20:36
point here there's an overlap with this
20:41
range also so it's possible there's a
20:43
point out there now if you do find a
20:49
point in the left subtree we know that
20:52
that point is going to be better than
20:55
any point you might possibly find in the
20:57
right subtree because all points in the
20:59
left subtree are to the left of points
21:01
in the right subtree and we want to find
21:03
the leftmost
21:04
in the rectangle so if you find a single
21:06
point here that's in the rectangle we
21:09
don't need to search here at all okay so
21:12
the right subtree is searched only if
21:14
you don't find anybody here okay all
21:20
right so the strategy is check the route
21:25
if this is above the rectangle you're
21:28
done otherwise this might be a point
21:32
okay so you consider that make sure it's
21:35
in the rectangle if so it's a candidate
21:37
for the answer so it's the left subtree
21:41
okay if you find a point we saw say left
21:45
subtree only if there's a range overlap
21:47
if you find a point in the left subtree
21:50
you got to see if it's better than the
21:52
best point found so far okay because
21:54
this points here may not be to the left
21:57
of this one all right now if you find a
22:02
point to the left subtree you don't have
22:03
research here if you don't find a point
22:06
to the left subtree you have to search
22:08
yeah and to when I say you have to
22:13
search the right subtree again it is
22:14
easier to search the right subtree only
22:16
if there's a range overlap all right so
22:24
in this particular case the y-value here
22:29
isn't too big okay so we see if this is
22:33
in the range it's in the range so this
22:34
becomes a candidate check to see there's
22:37
an overlap with the left range so I
22:39
recursively search the left subtree when
22:42
you're recursively searching the left
22:44
subtree you look at eight it's outside
22:48
it's above the rectangle okay
22:50
it's bigger than seven so this point is
22:53
above the rectangle so we don't check
22:55
anybody else down here okay since you
23:00
didn't find a point here we have to look
23:04
here okay it's possible to have points
23:07
here that are better than that one okay
23:09
all right since there is a right range
23:13
right range overlap you check this one
23:15
recursively eleven five
23:18
okay so five is not above the rectangle
23:23
check to see it's within the rectangle
23:26
so that's a point it's better than that
23:29
one because it's to the left of that so
23:30
you update your best candidate then you
23:35
have to look at the left sub-tree if
23:36
there's a range overlap there is a range
23:38
overlap but there's no sub Trinity check
23:41
you didn't find a point there so you may
23:44
find a better point here so we see if
23:48
there's a range overlap with 1216 okay
23:52
there is a range overlap because x
23:56
equals 12 could be on that side it'd
23:58
still be on the boundary of this
24:00
rectangle so I search here okay all
24:04
right this six is not above the
24:06
rectangle see if it's a valid point in
24:09
the rectangle it's not then we'd check
24:13
the left sub-tree if there's a range
24:14
overlap here there is a range overlap
24:17
but it's empty you check the right
24:18
subtree if there's a range overlap there
24:20
is no range overlap we would not check
24:22
the right subtree all right so that's
24:25
how you would find the MINIX in
24:29
rectangle our questions about how the
24:34
search works so you search a subtree
24:40
only if there's a range overlap if you
24:44
find a point to the left sub-tree you
24:45
don't search the right subtree even if
24:47
there's a range overlap
24:54
alright the claim is that the complexity
24:56
of this is log of K leaning the height
24:59
it's not easy to see why that is so
25:02
because both the left and right subtrees
25:04
are being searched so let's take a look
25:08
at a proof that the complexity is log of
25:12
K all right so in the proof I'll first
25:20
put a profile of the nodes in my radix
25:25
primary search tree that get visited
25:28
during the search for the leftmost point
25:31
in the rectangle by visited what I mean
25:34
is that my search algorithm takes a look
25:39
at the point that is stored in the node
25:40
checks to see if it's y value makes this
25:43
point above the rectangle or not ok so
25:48
if you examine a point to see if it is
25:51
above the rectangle then you would state
25:54
the node
25:55
if you simply check the range over note
25:58
4 overlap you haven't visited the node
26:00
because you can do the rain check
26:02
without going down to the node you just
26:04
take the range of the know do currently
26:05
add cut it into two and do your rent
26:07
check but to check the Y value you have
26:11
to get down to the node and extract the
26:13
point ok so a node is visited if you
26:17
check the Y value of the point stored in
26:20
that node to see if it is above the
26:24
rectangle or not so when you check the y
26:29
value of the node if you find that it's
26:32
not above the rectangle we'll say the
26:35
conclusion as the Y is okay if you find
26:39
that the Y is above the rectangle then
26:41
the conclusion is that the Y value is
26:43
not okay
26:43
okay so for every node that gets
26:47
examined or visited we can label it as
26:50
either Y okay or why not okay because
26:53
for every wizard node the Y value is
26:55
checked for a node that's not visited
26:57
you don't check anything you never move
26:59
to that node all right so this here
27:04
gives me a possible profile
27:07
so some nodes have their Y value some
27:10
nodes are labeled Y is not okay some
27:12
have themselves labeled as Y is okay
27:16
okay and then of course there are other
27:19
nodes probably along the path toward the
27:22
root up here which are not shown now if
27:30
you have a node that's labeled why not
27:32
okay then it cannot have any children
27:35
that are visited okay because that's the
27:37
first thing you do you check the Y if
27:38
the Y is not okay
27:40
you discontinue the such so nodes
27:44
labeled why not okay do not have a
27:47
visited child if a node is labeled y
27:52
okay then it may or may not have a
27:55
visited child okay so for example here Y
27:59
is okay
28:00
but if there's no overlap with the left
28:03
child's range you don't visit that node
28:07
right so a child is visited only if your
28:13
Y is okay and there is a range overlap
28:18
okay all right so the first step in the
28:26
proof is label all the wizard nodes
28:32
either with y okay or why not okay
28:41
and then really what you want to show is
28:44
that the total number of nodes visited
28:47
is linear in log K time spent on each
28:53
visited node is constant you examine the
28:56
Y then you check its X and then you do
28:59
an x-ray a check for the left subtree
29:01
and I x-ray rain check for the right
29:02
subtree so time for visitor node is
29:06
order one we need to show that the total
29:08
number of visited nodes is linear in log
29:11
K all right so I've labeled this figure
29:16
doesn't show all of the visited nodes it
29:18
only shows some of them there are
29:20
additional ones on the path toward the
29:23
root all right well once you've labeled
29:34
all the visited nodes I'll then identify
29:37
a node which I'll call the yellow node
29:40
and this node has the property that is
29:43
the node it's a visited node as closest
29:46
to the root okay and both of its
29:51
children are labeled as visited they may
29:56
not both have Y okays as the children so
29:59
one could be Y okay and one is why not
30:01
okay or both could be why not okay
30:03
but yeah it's closest to the root and it
30:09
has both children labeled as visited now
30:17
it's possible that such a node doesn't
30:19
exist okay so the first thing we need to
30:22
do is establish the existence or
30:24
nonexistence of such a node
30:31
now if such a node does not exist then
30:35
every visited node has at most one
30:38
visited child because the definition of
30:44
the yellow node is it's got to be a node
30:47
with two visited children and from the
30:51
potentially many nodes that we have to
30:52
visited children is the one that's
30:54
closest to the root now if there is no
30:58
wizard node with two children then every
31:00
visited node has only one child and so
31:03
what you have if you look at your
31:04
profile of wizard nodes you have kind of
31:07
a chain it starts at the root
31:08
that's visited it's got one child that's
31:10
visited that's got one child that's
31:12
visited so the number of visited nodes
31:14
can be at most log K okay so if there is
31:19
no yellow node then there are only log K
31:21
visited nodes and so your complexities
31:24
want K alright so we may assume that
31:28
there is a yellow node otherwise you got
31:30
nothing left to prove all right so
31:37
assume there's a yellow node the next
31:39
thing we need to establish is that the
31:41
yellow node is unique so that there are
31:47
many nodes here that have to visited
31:50
children what we need to show there's
31:54
only one node that has two visited
31:57
children and it's closest to the root if
32:01
there are if there's more than one node
32:05
closest to the root that has to visit a
32:06
children that means that you've got two
32:10
or more nodes on the same level okay
32:13
they can't be on different levels
32:15
because if you're on two different
32:16
levels somebody at the higher level is
32:18
closer to the root okay all right so
32:23
suppose you say I've got this node here
32:27
okay
32:27
it's got two visited children because
32:29
that's not the way I've got in this
32:31
figure but suppose this one had two
32:32
visited children and you get somebody
32:34
out here which has two visited children
32:38
okay and you say well these two are my
32:41
yellow nodes they're the ones that are
32:42
closest to the root
32:43
with the property that they have to
32:45
visit with children well that can't be
32:47
the case because if he got this fellow
32:49
and he got that fellow then their lowest
32:52
common ancestor this guy must have its
32:56
left and right child visited okay and
33:00
that lowest common ancestor is closer to
33:02
the root than these two guys so if you
33:04
have two guys on the same level that are
33:06
visited their lowest common ancestors
33:08
closer to the root and must also have
33:10
two visitor children because if a note
33:13
is not visited you can't get to its
33:15
children okay so the yellow note is
33:19
unique all right what that means is that
33:28
the nodes that I have not shown out here
33:31
okay
33:32
on the path from this yellow node to the
33:34
root which are all visited okay
33:37
all of those guys have only one visited
33:39
child all right all right so the yellow
33:55
note is unique okay now if you look at
33:58
the subtree rooted at the yellow node
34:00
okay so certainly that sub trees got
34:04
other nodes that are visited and have
34:07
two visited children could have many of
34:09
these but the claim is that none of the
34:15
nodes down here okay that are labeled
34:18
yok can have two children that are
34:21
labeled why okay so for example this guy
34:27
here has one child labeled Y okay the
34:30
other ones labeled not okay it's not
34:35
possible for any node down here to have
34:38
two children labeled Y okay well how do
34:42
you see that if this one had been
34:45
labeled Y okay okay right so since this
34:51
is y okay there's an X range overlap
34:53
otherwise you wouldn't have even checked
34:57
since that is why okay because this
35:00
guy's got two children that are visited
35:01
there's got to be an X range overlap
35:03
otherwise you know check that okay so
35:05
you got an excellent overlap there I got
35:07
an X range over up there which means the
35:09
x value of anybody here has to be in the
35:11
rectangle and if the wire is okay then
35:14
it is a point in the rectangle so this
35:18
was okay then whatever point is stored
35:20
here is inside your career rectangle
35:23
and if it's inside your query rectangle
35:25
you should not have gone and checked
35:26
that fellow in which case this could not
35:29
be your yellow node okay so so this
35:35
fellow cannot have its Y value set to
35:38
okay if it did you should not have been
35:40
in the right subtree of the element okay
35:44
same is true here if this guy had its Y
35:49
value labeled okay it has to be a point
35:51
that is inside the rectangle and if it's
35:58
in the rectangle you should not be
36:01
searching down here its right subtree
36:05
okay so this node can only have one
36:09
fellow labeled Y okay it's either this
36:12
guy this guy's label Y okay you
36:13
shouldn't be searching here if it's this
36:15
guy this guy has to be not okay okay and
36:20
the same is true over there all right so
36:26
you can argue that no matter which node
36:29
you look at in the yellow subtree okay
36:33
that node can have only one child that
36:36
is labeled Y okay kind of too
36:46
all right so what that means is that if
36:50
you look at this yellow subtree look at
36:53
the outer left profile okay the outer
36:56
left profile can have at most log K
36:58
nodes on it and each of these nodes can
37:02
have another child but that has to be
37:04
labeled not okay you can't have a big
37:07
sub tree down here it's can only be a
37:08
single node sub tree so if you look at
37:10
the left profile of the yellow node you
37:13
can have only two log K nodes on it the
37:16
outer one can have log K and then each
37:19
of those fellows could have one child a
37:21
will not okay all right so you can have
37:24
to log here on this side similarly you
37:26
can have to log K on that side so that's
37:29
a total of four log K and that includes
37:32
whatever you've got up here because if
37:35
you had six nodes up here then down here
37:38
it's going to be a log K minus six times
37:41
four so the total number of visited
37:46
nodes is bounded by four times log K
37:58
as a result the complexity of finding
38:02
the leftmost point in the rectangle is
38:03
log K yep oh okay question is like here
38:20
okay
38:21
I found out why okay well then why would
38:24
I go into the left subtree okay now I
38:27
found out why okay right but the point
38:31
stone here may not be in the rectangle
38:33
the x value may not be in the rectangle
38:35
okay so even though there's an X range
38:39
overlap between the rectangle and here
38:41
this point may be too far to the left
38:44
okay and that's why we would go further
38:47
down okay
38:49
all right certainly if this point was in
38:52
the rectangle okay we would search down
38:54
here to find better points but we would
38:56
not go there because you found a point
38:58
on the left side you're right all right
39:03
other questions
39:09
all right if you want to do the max X
39:13
that's a metric to the men okay so we
39:15
want to find the rightmost points
39:17
instead the leftmost point we run
39:19
essentially the same algorithm except
39:22
that instead of checking the left
39:24
sub-tree first you check the right
39:25
sub-tree first okay so if there's an
39:27
overlap with the right range you go in
39:29
here if you find a point here then you
39:31
don't go here all right so this is
39:36
symmetric you do the right sub-tree
39:38
before the left otherwise the algorithm
39:40
is the same as the MINIX
39:42
and the proof is identical that the
39:46
complexities log k or maybe I should say
39:50
the proof is symmetric
40:03
or you want to find them in Y in X range
40:15
all right so let's say the range is 610
40:22
you start out here you check to see if
40:25
this point is in the range in this case
40:27
it's not but had that point been in the
40:29
range there's no point going further
40:31
down because Y values only increase okay
40:34
so the first point you find well the
40:37
closest point to the root that you find
40:39
that's in the range okay
40:42
does the job okay so here we check okay
40:46
at this point is not in the range so now
40:50
we got to check the left and right
40:51
subtrees so I find a point in the left
40:53
subtree that's in the range recursively
40:55
using this strategy find a point in the
40:58
right subtree that's in the range using
41:00
the strategy recursively and take the
41:02
better of the two you check a subtree
41:11
only if there's a range overlap just
41:16
like in the other two cases okay so
41:18
always sub trees are checked only if
41:20
there's a range overlap
41:29
or again the complexities lock' the
41:32
proof is similar to the earlier one
41:51
all right the last operation is to
41:53
enumerate the points in a rectangle it's
42:05
a given the left right and top
42:06
boundaries of the rectangle this is kind
42:15
of an extension of the algorithm to find
42:17
the leftmost point in a rectangle now we
42:19
want to find all of them so you check
42:22
the y value here which is 1 if it's
42:26
above the top boundary you abandon the
42:29
search if it's not above the top
42:33
boundary you check to see if this is a
42:34
point in the rectangle in this case it
42:36
is and so you output that as a point
42:40
they may be more points in the left
42:43
subtree and more points in the right
42:44
subtree so you search the left subtree
42:48
only if there's a range overlap and you
42:52
break all the points there then you
42:54
search the right subtree only if there's
42:56
a range overlap and numerate all the
42:58
points of that so in this particular
43:05
case there's a range overlap here so we
43:08
will be entering here we'll check this
43:11
point here 8 is not above the rectangle
43:14
and it's not inside the rectangle
43:17
because of the 5 so this point is not
43:19
output they will check the left subtree
43:23
there's no range overlap so you actually
43:26
won't come here there is a range overlap
43:30
with the right subtree so we'll visit
43:33
the right subtree this point is above
43:36
the rectangles it's not output if they
43:38
had been a big subtree here we would not
43:40
check it we would come here because
43:45
there's a range overlap the 16 sorry ok
43:51
so the 5 is not above the rectangle 11
43:55
is inside so we output that the left
43:59
range there's an overlap but it's empty
44:01
the subtree there
44:04
right range there's an overlap you enter
44:06
here the six is not outside the above
44:09
the rectangle so we checked the 14 as
44:11
outside so it's not output we'll check
44:14
the range of the left sub-tree here
44:18
there is a range overlap but this
44:20
subtree is empty there's a range overlap
44:22
there's no range overlap with the right
44:24
subtree so we don't go into the right
44:25
subtree alright so the algorithms are
44:36
fairly short with the best stated
44:39
recursively and the complexity of the
44:43
first three we saw was log K here the
44:48
complexity can be shown to be log K plus
44:52
the number of points that are in the
44:55
answer again the reasoning is very
45:00
similar to the first proof you kind of
45:03
look at the envelope and if you actually
45:04
look at points inside the envelope they
45:08
have to be in the rectangle or they have
45:11
to be labeled why not okay all right any
45:17
questions
45:24
all right so we'll stop here