C#でkd-tree

眠れないので、C#でkd-treeを作ってたらこんな時間に...ﾃﾗｱﾎｽ

ちなみに、kd-treeとは2分木を構築するのでk次元空間をO(log n)、ワーストケースO(n)で探索可能なアルゴリズム。
うまくバランスのとれたツリーを作らないと効率がおちちゃうのが欠点。
でも、近傍の点を求め易いしアルゴリズム自体の実装も簡単なので個人的にはかなりオヌヌメ。

せっかくオブジェクト指向言語を使ってるのでそれっぽく簡単に扱えるように設計して実装してみたり...

List<Node> nodeList = new List<KDTree.Node>();
nodeList.Add(new Node(new double[]{2, 3}));
nodeList.Add(new Node(new double[]{5, 4}));
nodeList.Add(new Node(new double[]{9, 6}));
nodeList.Add(new Node(new double[]{4, 7}));
nodeList.Add(new Node(new double[]{8, 1}));
nodeList.Add(new Node(new double[]{7, 2}));

KDTree.Tree tree = new KDTree.Tree(nodeList);
tree.Build();

Console.WriteLine("Root = ({0},{1})", tree.Root.Vector[0], tree.Root.Vector[1]);

肝心のアルゴリズムのコードはこんな感じ↓

private Node Build(List<Node> nodeList, int depth)
{
    if (nodeList.Count == 0)
    {
        return null;
    }

    int k = nodeList[0].Vector.Length;
    int axis = depth % k;

    nodeList.Sort(delegate(Node n1, Node n2)
    {
        if (n1.Vector[axis] > n2.Vector[axis])
        {
            return 1;
        }
        else if (n1.Vector[axis] < n2.Vector[axis])
        {
            return -1;
        }

        return 0;
    });

    int median = nodeList.Count / 2;

    List<Node> leftNodeList = new List<Node>();
    List<Node> rightNodeList = new List<Node>();

    for (int i = 0; i < median; i++)
    {
        leftNodeList.Add(nodeList[i]);
    }

    for (int i = median + 1; i < nodeList.Count; i++)
    {
        rightNodeList.Add(nodeList[i]);
    }

    Node node = nodeList[median];
    node.LeftChild = Build(leftNodeList, depth + 1);
    node.RightChild = Build(rightNodeList, depth + 1);

    return node;
}