score:1

Accepted answer

Maybe you want to look into an alternative data index structure: Here

It always depends on the work you are doing with the data, but if you assign a unique ID on each element that stores the hierarchical form, and creating an index of what you store, your optimization will make much more sense than micro-optimizing parts of what you do.

Also, this also lends itself a very different paradigm in search algorithms, that uses no recursion, but in the cost of additional memory for the IDs and possibly the index.

score:1

If you must visit all leaf nodes, you cannot speed up the search: it is going to go through all nodes no matter what. A typical trick played to speed up a search on trees is organizing them in some special way that simplifies the search of the tree. For example, by building a binary search tree, you make your search O(Log(N)). You could also store some helpful values in the non-leaf nodes from which you could later construct the answer to your search query.

For example, you could decide to store the _bestLeaf "pointing" to the leaf with the highest _nodeDelta of all leaves under the current subtree. If you do that, your search would become an O(1) lookup. Your inserts and removals would become more expensive, however, because you would need to update up to Log-b(N) items on the way back to root with the new _bestLeaf (b is the branching factor of your tree).

score:1

I think the first thing you should think about is maybe going away from the N-Tree and going to as Binary Search tree.

This means that all nodes have only 2 children, a greater child, and a lesser child.

From there, I would say look into balancing your search tree with something like a Red-Black tree or AVL. That way, searching your tree is O(log n).

Here are some links to get you started:

http://en.wikipedia.org/wiki/Binary_search_tree http://en.wikipedia.org/wiki/AVL_tree http://en.wikipedia.org/wiki/Red-black_tree

Now, if you are dead set on having each node able to have N child nodes, here are some things you should thing about:

  1. Think about ordering your child nodes so that you can quickly determine which has the highest leaf number. that way, when you enter a new node, you can check one child node and quickly determine if it is worth recursively checking it's children.
  2. Think about ways that you can quickly eliminate as many nodes as you possibly can from the search or break the recursive calls as early as you can. With the binary search tree, you can easily find the largest leaf node by always only looking at the greater child. this could eliminate N-log(n) children if the tree is balanced.
  3. Think about inserting and deleting nodes. If you spend more time here, you could save a lot more time later

score:0

As others mention, a different data structure might be what you want.

If you need to keep the data structure the same, the recursion can be unwound into loops. While this approach will probably be a little bit faster, it's not going to be orders of magnitude faster, but might take up less memory.


Related Articles