)combinat::trees – ordered trees
combinat::trees is the domain of ordered trees. It provides functions for enumerating, generating, and manipulating ordered trees.
Creating Elements
combinat::trees(list)
Parameters:
|
list: |
A nested list representing the tree to be created. |
Superdomain
combinat::trees
Categories
Cat::DecomposableClass, Cat::CombinatorialClass
Axioms
Ax::normalRep, Ax::canonicalRep
Related Domains:
combinat::binaryTrees, combinat::decomposableObjects, combinat::labelledBinaryTrees
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 (possibly dummy) labels. This way, various kinds of labelled trees (in particular 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. Nodes without labels are emulated by using a dummy label; see "dummyLabel".
When a function uses a depth-first 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: Left means that the subtrees are visited from left to right, and Right from right to left. Prefix means that the node is visited before its subtrees, Postfix means it is visited after, while Infix means its is visited exactly after the first subtree.
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 encode respectively the subtrees of t.
This encoding is somewhat verbose, but is very flexible to accommodate all kinds of trees (say with labels on leaves, but not on internal nodes, or the converse).
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 |
size – size of a tree
combinat::trees::size(tree t)
Returns the size of t, that is its number of nodes.
count – number of trees
combinat::trees::count(nonnegative integer n)
Returns the number of trees of size n.
generator – generator for trees
combinat::trees::generator(nonnegative integer n)
Returns a generator for the trees of size n.
list – list of trees
combinat::trees::list(nonnegative integer n)
Returns the list of trees of size n.
unrank – unranking of a tree
combinat::trees::unrank(nonnegative integer n, nonnegative integer i)
Returns the i-th tree of size n.
random – random tree
combinat::trees::random(nonnegative integer n)
Returns a random tree of size n.
Access Methods
nops – number of operands of a tree
combinat::trees::nops(tree t)
Returns the number of operands of t, that is its number of subtrees.
op – operands of a tree
combinat::trees::op(tree t)
combinat::trees::op(tree t, nonnegative integer i)
combinat::trees::op(tree t, nonnegative range )
combinat::trees::op(tree t, [
])
Returns a sequence of operands, or the requested operand, or FAIL if no corresponding operand exists.
select – select operands
combinat::trees::select(tree t, function f, <p1, p2, 
>)
Returns a copy of t with all its subtrees removed that do not satisfy the criterion defined by the function f.
map – apply a function to all operands
combinat::trees::map(tree t, function f, <p1, p2, 
>)
Returns a copy of t with f applied to all its subtrees.
The return value of f should always be a valid tree. This is not checked!
mapLabels – apply a function to all labels
combinat::trees::mapLabels(tree t, function f, <p1, p2, 
>)
Returns a copy of t with f applied to all its non dummy labels.
append – append new operands
combinat::trees::append(tree t, <t1, t2, 
>)
Returns a copy of t with the subtrees t1, t2, Symbol::hellip appended to the right of its existing subtrees
subsop – replace operands of a tree
combinat::trees::subsop(tree t, i = new)
combinat::trees::subsop(tree t, i1 = new1, i2 = new2, 
)
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 
or to change the label of the root if 
.
Returns a copy of t with several operands replaced at once.
_index – indexed access
combinat::trees::_index(tree t, nonnegative integer i)
Returns the i-th operand of t or FAIL if no corresponding operand exists.
set_index – indexed assignment
combinat::trees::set_index(tree t, nonnegative integer i, tree new)
Sets the i-th operand of t to new. Returns new in the first form, and the modified t in the second form.
Conversion Methods
convert – conversion of a nested list into a tree
combinat::trees::convert(list l)
Returns the tree whose structure is encoded in the list l. Convert is called by the constructor an behaves identically.
toList – conversion of a tree into a nested list
combinat::trees::toList(tree t)
Returns a nested list which encodes the structure of t, and can be fed back into the constructor. Thus convert(dom::toList(t)) is always equal to t, when t is a tree.
expr – convert into an element of a basic domain
combinat::trees::expr(tree t)
Converts t into a nested list, such that all sub-objects are elements of basic domains as well.
Unlike toList, labels are also converted to expressions.
print – pretty printing of a tree
combinat::trees::print(tree t)
Returns a output::asciiArt representation of t suitable for basic 2D pretty printing.
Technical Methods
revert – reverse of a tree
combinat::trees::revert(tree t)
Returns the reverse tree of t obtained by reverting the order of the subtrees of t, and reverting those recursively.
shape – shape of a tree
combinat::trees::shape(labelled tree t)
Returns the shape of a labelled tree, that is the unlabelled tree obtained by removing all labels.
toWord – word from a tree
combinat::trees::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.
fromShapeAndWord – filling of a tree
combinat::trees::fromShapeAndWord(tree t, word w, order p)
Label the nodes of the tree t with the elements 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.
toPoset – converting a tree into a partially ordered set.
combinat::trees::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.
toNonCrossingPartition – bijection to non crossing partitions
combinat::trees::toNonCrossingPartition(tree t)
Returns the non-crossing set partition corresponding to the tree t by the standard bijection.
See also combinat::nonCrossingPartitions and combinat::trees::fromNonCrossingPartition
Details: given a tree of size 
(in fact a forest of size 
), one gets a non crossing partition by labelling its nodes with 
in prefix order, and returning the set partition on 
induced by the relation "being sibling".
For the empty tree, the empty non crossing set partition is returned, which breaks the bijection. We might want to raise an error instead.
Complexity: 
.
fromNonCrossingPartition – bijection from non crossing partitions
combinat::trees::fromNonCrossingPartition(non crossing set partition p)
Returns the tree corresponding to the non crossing set partition p by the standard bijection.
See also combinat::nonCrossingPartitions and combinat::trees::toNonCrossingPartition
Complexity: 
because the parts of the partition are not sorted.
One computes the list all the trees on 
to 
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 all trees of a given size, one can generate them one by one to save memory:
g:=combinat::trees::generator(4):
g(); g(); g(); g(); g(); g();
o
/|\
o
/ \
|
o
/ \
|
o
|
/ \
o
|
|
|
The i-th tree of size n can be obtained directly as follow:
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
/| \
| // | \ \
| / \ / \
/ \ | |/////\\\\\/ \
| | | | |
| | |
|
/ \
/ / \ \
//\ \ |
| /// \ \\ / \
| | | |
/ \ / \
/ | \|
/ / \\
| |
|
|
/ | \
/|\| |
/|\
The structure of a tree is encoded as a list of lists. Nodes without label are emulated using a dummy label. To shorten the notations, we define an alias for this dummy label:
alias(d = combinat::trees::dummyLabel):
Now, to construct a tree from a list, one can use both:
combinat::trees([d,[d],[d,[d],[d]]]);
combinat::trees::new([d,[d],[d,[d],[d]]]);
combinat::trees::convert([d,[d],[d,[d],[d]]])
o
/ \
/\
o
/ \
/\
o
/ \
/\
To recover the list-format of a tree, one uses:
combinat::trees::expr(%)
As a syntactic sugar, the brackets may be omitted around the labels of inner leaves:
combinat::trees([d, d, [d, d, d]]);
o
/ \
/\
It is advised not to use this feature in programs; indeed, labels which are themselves lists will be misinterpreted as encoding subtrees.
The pretty printing of large trees like the random one of example 1 is far from perfect. Well, with ASCII art drawing all one can hope for is to give a rough idea of the general shape of the tree. Still, in principle the drawing should be unambiguous, at least for unlabelled trees. For example, can you tell the difference between the two following trees?
combinat::trees([d,[d,[d,[],[d,[],[d,d,[]]]], [d,[d,d, d]]]]);
combinat::trees([d,[d,[d,[],[d,[],d ]], [d,[d,[d,d,[]],d]]]]);
o
|
/ \
\ |
\/ \
/
o
|
/ \
\ |
\ / \
/
Of course, in case of ambiguous output, it is always possible to check the internal data structure, or the list-form of the tree. In the long term, it is also planned to have proper TeX, dot, and XML output.
Let us compute some simple statistics on a given tree:
treetmp:=combinat::trees([d, [d, d], [d, d, d, d]])
o
/ \
|/|\
The size, number of operands, and operands are respectively:
combinat::trees::size(treetmp);
combinat::trees::nops(treetmp);
combinat::trees::op(treetmp)
o, o
| /|\
Change the shape of a tree:
treetmp := combinat::trees([d, [d, [d]], [d, [d], [d], [d]]]);
treetmp2 := combinat::trees::subsop(treetmp,
1=combinat::trees([d,[d],[d]]));
treetmp2[1]
o
/ \
|/|\
o
/ \
/\/|\
o
/ \
Change the shape of the tree using another way:
treetmp3:=treetmp; treetmp3[1]:=combinat::trees([d,[d],[d]]);
bool(treetmp2=treetmp3)
o
/ \
|/|\
o
/ \
We demonstrate how to substitute a node inside a tree:
t1 := combinat::trees([1, [2, [1], [2, [1], [1]]], [3]]):
ts := combinat::trees([4, [2]]):
t2 := subsop(t1, [1, 2]=ts):
t1, ts, t2
1 , 4, 1
/ \ | / \
2 3 2 2 3
/ \ / \
1 2 1 4
/ \ |
1 1 2
To recursively revert the subtrees of a tree (making the mirror image of this tree), one uses:
tree:=combinat::trees([d, [d], [d, [d], [d, [d], [d], [d, [d]]], [d]]]);
combinat::trees::revert(tree)
o
/ \
/ | \
/|\
|
o
/ \
/ | \
/|\
|
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);
6
/ \
3 8
/ \/ \
1 57 10
\/ |
24 9
Here is how to put on the nodes of a tree the labels given by a word and following a depth-first walk:
valtree := combinat::trees([d,[d,[d,[],[d]],[d,[d],[]]],
[d,[d],[d,[d]]]]);
valb := combinat::trees::fromShapeAndWord(valtree,
[8,4,1,7,9,5,3,10,2,6],Postfix);
combinat::trees::toWord(valb,Postfix);
o
/ \
/\ /\
\/ |
6
/ \
9 2
/ \/ \
4 75 10
\/ |
81 3
Background:
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 domains of labelled trees (see as those created by mean of combinat::treesGeneric) 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.