Предскажите необходимое количество предварительно распределенных узлов в kD-дереве

Question

Я реализую динамическое kD-Tree в представлении массива (сохраняя узлы в std :: vector) в ширину. Каждый i-й нелистовой узел имеет левого ребенка в (i<<1)+1 и право ребенка в (i<<1)+2. Он будет поддерживать инкрементную вставку точек и сбор очков. Однако я столкнулся с проблемой определения необходимого количества возможных узлов для постепенного предварительного выделения пространства.

Я нашел formula on the web, который, как представляется неправильным:

N = мин (т - 1, 2n - ½m - 1),

где т является наименьшей степенью 2 больше или равно n, число точек .

Моя реализация формулы заключается в следующем:

size_t required(size_t n) 
{ 
    size_t m = nextPowerOf2(n); 
    return min(m - 1, (n<<1) - (m>>1) - 1); 
} 

функция nextPowerOf2 возвращает мощность 2 по величине или равной п

Любая помощь будет оценена.

Answer 1

Каждый узел kd-дерева делит пространство на два пробела. Следовательно, количество узлов в kd-дереве зависит от того, как вы выполняете это разделение:

1) Если вы разделите их в середине пространства (то есть, если пространство от x1 до x2, вы разделите пространство с линией x3 = (x1 + x2)/2), то: i) Каждая точка будет выделена собственным узлом, а ii) Каждый промежуточный узел будет пустым.

В этом случае количество узлов будет зависеть от того, насколько велики координаты точек. Если координаты ограничены | X |, то общее число узлов в kd-дереве должно быть немного меньше, чем log | X | * n (точнее, вокруг log | X | * n - n log n + 2n) в худшем случае. Чтобы увидеть это, рассмотрим следующий способ добавления точек: вы добавляете несколько коллекций, каждая коллекция имеет два чрезвычайно близких точки, расположенных наугад. Для каждой пары точек дерево необходимо будет непрерывно делить пространство log | X | раз, и если log | X | значительно больше, чем log n, создавая log | X | промежуточные узлы в процессе.

2) Если вы разделите их, используя точку в качестве разделительной линии, то каждый узел (включая промежуточные узлы) будет содержать точку. Таким образом, общее число узлов - просто n. Однако обратите внимание, что использование точки для разделения пространства может привести к очень плохой производительности, если точки не заданы в случайном порядке (например, если точки указаны в порядке возрастания X, глубина дерева будет O (n). Для сравнения, глубина дерева в (1) не превосходит O (log | X |)).