Searching for nearest node in n-ary tree?

alogim

I've got a tree data structure. The tree is composed of nodes, each like this:

struct node
{
  int x, y;
  QLineF edge;
  node* parent;
  QVector<node*> children;
}

x and y represent the node coordinates, edge is the link between the parent and the node itself, parent is the node's parent and children represent node's children.
The tree grows when my application runs, reaching dimensions of tenths of thousands of nodes. Now, my application generates a random node in a certain space and must find the nearest node in the tree. Each node may potentially have thousands of children.
At first I used a QVector in which I stored pointers to the nodes in the tree, and I simply iterated over the whole QVector to find the node that is the nearest to the generated one.
Then I changed approach and I now start from the root node and visit each children and so on to find the nearest node, by simply accessing the pointers.
In each case, anyway, I need to visit all the nodes since I do not know if the nearest node is the first one or the last one.

Using a QElapsedTimer tough, I noticed that this last approach is almost always much much slower than the simpler iteration over the QVector.
So, shall I keep the QVector approach? If, on one hand, it is faster, on the other hand it occupies more memory since it stores tenth of thousands of pointers to nodes.

mrjj

hi
When using only pointers it becomes sort of linked
list which can be slower in many cases with modern
hardware.
You could have a look on
https://www.youtube.com/watch?v=YQs6IC-vgmo
If u are interested in it.

I would keep the the vector approach if the extra memory use is acceptable.

kshegunov

@alogim
You're sort of naively using the simplest form of the tree data structure. If I understand your question correctly you should look at some BSP tree structure implementations, as they seem to suit your case quite well.