CODEWITHSUNDEEP
arraysalgorithmdata-structuresgraphicstree
user1855952
user1855952

Reputation: 1575

KDTree implementation as single array / without nodes

So for a project I've implemented a balanced KD-Tree and k-nearest neighbors search algorithm for it the "traditional" way as a standard tree - i.e. I have node structs like the following

struct KDNode{
    int level; //used for x,y,z axis splitting
    Point pos;
    KDNode *left, *right; //Child nodes
}

...and then store the tree in memory as an actual tree data structure. However, I recently heard that it is possible to store a KD-Tree in memory as a large array without having to create any node objects and that this method of construction would be much more efficient memory wise and time-performance wise.

However, I'm not at all sure how such a construction would work and cannot find anything online detailing exactly how I would go about implementing a KD-Tree this way.

So my question is, how would one go about implementing a KD-Tree as a single-dimensional array without the use of nodes?

Upvotes: 5

Views: 2770

Answers (2)

Justin
Justin

Reputation: 4216

Well, I could see how it could be implemented in single array. But it would require a fairly densely filled and well balanced kd-tree. If your tree is sparse it could be implemented with an array but it would be fairly wasteful in terms of space.

You can use the same technique they use to implement a heap in an array. There is a formula to find the children of an item using the items current index, more info here and here. The formula is 2*index+1 for left child and 2*index+2 for the right child.

This "heap as an array" could be applied to any binary-tree data structure but it particularly useful with a heap since you know the array will be densely filled.

Complete binary tree with index values in node:

               [0]
      [1]                [2]
  [3]     [4]       [5]       [6]  
[7] [8] [9] [10] [11] [12] [13] [14]

Same representation in an array: [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

If you are at [4] and want to find it's children; it's left child is (2*4+1) 9 and it's right child is (2*4+2) 10.

Upvotes: 7

Cybercartel
Cybercartel

Reputation: 12592

You can reduce the dimension with a space filling curve at some costs. Use a quadkey to search for nearest-neighbor.

Upvotes: 2

Related Questions