Searching for nearest node in n-ary tree?
-
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; }xandyrepresent the node coordinates,edgeis the link between the parent and the node itself,parentis the node's parent andchildrenrepresent 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 aQVectorin which I stored pointers to the nodes in the tree, and I simply iterated over the wholeQVectorto 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
QElapsedTimertough, I noticed that this last approach is almost always much much slower than the simpler iteration over theQVector.
So, shall I keep theQVectorapproach? 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=YQs6IC-vgmo
If u are interested in it.I would keep the the vector approach if the extra memory use is acceptable.
-
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; }xandyrepresent the node coordinates,edgeis the link between the parent and the node itself,parentis the node's parent andchildrenrepresent 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 aQVectorin which I stored pointers to the nodes in the tree, and I simply iterated over the wholeQVectorto 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
QElapsedTimertough, I noticed that this last approach is almost always much much slower than the simpler iteration over theQVector.
So, shall I keep theQVectorapproach? 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.
