Implementing a quadtree using arrays

Question

I am trying to write code for simulating n-body problem using the Barnes-Hut tree algorithm. I plan on using CUDA in the future and thus want my quadtree data structure to not be composed of heap objects.

From the paper "An Efficient CUDA Implementation of the Tree-Based Barnes Hut n-Body Algorithm" by Martin Burtscher and Keshav Pingali (sorry couldn't find link) the authors state:

Dynamic data structures such as trees are typically built from heap objects, where each heap object contains multiple fields, e.g., child-pointer and data fields, and is allocated dynamically. Because dynamic allocation of and accesses to heap objects tend to be slow, we use an array-based data structure. Accesses to arrays cannot be coalesced if the array elements are objects with multiple fields, so we use several aligned scalar arrays, one per field, as outlined in Figure 6.6. As a consequence, our code uses array indexes instead of pointers to tree nodes.

I understand the part about aligned scalar arrays (i.e. SOA vs AOS idiom in parallel computing), but unfortunately the authors do not explain how one constructs the quadtree using arrays.

My question is how does one implement a quadtree data structure (with methods for inserting spacial points) using arrays? I know how to implement a quadtree in the traditional way using node structs and pointers for children etc. Can someone provide a reference that details how to do this using arrays. Even information on how to implement a binary tree (or any tree really) using arrays might be useful here.

Answer 1

Implementing a binary tree using array is really simple, firstly we are going to index the array from 1, i.e the root node is going to be 1, and then the

left child will be : leftChildIndex = 2 * parentIndex;

right child will be at : rightChildIndex = 2 * parentIndex + 1;

Now if one want to find the parent of current node : parentIndex = currIndex/2;

I have written a c++ code that does the preorder traversal of the tree :

#include<iostream>

using namespace std;

int binaryTree[20], lengthOfTree;
int leftChild(int idx){ return 2*idx; }
int rightChild(int idx){ return 2*idx+1; }
int parentIndex(int idx){ return idx/2; }

void traverseTree(int idx){
    if(idx >= lengthOfTree) return;
    cout << binaryTree[idx] << " ";
    traverseTree(leftChild(idx));
    traverseTree(rightChild(idx));
}

int main(){

    lengthOfTree = 15;
    for(int i = 1;i <= lengthOfTree;i++){
        cin >> binaryTree[i];  
    }
    traverseTree(1);
    cout << endl;

return 0;
}

Link to solution on Ideone : http://ideone.com/ZpTJCa

----------------------------------------------------------------------------

Indexing a quad tree might be a little more complex, so what we can do is again index the tree from 1, for each node we can find the level of that node, eg : the level of node 1 is 0, level of node 4 is 1, level of node 11 is 2.

pseudoCode for finding level : O(log n)

int findLevel(int nodeNo){
    int level = 0;
    int currNode = 1;
    while(currNode < nodeNo){
        currNode = currNode + pow(4, level++);
    }
    return level;
}

Similarly the leftmost node of the current level and the rightmost node of the currentlevel can be calculated using the above pseudocode, then to find the 4 children of the current node we can do :

1st child of current node : child1 = (rightmostNode - currentNode) + 4 * (currentNode - leftmostNode);

2nd child of current node : child2 = child1 + 1;

3rd child of current node : child3 = child2 + 1;

4th child of current node : child4 = child3 + 1;

Also you can create a mapping for finding the parent.

Answer 2

A quad tree, represented as an array is called a "Linear Quadtree". Using this term you will find some literature.

A paper from Hannan Samet recommends to first implement an application using a tradional quadtree, then check whether a linear quadtree approach will work. Not all applications can use a linear quadtree.

"(with methods for inserting spatial points)"

Such linear approaches often demand a static quad tree, that is one which does not change its content. Same applies for GPU applications, they demand a (huge) static data set, where millions of operations are executed. The access (uploading time) to the GPU is relative slow, so the type of the application should one where the most data will not change (for some time).