C++で2次元kdツリー構築アルゴリズムを実装する

Question

私はC++で2次元kdツリー構築アルゴリズムを実装するための個人プロジェクトを進めています。ポイント数、及びポイントそのもの（：
私はすでにこれを行うライブラリがある知っているが、私は
プログラミングC++での経験を積みたい

入力（あなたが表示する個人的なプロジェクトを持っている場合は、再開するのに役立ちます）入力をコマンドラインから読み込むことができます）

私はこれをO（n log n）時間で実行したいと思います。そうすれば誰かが擬似コードを提供してくれます。 。

Answer 1

私は最近kd-treesで遊んでいます。ここにいくつかのテストされていないコードがあります。 kd-tree構築は2段階で行われます。点のリストをたどり、O（n）、各次元に沿ってソートする、O（nlogn）。ですから、O（nlogn）時にkd木を構築することができます。

ツリーを検索して（最近隣のものを探していると）、やっかいです。私はそのための簡単な文書を見つけることができませんでした。

struct Node 
{ 
    int[2] point; 
    Node* left; 
    Node* right; 
} 

Node* createtreeRecursive (int** values /* int[2][len] */, int len, int dim = 2, int depth = 0) 
{ 
    // If empty, return 
    if (value <= 1) return null; 

    // Get axis to split along 
    int axis = depth % dim; 

    int** sorted = sortAlongDim (values, axis); 

    int mid = len/2; 
    Node* curr = new Node(); 
    curr.point[0] = sorted [0][mid]; 
    curr.point[1] = sorted [1][mid]; 

    int** leftHalf = values; 
    int** rightHalf = &(values [mid]); 

    curr.left = createtreeRecursive (leftHalf, mid, dim, depth + 1); 
    curr.right = createtreeRecursive (rightHalf, len - mid, dim, depth + 1); 

    return curr; 
} 

int** sortAlongDim (int** values, int axis)