Class SuffixTreeNode.Leaf

Builds a leaf, i.e. a node with no children and the start index of the suffix in the text.

Inheritance
System.Object
SuffixTreeNode
SuffixTreeNode.Leaf
Implements
System.IEquatable<SuffixTreeNode>
System.IEquatable<SuffixTreeNode.Leaf>
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)
Namespace: MoreStructures.SuffixTrees
Assembly: MoreStructures.dll
Syntax
public class Leaf : SuffixTreeNode, ISuffixStructureNode<SuffixTreeEdge, SuffixTreeNode>, IRecImmDictIndexedTreeNode<SuffixTreeEdge, SuffixTreeNode>, IEquatable<SuffixTreeNode>, IEquatable<SuffixTreeNode.Leaf>

Constructors

| Improve this Doc View Source

Leaf(Int32)

Builds a leaf, i.e. a node with no children and the start index of the suffix in the text.

Declaration
public Leaf(int LeafStart)
Parameters
Type Name Description
System.Int32 LeafStart

Properties

| Improve this Doc View Source

LeafStart

Declaration
public int LeafStart { get; set; }
Property Value
Type Description
System.Int32

Methods

| Improve this Doc View Source

IsEquivalentTo(SuffixTreeNode, TextWithTerminator[])

Determines whether this SuffixTreeNode structure is equivalent to the provided other structure, w.r.t. the provided texts.

Declaration
public override bool IsEquivalentTo(SuffixTreeNode other, params TextWithTerminator[] texts)
Parameters
Type Name Description
SuffixTreeNode other

The other tree, to compare this tree against.
TextWithTerminator[] texts

The text, based on which to evaluate the tree equivalence.
Returns
Type Description
System.Boolean

True if the two trees are equivalent for the provided text, false otherwise.
Overrides
Remarks

DEFINITION
The definition of SuffixTreeNode structures equivalence depends on (a list of) TextWithTerminator: two trees can be equivalent for some texts, and not equivalent for others. This is because of the Edge Compression technique used by SuffixTreeEdge, to store edges in O(1) space, instead of O(n).
Moreover, equivalence is based on the equivalence of edges and of the specific type of node.
- Two SuffixTreeEdge E1 and E2 are equivalent w.r.t. a TextWithTerminator T, if the string identified by each edge is the same: T[E1] == T[E2].
- Two SuffixTreeNode.Leaf L1 and L2 are equivalent if their LeafStart is the same: L1.LeafStart == L2.LeafStart.
- Two SuffixTreeNode.Intermediate I1 and I2 are equivalent if there is a 1-to-1 correspondence between children edges and child nodes pointed by such edges are equivalent: for each edge e1 of I1.Children there exists exactly one equivalent edge e2 of I2.Children and I1.Children[e1] is equivalent to I2.Children[e2] w.r.t. T.

COMPLEXITY
- Checking for edges equivalence is a O(n) operation, where n is the number of nodes in the tree, since it requires decompressing the labels of each of the edges being compare and compare for equality the two resulting O(n) strings.
- Checking for leaves equivalence is a O(1) operation, since it only requires comparing LeafStart, which has constant size.
- Checking for intermediate nodes equivalence is a O(n) operation, amortized cost over the total number of edges in the tree, since there are O(n) edges in total in the tree, an edge is visited multiple times but always in the context of a single node, and the node equivalence check requires looking for the equivalent edge.
- In conclusion Time Complexity is O(n^2) and Space Complexity is O(n).

Implements

System.IEquatable<T>
System.IEquatable<T>

Extension Methods