combinat::binaryTrees
--
binary trees
The library combinat::binaryTrees
provides functions for counting,
generating, and manipulating binary trees.
combinat::trees
such that
every node exactly has two operands: the left and the right
subtree.
combinat::binaryTrees(list)
list | - | A nested list of lists. |
combinat::binaryTrees
(list)
creates a new binary tree whose recursive
structure is encoded by list
. See combinat::trees
for
details on the structure of the list.Cat::DecomposableClass
, Cat::CombinatorialClass
combinat::trees
, combinat::decomposableObjects
, combinat::dyckWords
The empty binary tree with zero nodes
The binary tree with one single node with two empty subtrees
The dummy label which is used for unlabelled binary trees
isA(any type bt <, nonnegative integer n>)
bt
is a binary tree.bt
is a
a binary tree of size n
.
count(nonnegative integer n)
n
.
generator(nonnegative integer n)
n
.
list(nonnegative integer n)
n
.
unrank(nonnegative integer n, nonnegative integer i)
n
.
random(nonnegative integer n)
n
.
branchSlice(binary tree t <, direction>)
direction
can be Left
or Right
. Returns the
list of the binary trees without left (resp. right) subtrees
obtained by slicing the left (resp. right) branch of t
,
ordered from top to bottom.
toDyckWord(binary tree t)
shuffle(binary tree t1, binary tree t2)
t1
and t2
.We introduce here a binary tree of size 5, and test its type:
>> bt:=combinat::binaryTrees([1, [1, [1, [1, [], []], []],
[1, [], []]], []]);
combinat::binaryTrees::isA(bt);
combinat::binaryTrees::isA(bt,5);
combinat::binaryTrees::isA(bt, 3);
o / / \ / TRUE TRUE FALSE
There is a strong difference between the binary tree and the list used in its construction:
>> combinat::binaryTrees::isA([1, [1, [1, [1, [], []], []],
[1, [], []]], []]);
domtype([1, [1, [1, [1, [], []], []], [1, [], []]], []]);
domtype(bt);
FALSE DOM_LIST combinat::binaryTrees
There are 5 trees of size 3:
>> combinat::binaryTrees::count(10);
16796
If you want to run through the trees of size n, you can generate them one by one to save memory:
>> g := combinat::binaryTrees::generator(3):
g();
g(), g(), g(), g(), g();
o \ \ o o o o \, / \, / , / , FAIL / \ /
In this example, we list all the trees on 0 to 4 nodes:
>> for i from 0 to 4 do
print(combinat::binaryTrees::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 / / | \ , / , / , / | / / \ \ / --
We can directly get the sixth tree of size 4:
>> combinat::binaryTrees::unrank(6,4);
o / \ \
We can select a random binary tree by:
>> combinat::binaryTrees::random(10);
o / / / \ / / \ / \
We define a binary tree by hand:
>> t := combinat::binaryTrees([1, [1, [1, [], [1]], []], [1, [1]]])
o / \ / / \
The tree can be converted back into a list of lists. Note that the constructor added automatically the missing empty lists:
>> expr(t)
[1, [1, [1, [], [1, [], []]], []], [1, [1, [], []], []]]
We can slice the left or the right branch of t
:
>> combinat::binaryTrees::branchSlice(t, Left)
-- o o -- | \, o, \ | -- / --
>> combinat::binaryTrees::branchSlice(t, Right)
-- o -- | / o | | / , / | -- \ --
Let us start with a binary tree:
>> combinat::binaryTrees::unrank(12,7);
o \ \ \ / / \
We can compute its image under the usual bijection with Dyck words:
>> combinat::binaryTrees::toDyckWord(
combinat::binaryTrees::unrank(12,7));
[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0]
Ax::normalRep
,
Ax::canonicalRep
MuPAD Combinat, an open source algebraic combinatorics package