Skip to main content
added 63 characters in body
Source Link
Philipp
  • 123k
  • 28
  • 264
  • 344

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

With aWhat sets kd-tree, which property oftrees apart from normal binary trees is the value definesway they decide what's "larger" orand what's "smaller" alternates: The property which decides this cycles between tree levels.

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

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

With a kd-tree, which property of the value defines "larger" or "smaller" alternates between tree levels.

The median of a node in a kd-tree is actually the coordinate of its value.

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.

Source Link
Philipp
  • 123k
  • 28
  • 264
  • 344

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

With a kd-tree, which property of the value defines "larger" or "smaller" alternates between tree levels.

The median of a node in a kd-tree is actually the coordinate of its value.