Class FullyRecursiveBreadthFirstTraversal<TEdge, TNode>

A lazy, fully-recursive, breadth-first IVisitStrategy<TNode, TVisitContext> implementation, i.e. a traversing strategy which visits all the nodes at the current depth, along any path of the tree, before going deeper or shallower, exploring nodes with higher or lower depth.

Inheritance
System.Object
TreeTraversal<TEdge, TNode>
BreadthFirstTraversal<TEdge, TNode>
FullyRecursiveBreadthFirstTraversal<TEdge, TNode>
Implements
IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.RecImmTrees.Visitor
Assembly: MoreStructures.dll
Syntax
public class FullyRecursiveBreadthFirstTraversal<TEdge, TNode> : BreadthFirstTraversal<TEdge, TNode>, IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>> where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Type Parameters
Name Description
TEdge
TNode
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with tree of a "reasonable" height.

Methods

| Improve this Doc View Source

Visit(TNode)

Lazily and recursively visits the structure of the provided node, returning the sequence of IRecImmDictIndexedTreeNode<TEdge, TNode> of the structure, in breadth-first order.

Declaration
public override IEnumerable<TreeTraversalVisit<TEdge, TNode>> Visit(TNode node)
Parameters
Type Name Description
TNode node

The node on where to start visit the structure.
Returns
Type Description
IEnumerable<TreeTraversalVisit<TEdge, TNode>>

A sequence emitting (node, visit context) couples, in the visit order defined by the visit strategy.
Overrides
MoreStructures.RecImmTrees.Visitor.TreeTraversal<TEdge, TNode>.Visit(TNode)
Remarks

ALGORITHM
- The algorithm first lazily visits all nodes in structure in natural recursion/depth-first order, returning an instance of all nodes with their level in the structure.
- Then, it lazily sort and visit them level by level, according to TraversalOrder, yielding to the output sequence, so that the client code implementing the visitor can lazily process the nodes.

COMPLEXITY
- Excluding visitor, constant time work is done for each of the n nodes of the tree (such as destructuring of items and construction of the input record for the recursive call).
- Recursive traversal, as well as sorting, are lazily executed. Iteration-cost is constant w.r.t. n. ChildrenSorter cost depends on the actual algorithm used. When no sorting, Counting Sort or QuickSort is applied (respectively O(1), O(n), O(n * log(n)), the cost is tipically equalized or exceeded by sorting cost (see below).
- So Time Complexity is dominated by the two operations on the generated by the recursive traversal: sorting and visitor.
- Sorting done on the of all the n nodes retrieved during recursive traversal via the LINQ functionalities and .
- Visitor is client code invoked during iteration of the output sequence, containing each of the n nodes of the sorted .
- If the size of alphabet of elements of the tree is a small constant c, sorting could be done in linear time via Counting Sort. Otherwise, a comparison-based sorting takes at best a time proportional to n * log(n). However, LINQ sorting by and is QuickSort based, and has a O(n * log(n)) average runtime, with O(n^2) worst case.
In conclusion:
- Time Complexity is O(n * (log(n) + Ts)), where Ts is the amortized time cost of ChildrenSorter per node. Taking into account the visit of each emitted node, Time Complexity is O(n * (log(n) + Ts + Tv)), where Tv is the time cost of the visitor per node.
- Space Complexity is O(n). Taking into account the visit of each emitted node, Space Complexity is O(n * Sv), where Sv is the space cost of visitor per node.

Implements

Extension Methods