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.
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
b is the branching factor of your tree).
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:
Now, if you are dead set on having each node able to have N child nodes, here are some things you should thing about:
- 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.
- 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.
- Think about inserting and deleting nodes. If you spend more time here, you could save a lot more time later
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.
- What are some alternatives to recursive search algorithms?
- Entity Framework, Code First and Full Text Search
- What does this C# code with an "arrow" mean and how is it called?
- What are some examples of MemberBinding LINQ expressions?
- What are some clever uses of LINQ?
- This code returns distinct values. However, what I want is to return a strongly typed collection as opposed to an anonymous type
- What is the fastest way to search a List<T> across multiple properties?
- How do I speed up recursive search function?
- Calling fellow code nerds - Alternatives to Nested Loops?
- What is the best way to create strongly typed LINQ queries from some given strings, via reflection
- How much is too much data for and XML file, and what are some file based database alternatives?
- LINQ Source Code Available
- What are the alternatives to using Expand in a LINQ to ADO.net Data Service Query?
- What are some linq "best practices"
- .NET 4 Code Contracts: "requires unproven: source != null"
- What is the difference between ((IEnumerable)source).OfType<T>() and source as IEnumerable<T>
- At what point is a LINQ data source determined?
- What does the code query.Take(() => 1) do?
- How can I combine IObservable<T>.Throttle() with some other event source using Reactive Extensions?
- creating Linq to sqlite dbml from DbLinq source code
- What would be a reasonably fast way to code this sql query in c#?
- Running different code depending on what Net Framework version is installed
- what is equivalent c# code for following statement?
- How to convert this recursive code to Linq
- What can be the code for someIEnumerable.Select extension method?
- Linq recursive search nodes
- what does this .net line of code means
- Linq Recursive Search
- Search by zip code and filter list within specific radius?
- Usage recursive hierarchy tree structure in Linq query with multible tables and return some Json Value
- mutating the linq query to return the desired results
- Linq where closure with model list
- SQL queries in .NET
- XML Return parent node when searching children
- ASP.net Linq Query InvalidOperationException: The class '' has no parameterless constructor
- Linq ForEach - Returning cannot assign 'void' to an implicitly-typed local variable
- Extract derived elements from a list of base elements
- Convert SQL subquery to LINQ format which contains IN, DISTINCT keywords
- LINQ Query optimalisation using EF6
- Remove accents from string in LINQ loop - Ucommerce products
- How to search in generic list of ExpandoObject
- Building Expression Trees
- Fetch history of records using LINQ
- .Distinct() clause not working c# MVC
- Sampling a list with linq
- Insert LINQ Query Results Into DataTable
- Dynamic Column in Select Clause Issue
- How to filter child collections Entity Framework
- Update multiple entities in Entity Framework
- check that a specific user has specific permission in lightswitch