c++ - Predict the required number of preallocated nodes in a kD-Tree -

i'm implementing dynamic kd-tree in array representation (storing nodes in std::vector) in breadth-first fashion. each i-th non-leaf node have left child @ (i<<1)+1 , right child @ (i<<1)+2. support incremental insertion of points , collection of points. i'm facing problem determining required number of possible nodes incrementally preallocate space.

i've found formula on web, seems wrong:

n = min(m − 1, 2n − ½m − 1),

where m smallest power of 2 greater or equal n, number of points.

my implementation of formula following:

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

function nextpowerof2 returns power of 2 largest or equal n

any appreciated.

each node of kd-tree divides space 2 spaces. hence, number of nodes in kd-tree depends on how perform division:

1) if divide them in midpoint of space (that is, if space x1 x2, divide space x3=(x1+x2)/2 line), then: i) each point allocated own node, , ii) each intermediate node empty.

in case, number of nodes depend on how large coordinates of points are. if coordinates bounded |x|, total number of nodes in kd-tree should less log |x| * n (more precisely, around log |x| * n - n log n + 2n) in worst case. see this, consider following way add points: add multiple collections, each collection has 2 extremely nearby points located @ random. each pair of point, tree need continuously divide space log |x| times, , if log |x| larger log n, creating log |x| intermediate nodes in process.

2) if divide them using point dividing line, each node (including intermediate nodes) contain point. thus, total number of nodes n. however, note using point divide space may yield bad performance if points not given in random order (for example, if points given in ascending order of x, depth of tree o(n). comparison, depth of tree in (1) @ o(log |x|) ).