We construct a combinatorial class of complete binary labelled ordered trees:
T := combinat::treesGeneric(Labelled, CompleteBinary):
T::list(3)
-- 1 , 1 , 2 , 2 , 3 , 3 --
| / \ / \ / \ / \ / \ / \ |
-- 2 3 3 2 1 3 3 1 1 2 2 1 --
We may instead construct a class for unordered trees:
T:=combinat::treesGeneric(Labelled, CompleteBinary, Ordered=FALSE):
T::list(3)
-- 1 , 2 , 3 --
| / \ / \ / \ |
-- 2 3 1 3 1 2 --
Note that the trees are produced in a normal form where, among siblings, the subtree bearing the smallest label is always on the left.
Beware however that the constructor of T does neither check that the tree is given in normal form, nor put it into normal form:
T([1, 3, 2])
1
/ \
3 2
More advanced effects can be achieved by redefining some productions in the specification. Here, we construct a class of complete binary trees with labels on the leaves only. We start from the class of labelled complete binary trees, and look at the specification produced:
T:=combinat::treesGeneric(Labelled, CompleteBinary):
T::specification
table(Tree = Union(Leaf, Node),
Leaf = Alias(LeafLabel, dom @ DOM_LIST),
LeafLabel = Atom(id),
LeafNil = Epsilon(.), // not used
Node = Alias(NodeRaw, x -> dom([op(x, 1), op(op(x, 2))])),
NodeRaw = Prod(NodeLabel, ChildList),
NodeLabel = Atom(id),
ChildList = Prod(Tree, Tree))
All we need to do is to redefine the production for NodeLabel to specify that the label of a node is of size zero (see Epsilon in combinat::decomposableObjects) and generates a dummy label (see combinat::trees::dummyLabel):
T:=combinat::treesGeneric([NodeLabel=Epsilon(combinat::trees::dummyLabel)],
Labelled, CompleteBinary):
T::list(3)
-- o , o , o , o , o , o , o , o , o , o , o , o --
| / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ |
| 1 /\ 1 /\ 2 /\ 2 /\ 3 /\ 3 /\ /\ 3 /\ 3 /\ 2 /\ 2 /\ 1 /\ 1 |
-- 23 32 13 31 12 21 12 21 13 31 23 32 --
Here is the same class of trees, but now unordered. Note again that, among siblings, the subtree bearing the smallest label is always on the left:
T:=combinat::treesGeneric([NodeLabel=Epsilon(combinat::trees::dummyLabel)],
Labelled, CompleteBinary, Ordered=FALSE):
T::list(3)
-- o , o , o --
| / \ / \ / \ |
| 1 /\ /\ 3 /\ 2 |
-- 23 12 13 --
Beware that the default implementation of "size" is not (yet) aware that the internal nodes have been redefined to be of size zero. It needs to be reimplemented appropriately to yield a consistent result:
t := T::random(5)
o
/ \
/ \ 3
1 /\
/\5
24
t := T::size(t)
