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
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.

Not the answer you're looking for? Browse other questions tagged .