[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]