[Previous] [Next] [Contents]

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

## `combinat::labelledBinaryTrees` -- labelled binary trees

#### Introduction

The library `combinat::labelledBinaryTrees` provides functions for inserting words in trees in order to create binary search trees or decreasing trees.

All manipulation functions defined in `combinat::binaryTrees` and `combinat::trees` can be used in `combinat::labelledBinaryTrees`

#### Details

- A labelled binary tree is a binary tree with labels at each node, either internal node or leaf. Technically, it is a `combinat::trees` such that every node exactly has a label and two operands: the left and the right subtree.
- The labelled binary trees inherit most of the structure of binary trees.

#### Creating Elements

`combinat::labelledBinaryTrees(list)`

#### Parameters

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

#### Categories

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

#### Related Domains

`combinat::trees`, `combinat::binaryTrees`, `combinat::decomposableObjects`

#### Details

- ``combinat::labelledBinaryTrees`(list)` creates a new binary tree whose recursive structure is encoded by `list`. See `combinat::trees` for details on the structure of the list.

#### Entries

zero

The empty labelled binary tree with zero nodes

one

The labelled binary tree with one single node with two empty subtrees

#### Method fromShapeAndWord: creates a labelled binary tree from a given tree and a word

- `fromShapeAndWord(binary tree t, word w <, reading Order O>)`

- Returns the binary tree obtained by putting the letters of `w` in a given order. This order can be: LeftPrefix=Prefix, RightPrefix, LeftPostfix=Postfix, RightPostfix, LeftInfix=Infix, RightInfix.
- The defaut order is Prefix.

#### Method toWord: reads a labelled binary tree in a given order

- `toWord(labelled binary tree t <, reading Order O>)`

- Returns the word obtained by reading a labelled binary tree in the given order. This order can be: LeftPrefix=Prefix, RightPrefix, LeftPostfix=Postfix, RightPostfix, LeftInfix=Infix, RightInfix.
- The defaut order is Prefix.

#### Method decreasingTree: insertion of a word in a decreasing tree

- `decreasingTree(word w)`

- Returns the decreasing tree corresponding to the word `w`. The algorithm works as follows: it first inserts the right-most greatest letter of `w` at the root. It then cuts the word into two pieces, the left and right of the inserted letter. It then recursively inserts the left (resp. right) part in the left (resp. right) branch of the tree.

#### Method searchTreeInsertLetter: insertion of a letter in a binary search tree

- `searchTreeInsertLetter(labelled binary tree t,letter l)`

- Returns the binary search tree obtained by inserting a letter <l> in a labelled binary tree. The insertion process works as follows: a letter inserts in an empty tree by putting its label at the root. If the tree has a root labeled by r, the letter inserts in the left or in the right part of the tree depending on whether l≤r or l>r.

#### Method searchTreeInsertWord: insertion of a word in a binary search tree

- `searchTreeInsertWord(labelled binary tree t,letter l)`

- Returns the binary search tree obtained by inserting a word in a labelled binary tree, the letters being inserted one at a time, in the usual reading way.

#### Example 1

First, let us create a labelled binary tree. We can then recover the word it came from, even get another word, using a reading different from the prefix order:

    >> combinat::binaryTrees::unrank(251,9);
       a:=combinat::labelledBinaryTrees::fromShapeAndWord(%,[8,1,5,4,7,3,9,2,6]):
       expr(%);
       combinat::labelledBinaryTrees::toWord(a);
       combinat::labelledBinaryTrees::toWord(a,RightPostfix);

                                     o
                                      \
                                           \
                                          /  \
                                        /   /
                                       / \

          [8, [], [1, [], [5, [4, [7, [3, [], []], [9, [], []]], []],

             [2, [6, [], []], []]]]]

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

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

#### Example 2

Let us now insert a word in an empty binary tree to create its decreasing tree:

    >> combinat::labelledBinaryTrees::decreasingTree(
        [5, 1, 4, 8, 9, 3, 7, 2, 6]);
       expr(%);

                                         o
                                        /  \
                                     /    /  \
                                       \    /
                                      /

          [9, [8, [5, [], [4, [1, [], []], []]], []],

             [7, [3, [], []], [6, [2, [], []], []]]]

We can also insert a word to obtain its corresponding binary search tree, and then, insert a new letter in it:

    >> a:=combinat::labelledBinaryTrees::searchTreeInsertWord(
         combinat::labelledBinaryTrees::zero(),
        [5, 1, 4, 8, 10, 3, 7, 2, 6]);
       expr(%);
       combinat::labelledBinaryTrees::searchTreeInsertWord(a,[9,0]);
       expr(%);

                                         o
                                     /      \
                                        \  / \
                                       /  /
                                      /

          [5, [1, [], [4, [3, [2, [], []], []], []]],

             [8, [7, [6, [], []], []], [10, [], []]]]

                                         o
                                     /      \
                                    /   \  /  \
                                       /  /  /
                                      /

          [5, [1, [0, [], []], [4, [3, [2, [], []], []], []]],

             [8, [7, [6, [], []], []], [10, [9, [], []], []]]]

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package