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
combinat::trees
such that
every node exactly has a label and two operands: the left and the right
subtree.
combinat::labelledBinaryTrees(list)
list | - | A nested list of lists. |
Cat::DecomposableClass
, Cat::CombinatorialClass
combinat::trees
, combinat::binaryTrees
, combinat::decomposableObjects
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.The empty labelled binary tree with zero nodes
The labelled binary tree with one single node with two empty subtrees
fromShapeAndWord(binary tree t, word w <, reading Order O>)
w
in a given order. This order can be: LeftPrefix=Prefix, RightPrefix,
LeftPostfix=Postfix, RightPostfix, LeftInfix=Infix, RightInfix.
toWord(labelled binary tree t <, reading Order O>)
decreasingTree(word w)
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(labelled binary tree t,letter l)
searchTreeInsertWord(labelled binary tree t,letter l)
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]
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, [], []], []]]]
MuPAD Combinat, an open source algebraic combinatorics package