アルゴリズムクイックリファレンス 第2版

10.5

 最近傍法

■

335

}

tree.setRoot(generate (1, maxD, points, 0, points.length-1));

return tree;

}

// points[left, right]

に対して

d

番目

(1 <= d <= maxD)

の次元の節点を生成する

private static DimensionalNode generate (int d, int maxD,

IMultiPoint points[],

int left, int right) {

//

やさしいケースをまず処理する

if (right < left) { return null; }

if (right == left) { return new DimensionalNode (d, points[left]); }

// array[left,right]

を並べ替え、

m

番目の要素が中央値となり、その前の要素はすべて

// <= median

であるようにする。これは整列していなくてもよい。

//

同様に、後の要素はすべて

>= median

となるが、これも整列している必要はない。

int m = 1+(right-left)/2;

Selection.select(points, m, left, right, comparators[d]);

//

この次元の中央の点が親となる

DimensionalNode dm = new DimensionalNode ...