[Previous] [Next] [Contents]

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

## `combinat::binaryTrees` -- binary trees

#### Introduction

The library `combinat::binaryTrees` provides functions for counting, generating, and manipulating binary trees.

#### Details

- A binary tree is either empty, or constructed recursively from two trees by attaching them to a common ancestor node. Technically, it is a `combinat::trees` such that every node exactly has two operands: the left and the right subtree.

- A complete binary tree is a binary tree where each interior node (not a leaf) has non-empty left and right subtrees.

- The binary trees of size n are enumerated by the Catalan numbers. So they are in bijection with Dyck words.

#### Creating Elements

`combinat::binaryTrees(list)`

#### Parameters

`list` | - | A nested list of lists.

#### Details

- ``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.

#### Categories

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

#### Related Domains

`combinat::trees`, `combinat::decomposableObjects`, `combinat::dyckWords`

#### Entries

zero

The empty binary tree with zero nodes

one

The binary tree with one single node with two empty subtrees

dummyLabel

The dummy label which is used for unlabelled binary trees

#### Method isA: test if an object is a binary tree

- `isA(any type bt <, nonnegative integer n>)`

- Returns whether the object `bt` is a binary tree.
- If the optional argument is present, returns whether `bt` is a a binary tree of size `n`.

#### Method count: number of binary trees

- `count(nonnegative integer n)`

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

#### Method generator: generator for binary trees

- `generator(nonnegative integer n)`

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

#### Method list: list of the binary trees

- `list(nonnegative integer n)`

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

#### Method unrank: unranking of a binary tree

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

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

#### Method random: random tree

- `random(nonnegative integer n)`

- Returns a random binary tree of size `n`.

#### Method branchSlice: left or right branch slice of a binary tree

- `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.

#### Method toDyckWord: Transformation of a tree into a Dyck word

- `toDyckWord(binary tree t)`

- Returns the Dyck word corresponding to the tree.

#### Method shuffle: [DocState=alpha] shuffle product of two binary trees

- `shuffle(binary tree t1, binary tree t2)`

- Returns the shuffle product of `t1` and `t2`.

#### Example 1

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

#### Example 2

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
                              /         \   /

#### Example 3

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  |
                                  |  /   , /   |
                                  --  \       --

#### Example 4

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]

#### Super-Domain

`combinat::trees`

#### Axioms

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

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package