Next: k-nomial tree functions, Previous: Floating-point functions, Up: Built-in functions [Contents][Index]

`n`-ary trees are used quite frequently in
communication patterns because they require only logarithmic time
(in the number of tasks) for a message to propagate from the root
to a leaf. coNCePTuaL supports `n`-ary trees in the form
of the `TREE_PARENT`

and
`TREE_CHILD`

functions.

- Function:
**TREE_PARENT***(*`task_ID`[,`fan-out`]) -
`TREE_PARENT`

takes a task number and an optional tree fan-out (*n*) and returns the task’s parent in an`n`-ary tree.*n*defaults to ‘`2`’, i.e., a binary tree. Taking the`TREE_PARENT`

of any task less than 1 returns the value ‘`-1`’.

- Function:
**TREE_CHILD***(*`task_ID`,`child`[,`fan-out`]) -
`TREE_CHILD`

takes a task number, a child number (*0 <= i < N*), and an optional tree fan-out (*n*), which again defaults to ‘`2`’. It returns the task number corresponding to the given task’s*child*th child.

The following illustrations show how tasks are numbered in, respectively, a 2-ary and a 3-ary tree:

As shown by the 2-ary tree, task 1’s
children are task 3 and task 4.
Therefore, ‘`TREE_PARENT(3)`’ and
‘`TREE_PARENT(4)`’ are both
‘`1`’; ‘`TREE_CHILD(1,
0)`’ is ‘`3`’; and,
‘`TREE_CHILD(1, 1)`’ is
‘`4`’. In a 3-ary tree, each task has three
children. Hence, the following expressions hold:

- ‘
`TREE_PARENT(7, 3)`’ ⇒ ‘`2`’ - ‘
`TREE_PARENT(8, 3)`’ ⇒ ‘`2`’ - ‘
`TREE_PARENT(9, 3)`’ ⇒ ‘`2`’ - ‘
`TREE_CHILD(2, 0, 3)`’ ⇒ ‘`7`’ - ‘
`TREE_CHILD(2, 1, 3)`’ ⇒ ‘`8`’ - ‘
`TREE_CHILD(2, 2, 3)`’ ⇒ ‘`9`’