, the letter inserts in the left or in the right part of the tree depending on whether 
or 
.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
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:
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.
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 , the letter inserts in the left or in the right part of the tree depending on whether or .
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.
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
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
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
5
/ \
1 8
/ \ / \
0 4 7 10
/ / /
3 6 9
/
2
