0
$\begingroup$

I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to set notation conventions that will not drive other people insane. The primary difference is that this algorithm makes use (logically) of tree data structures while the traditional algorithms in the field have used linear arrays.

The old algorithms therefore could denote specific data as $data_i$ (that is, using LaTex subscripts. Similarly, one could refer to $data_{i-1}$, and it would be clear that that is the "parent" data to $data_i$. Unfortunately, trees do not support this sort of indexing.

Are there any notation conventions for trees that allow clear, concise descriptions of that sort? I want to be able to give talk about an arbitrary bit of data (i.e. $data_i$) and readily discuss parent and child data. The community is mathematician heavy and as such mathematical notation of the sub/superscript y operator sort is favored over the class.property CS style. Note also that these are arbitrary trees; they need not be binary or any other such structure.

Does anyone know of a notation convention that would fit the bill? Alternatively, is there a better place to ask this? Thanks for the help.

Improve this question
$\endgroup$
2
  • $\begingroup$ What kind of tree structure? Are there values in the nodes? Are there values in the leaves? Does the tree have a fixed arity (e.g. binary tree)(as opposed to a rose tree)? Are there any other structural invariants (balanced)? $\endgroup$
    – Tinctorius
    Commented Jan 2, 2013 at 19:22
  • $\begingroup$ As the question says "Note also that these are arbitrary trees; they need not be binary or any other such structure." All nodes/leaves in the tree have values. The current implementation of the algorithm features several trees with identical structures but different sets of data. Some trees contain floats at each node, while others feature an large object at each node. $\endgroup$
    – Ethan Van Andel
    Commented Jan 2, 2013 at 20:55

1 Answer 1

Reset to default
2
$\begingroup$

You can use functions.

Let $node$ be an arbitrary node of the tree.

Then $data(node)$ is data associated with $node$, $children(node)$ is set of child nodes of $node$ and $parent(node)$ is parent of $node$.

For data associated with $i^{th}$ child of $node$ you can use $data(children(node)_i)$ etc.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ for the $i^{th}$ child i would prefer $child(node, i)$, but thats a matter of taste $\endgroup$
    – Simon S
    Commented Jan 3, 2013 at 0:42
  • $\begingroup$ Is this an established convention? It's similar to what I was considering, but if there are conventions of which I am unaware, I'd like to respect them. $\endgroup$
    – Ethan Van Andel
    Commented Jan 3, 2013 at 0:56
  • 2
    $\begingroup$ It doesn't matter if it is an established or not. If it is good it will establish itself. :) $\endgroup$
    – Pratik Deoghare
    Commented Jan 3, 2013 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.