C++에서 2 차원 kd 트리 생성 알고리즘 구현

Question

저는 C++에서 2 차원 kd 트리 생성 알고리즘을 구현하기 위해 개인 프로젝트를 진행하고 있습니다. 점의 수, 점 자체 (:
이미 이렇게 라이브러리가 알고 있지만 내가
프로그래밍 C++에서 경험을 쌓고 싶어

입력 (당신이 보여 개인 프로젝트가 있다면 이력서에 도움이됩니다) 입력을 명령 줄에서 읽을 수 있습니다.)

O (n log n) 시간에 실행하고 싶습니다. 이렇게하면 누군가가 의사 코드를 제공하여 시작할 수있게 도와줍니다. 미리 감사드립니다. .

Answer 1

저는 최근에 kd 나무로 놀아 왔습니다. 여기에 테스트되지 않은 코드가 있습니다. kd-tree 건설은 2 단계로 이루어집니다. 점 목록 O (n)을 탐색하고 각 차원 O (nlogn)을 따라 정렬합니다. 그래서, 네, O (nlogn) 시간에 kd-trees를 만들 수 있습니다.

트리를 통해 검색하면 (가장 가까운 이웃을 찾고 있다고 말하면서) 더 까다로워집니다. 나는 그것을 쉽게 이해할 수있는 문서를 찾지 못했습니다.

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)