Package org.ddogleg.nn.alg

Class KdTree

java.lang.Object

org.ddogleg.nn.alg.KdTree

public class KdTree
extends Object

K-D Tree is short for k-dimensional tree and is a binary tree data structure used for quickly finding the nearest-neighbor of a k-dimensional point in a set. Each point can optionally have data associated with it. The tree is structured such that at each node has a point and two children. All points in the set with values <= to the node's point in the specified dimension/axis are on the the left and >= to the right. A leaf will have no children.

NOTE: If multiple points have identical values then there will be a node for each point.

NOTE: If there is more than one point with an identical value to the node's point, then the identical points can go in either the left or right branches.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	KdTree.Node	Data type for each node in the binary tree.

Field Summary

Fields

Modifier and Type	Field	Description
int	N
@Nullable KdTree.Node	root

Constructor Summary

Constructors

Constructor	Description
KdTree()
KdTree(int N)	Specifies the type of points it can process.

Method Summary

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

N

public int N

root

@Nullable
public @Nullable KdTree.Node root

Constructor Details

KdTree

public KdTree(int N)

Specifies the type of points it can process.

Parameters:

N - Number of elements in a point

KdTree

public KdTree()