Реализовать алгоритм построения двумерного дерева kd в C ++ - PullRequest
Новая
       22

Реализовать алгоритм построения двумерного дерева kd в C ++

1 голос
/ 24 ноября 2010

Я работаю над личным проектом по реализации алгоритма построения двумерного дерева kd в C ++.
Я знаю, что есть библиотеки, которые уже делают это, но я хочу получить опыт программирования на C ++
(помогает при возобновлении, если у вас есть личные проекты для показа)

Ввод: количество точек и сами точки (ввод можно прочитать из командной строки)

Я хочу, чтобы это запускалось вO (n log n) раз, можно ли это сделать, если кто-то может предоставить какой-нибудь псевдокод, чтобы помочь мне начать, заранее спасибо.

1 Ответ

2 голосов
/ 24 ноября 2010

Я недавно играл с kd-деревьями.Вот некоторый непроверенный код.постройка kd-дерева в 2 этапа;обход списка точек O (n) и сортировка по каждому измерению O (nlogn).Итак, да, вы можете построить kd-деревья за O (nlogn).

Поиск по дереву (скажем, вы ищете ближайших соседей), хотя и становится сложнее.Я не нашел простой документации для этого. 

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)
...