combinat::labelledBinaryTrees – labelled binary trees

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

→ Examples

Creating Elements

combinat::labelledBinaryTrees(list)

Parameters:

list

A nested list of lists.

Categories

Cat::DecomposableClass, Cat::CombinatorialClass

Related Domains:

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

Details:

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 size is inherited from combinat::trees.

Method nops is inherited from combinat::trees.

Method op is inherited from combinat::trees.

Method subsop is inherited from combinat::trees.

Method _index is inherited from combinat::trees.

Method set_index is inherited from combinat::trees.

Method expr is inherited from combinat::trees.

Method print is inherited from combinat::trees.

Method revert is inherited from combinat::trees.

fromShapeAndWord – creates a labelled binary tree from a given tree and a word

combinat::labelledBinaryTrees::fromShapeAndWord(binary tree t, word w, <readingOrder 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.

toWord – reads a labelled binary tree in a given order

combinat::labelledBinaryTrees::toWord(labelled binary tree t, <readingOrder 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.

decreasingTree – insertion of a word in a decreasing tree

combinat::labelledBinaryTrees::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.

searchTreeInsertLetter – insertion of a letter in a binary search tree

combinat::labelledBinaryTrees::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 math, the letter inserts in the left or in the right part of the tree depending on whether math or math.

searchTreeInsertWord – insertion of a word in a binary search tree

combinat::labelledBinaryTrees::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]);

combinat::labelledBinaryTrees::toWord(a);

combinat::labelledBinaryTrees::toWord(a,RightPostfix);

o

\

  \

  /\

/ /

/\

 

8

  \

  1

   \

   5

  / \

  4 2

/ /

7 6

/ \

3 9

 

math

math

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(%);

  9

/ \

8 7

/ / \

5 3 6

\ /

4 2

/

1

 

math

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(%);

   5

/   \

1   8

  \ / \

  4 7 10

/ /

3 6

/

2

 

math

   5

/   \

1   8

/ \ / \

0 4 7 10

/ / /

3 6 9

/

2

 

math