Important: Please read the Qt Code of Conduct  https://forum.qt.io/topic/113070/qtcodeofconduct
Searching for nearest node in nary tree?

I've got a tree data structure. The tree is composed of
node
s, each like this:struct node { int x, y; QLineF edge; node* parent; QVector<node*> children; }
x
andy
represent the node coordinates,edge
is the link between the parent and the node itself,parent
is the node's parent andchildren
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 aQVector
in which I stored pointers to the nodes in the tree, and I simply iterated over the wholeQVector
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 theQVector
.
So, shall I keep theQVector
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.

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=YQs6ICvgmo
If u are interested in it.I would keep the the vector approach if the extra memory use is acceptable.

@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.