[MUSIC] So if we end up with a nearly
balanced binary tree. So a nearly balanced binary tree
is something that looks mostly. So this is a binary tree. A balanced binary tree. This would be a balanced binary tree. There are the same number of leaves
on the left and right-hand side. So we can start talking about what is
the size and the depth of this tree. So if there are N total data points, and
let's assume that we end up with just one observation at each leaf node, then how
many nodes are there total in this tree? We can show that there are 2N- 1 nodes. And so let's see. If we had four data points, we have one,
two, three, four, five, six, seven nodes. And that's exactly 2 times 4 minus 1 is 7. Okay, so at least that little
example checks out there. So this is 2N- 1 nodes if one data point at each leaf. And assuming that it's
a balanced binary tree. But the point is that there's on
the order of N nodes in our tree. And how deep is the tree? Well, the tree has depth
that's on the order of log N. And that's also pretty
straightforward to show. So when N is 4,
we end up with a depth 2 tree. Okay, so now let's talk a little bit about
the complexity of constructing this tree. And so, what do we have to do? Well, if we use our median heuristic for how to set the split value,
then at every level of our tree, we have N observations that we either
have to send to the right or to the left. So in the first case,
it's just one split left and right. At the second level you have two splits. But they're splits of smaller numbers of
points and this goes on and on and on. But what you can show is that if you
do an efficient implementation of this, again, using a priority queue
like we've talked about earlier, then you end up with complexity that's
order N, At every level of the tree. So together, the construction
time would be order N log N, because I have an order
N operation at each of, on the order of log N levels of the tree. Okay, so that's our construction time. But now we have to think about the
complexity of doing our nearest neighbor query and see if we get gains that offset
the cost of constructing this tree. Okay, so to begin with, the first thing
we have to do when we have a query point, remember, is we traverse all
the way down to a leaf node. So we're going to go all the way
down the depth of the tree. So that's order log N, because remember,
the depth is on the order of log N. And then we have to do this backtrack and
traverse and backtrack and traverse. And in the worst case, how many
different points do we have to consider? How many different nodes
do we have to visit? Well, how many nodes are there in total? They're on the order of N nodes. So, N nodes in the worst case. So the worst case being when, because of the structure of the problem
we're not able to prune anything at all. So the complexity range is anywhere
from on the order of log N, if we can do lots of pruning,
everything gets pruned, all the way to on the order of N,
if we can't do any pruning. Remember that order N was the same
complexity as our brute force search. So, if we're just going to do
a single nearest neighbor query and if we got really unlucky about
the structure of the data, or how we chose to construct the kd-tree. We might actually take a penalty
over a brute force search. But in some cases, as we're going to show, you can actually have
significant gains in efficiency. Okay, so under some assumptions
about the distribution of points. So things that don't look like that
really elegant circle that we had before. We can get things that have on the order
of log N number of queries that we have to do, or distance computations
per query that we're looking at. But the number of inspections we
have to do can be exponential in d, the number of dimensions. So for all the examples,
all the pictures we're showing are just two-dimensional examples I
think of two words in our vocabulary. But, we might be interested in
much higher dimensions, and k-d trees truthfully don't work
very well in high dimensions. And we're going to return to
this later in this course. [MUSIC]