0
\$\begingroup\$

I've understood that KD tree split points using the median while cycling on each axis. I've also understood that at each node traversal, a nearest search must use a sphere to store to nearest neighbor (in case the query point is very close to the split median).

What I don't understand, is why median are always aligned with one point? Does that mean nodes are always storing one point? Does that mean each node can only have one point and 2 childs nodes ?

\$\endgroup\$
0

1 Answer 1

Reset to default
0
\$\begingroup\$

Because that's how binary trees work, of which kd-trees are a special case.

In a binary tree, each node has

  • exactly one value
  • 0-1 child-nodes carrying a smaller value
  • 0-1 child-nodes carrying a larger value

What sets kd-trees apart from normal binary trees is the way they decide what's "larger" and what's "smaller": The property which decides this cycles between tree levels.

The median of a node in a kd-tree is actually a coordinate of its value. You don't need an extra variable for this.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.