C#でkd-tree - KAWATAN.NETC#でkd-treeを作ってたみたー ちなみに、kd-treeとは2分木を構築するのでk次元空間をO(log n)、ワーストケースO(n)で探索可能なアルゴリズム。 2分木の作り方はまず、適当な点を選んで、そこから2次元空間ならx軸に平行になるように空間を分割。分割された空間の中からまた適当に点を選んで次はy軸で分割。今度はx軸で分割...というのを点がなくなるまで繰り返すと出来上がり。 このアルゴリズムは、うまくバランスのとれたツリーを作らないと効率がおちちゃうのが欠点。 でも、近傍の点を求め易いしアルゴリズム自体の実装も簡単なのでオヌヌメ。 [C#] namespace KDTree { public class Node { private Node leftChildNode; private Node rightChildNod
