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.


migrated from stackoverflow.com Jan 2 '13 at 19:51

This question came from our site for professional and enthusiast programmers.

  • $\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 Jan 2 '13 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 Jan 2 '13 at 20:55

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.

  • 1
    $\begingroup$ for the $i^{th}$ child i would prefer $child(node, i)$, but thats a matter of taste $\endgroup$ – Simon S Jan 3 '13 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 Jan 3 '13 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 Jan 3 '13 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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