[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

## `combinat::trees` -- the domain of trees

#### Introduction

`combinat::trees` is the domain of Trees. It provides also functions for enumerating, generating, and manipulating trees.

#### Details

- A tree either consists of a single node, or is recursively constructed from an ordered list of trees by attaching them to a common ancestor node.

- The operands of a tree are its subtrees.

- Empty trees and subtrees are actually tolerated, so that `combinat::binaryTrees` can inherit from the data structure and methods of `combinat::trees`.

- The nodes of a tree always carry dummy labels, so that `combinat::labelledBinaryTrees` can inherit from the data structure and methods of `combinat::trees`. The 0-th operand of a tree is the label of its root node.

- For conversions to and from basic MuPAD expressions, a tree is encoded using a nested list of lists. The empty tree is encoded as an empty list, while a non-empty tree `t` is encoded as a list whose first operand is the label of the root node of `t`, while the other operands encodes respectively the subtrees of `t`.

- When a function uses a depth walk algorithm, the user can choose in which order the node are visited among
  - Prefix=LeftPrefix,
  - RightPrefix,
  - Infix=LeftInfix,
  - RightInfix,
  - Postfix=LeftPostfix,
  - RightPostfix.
  When no order is specified, the default order is LeftInfix. The meanings of these options are the following: Leftmeans that the subtrees are visited from left to right, and Rightfrom right to left. Prefixmeans that the node is visited before its subtrees, Postfixmeans it is visited after, while Infixmeans its is visited exactly after the first subtree.

#### Creating Elements

`combinat::trees(list)`

#### Parameters

`list` | - | A nested list representing the tree to be created.

#### Details

- ``combinat::trees`(list)` creates a new tree whose recursive structure is encoded by `list` (see the details above). The empty tree is encoded as an empty list, while a non-empty tree `t` is encoded as a list whose first operand is the label of the root node of `t`, while the other operands encodes respectively the subtrees of `t`.

#### Categories

`Cat::DecomposableClass`, `Cat::CombinatorialClass`

#### Related Domains

`combinat::binaryTrees`, `combinat::labelledBinaryTrees`, `combinat::decomposableObjects`

#### Entries

zero

The empty tree with zero nodes

one

The tree with one single node

dummyLabel

The dummy label which is used for unlabelled trees

#### Method size: size of a tree

- `size(tree t)`

- Returns the size of `t`, that is its number of nodes.

#### Method count: number of trees

- `count(nonnegative integer n)`

- Returns the number of trees of size `n`.

#### Method generator: generator for trees

- `generator(nonnegative integer n)`

- Returns a generator for the trees of size `n`.

#### Method list: list of the trees

- `list(nonnegative integer n)`

- Returns the list of trees of size `n`.

#### Method unrank: unranking of a tree

- `unrank(nonnegative integer n, nonnegative integer i)`

- Returns the i-th tree of size `n`.

#### Method random: random tree

- `random(nonnegative integer n)`

- Returns a random tree of size `n`.

#### Method nops: number of operands of a tree

- `nops(tree t)`

- Returns the number of operands of `t`, that is its number of subtrees.

#### Method op: operands of a tree

- `op(tree t)`
- `op(tree t, nonnegative integer i)`
- `op(tree t, nonnegative range i..j)`
- `op(tree t, [i1, i2, ...])`

- Returns a sequence of operands, or the requested operand, or FAIL if no corresponding operand exists.

#### Method subsop: replace operands of a tree

- `subsop(tree t, i=new)`

- Returns a copy of `t` in which the `i`-th operand is replaced by the value `new`. It can be used either to change a subtree if `i`>0 or to change the label of the root if `i`=0.

- `subsop(tree t, i1=new1, i2=new2, ...)`

- Returns a copy of `t` with several operands replaced at once.

#### Method _index: indexed access

- t[i]
- `_index(tree t, nonnegative integer i)`

- Returns the i-th operand of `t` or FAIL if no corresponding operand exists.

#### Method set_index: indexed assignment

- t[i] := new
- `set_index(tree t, nonnegative integer i, new)`

- Sets the `i`-th operand of `t` to `new`. Returns `new` in the first form, and the modified `t` in the second form.

#### Method convert: conversion of an list into a tree

- `convert(list l)`

- Returns the tree whose structure is encoded in the list `l`. Convert is called by the constructor an behaves identically.

#### Method expr: conversion of a tree into an expression

- `expr(tree t)`

- Returns a list which encodes the structure of `t`, and can be fed back into the constructor. Thus `convert(expr(t))` is always equal to `t`, when `t` is a tree.

#### Method print: pretty printing of a tree

- `print(tree t)`

- Returns a `output::asciiArt` representation of `t` suitable for basic 2D pretty printing. The labels are not printed.

#### Method revert: reverse of a tree

- `revert(tree t)`

- Returns the reverse tree of `t` obtained by reverting the order of the subtrees of `t`, and reverting those recursively.

#### Method shape: shape of a tree

- `shape(labelled tree t)`

- Returns the shape of a labelled tree, that is the unlabelled tree obtained by removing all labels.

#### Method toWord: word from a tree

- `toWord(tree t, order p)`

- Returns the list of the labels of a tree by reading in a depth walk the nodes of the tree in a specified order. This order can be: LeftPrefix=Prefix, RightPrefix, LeftPostfix=Postfix, RightPostfix, LeftInfix=Infix, RightInfix. The defaut order is Prefix.

#### Method fromShapeAndWord: filling of a tree

- `fromShapeAndWord(tree t, word w, order p)`

- Label the node of the tree `t` with the element of the word `w`. This returns the tree of the same shape as t, which reading over order p gives w back. The length of the word `w` must be equal to the number of nodes of `t`.

#### Method toPoset: converting a tree into a partially ordered set.

- `toPoset(tree t)`

- Returns the partially ordered set encoded by the structure of `t`, that is return an element of `Graph`, whose vertices are the nodes of the tree and whose edges are the branches of the tree. This can only be done if the labels of the nodes of the tree are distinct.

#### Example 1

One computes the list all the trees on 0 to 5 nodes writing:

    >> for i from 0 to 5 do
         print(combinat::trees::list(i))
       end_for

                                        []

                                        [o]

                                         o
                                        [|]

                                   --  o   o --
                                   |  / \, |  |
                                   --      | --

                            --                     o --
                            |   o    o    o    o   |  |
                            |  /|\, / \, / \,  | , |  |
                            --        |  |    / \  | --

          --                          o                     o
          |    o     o    o    o     / \   o    o      o   / \   o
          |  // \\, /|\, /|\, /  \ ,   |, /|\, / \,  /  \, |  ,  | ,
          |           |   |     / \    |  |    | |  / \    |    /|\
          --

              o    o    o   o --
              |    |    |   |  |
             / \, / \,  | , |  |
               |  |    / \  |  |
                            | --

If one wants to run through the trees of a given size, one can generate the trees one by one to save memory:

    >> g:=combinat::trees::generator(4):
       g(); g(); g(); g(); g(); g();

                                         o
                                        /|\

                                         o
                                        / \
                                          |

                                         o
                                        / \
                                        |

                                         o
                                         |
                                        / \

                                         o
                                         |
                                         |
                                         |

                                       FAIL

If one wants direct access to the i-th tree of size n, it is possible in the following way:

    >> combinat::trees::unrank(2,4);

                                         o
                                        / \
                                          |

To make statistics on general trees or to test some conjectures on the shapes of trees with a large number of nodes, one can use:

    >> combinat::trees::random(91)

               o
             / |   \
             |  // |            \                                     \
             |    / \     /       \
            / \   | |///// \\\\\ /  \
            |     |    | |          |
            |            |          |
                                    |
                                   /                           \
                                     /  /                       \   \
                                      // \   \                      |
                                       |  ///  \             \\   /  \
                                          |    |              |   |
                                              /          \       / \
                                                /        |  \    |
                                                 /   /    \\
                                                 |   |
                                                     |
                                                     |
                                                   / | \
                                                  /|\| |
                                                      /|\

#### Example 2

The structure of a tree is encoded as a list of lists. To construct a tree from a list, one can use both:

    >> combinat::trees([1,[1],[1,[1],[1]]]);
       combinat::trees::new([1,[1],[1,[1],[1]]]);
       combinat::trees::convert([1,[1],[1,[1],[1]]])

                                        o
                                       /  \
                                         / \

                                        o
                                       /  \
                                         / \

                                        o
                                       /  \
                                         / \

To recover the list-format of a tree from its drawing, one uses:

    >> combinat::trees::expr(%)

                              [1, [1], [1, [1], [1]]]

#### Example 3

Let us compute some simple statistics on a given tree:

    >> treetmp:=combinat::trees([1, [1, [1]], [1, [1], [1], [1]]])

                                        o
                                       /  \
                                       | /|\

The size, number of operands and operands are respectively:

    >> combinat::trees::size(treetmp);
       combinat::trees::nops(treetmp);
       combinat::trees::op(treetmp)

                                         7

                                         2

                                      o   o
                                      |, /|\

#### Example 4

Change the shape of a tree:

    >> treetmp  := combinat::trees([1, [1, [1]], [1, [1], [1], [1]]]);
       treetmp2 := combinat::trees::subsop(treetmp,
                   1=combinat::trees([1,[1],[1]]));
       treetmp2[1]

                                        o
                                       /  \
                                       | /|\

                                         o
                                       /   \
                                      / \ /|\

                                         o
                                        / \

Change the shape of the tree using another way:

    >> treetmp3:=treetmp; treetmp3[1]:=combinat::trees([1,[1],[1]]);
       bool(treetmp2=treetmp3)

                                        o
                                       /  \
                                       | /|\

                                         o
                                        / \

                                       TRUE

#### Example 5

To recursively revert the subtrees of a tree (making the mirror image of this tree), one uses:

    >> tree:=combinat::trees([1, [1], [1, [1], [1, [1], [1], [1, [1]]], [1]]]);
       combinat::trees::revert(tree)

                                       o
                                      /   \
                                        / | \
                                         /|\
                                           |

                                           o
                                        /   \
                                      / | \
                                       /|\
                                       |

#### Example 6

To compute a special reading of a tree, one can use:

    >> valtree:=combinat::trees([6,[3,[1,[],[2]],[5,[4],[]]],[8,[7],[10,[9]]]]);
       combinat::trees::toWord(valtree,Infix);
       combinat::trees::toWord(valtree,RightPostfix);

                                          o
                                       /    \
                                     /   \ / \
                                      \ /    |

                          [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

                          [9, 10, 7, 8, 4, 5, 2, 1, 3, 6]

#### Example 7

To associate with each node of a given tree a value, thanks to a following order, one uses:

    >> valtree := combinat::trees([1,[1,[1,[],[1]],[1,[1],[]]],
                  [1,[1],[1,[1]]]]);
       valb := combinat::trees::fromShapeAndWord(valtree,
               [8,4,1,7,9,5,3,10,2,6],Postfix);
       combinat::trees::toWord(valb,Postfix);

                                          o
                                       /    \
                                     /   \ / \
                                      \ /    |

                                          o
                                       /    \
                                     /   \ / \
                                      \ /    |

                          [8, 4, 1, 7, 9, 5, 3, 10, 2, 6]

#### Background

- Unlike most combinatorial domains `combinat::trees` is not a facade domains.

- Empty trees and subtrees are actually tolerated, so that `combinat::binaryTrees` can inherit from the data structure and methods of `combinat::trees`.

- The nodes of a tree always carry dummy labels, so that `combinat::labelledTrees` (in construction) can inherit from the data structure and methods of `combinat::trees`. The 0-th operand of a tree is the label of its root node.

#### Super-Domain

`combinat::trees`

#### Axioms

`Ax::normalRep` `Ax::canonicalRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package