\begin{Mhelppage}{labelledBinaryTrees}{J.-C. Novelli}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{novelli}{10/2003}{proofread}

\begin{MInfo}
  \eng{labelled binary trees}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for inserting words in
    trees in order to create binary search trees or decreasing trees.}
  \eng{All manipulation functions defined in \Mup{combinat::binaryTrees} and
    \Mup{combinat::trees} can be used in \Mthis{}}
\end{MIntro}

\MKeywords{combinatorics, binary trees, labelled binary trees}

\begin{MDetails}
  \eng{A \emph{labelled binary tree} is a binary tree with labels at each
    node, either internal node or leaf.
    Technically, it is a \Mup{combinat::trees} such that
    every node exactly has a label and two operands: the left and the right
    subtree.}
  \eng{The labelled binary trees inherit most of the structure of binary
    trees.}
\end{MDetails}

% -----------------------------------------------------------
%
% -------- construction of Domain elements ----------
%
% -----------------------------------------------------------

\begin{MDomElConst}
  \MCall{list}
\end{MDomElConst}

\begin{MParameters}
  \param{list}%
  \eng{A nested list of lists.}
\end{MParameters}

\begin{MCategories}
\Mex{Cat::DecomposableClass}, \Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::trees, combinat::binaryTrees,
  combinat::decomposableObjects}

\begin{MDetails}
  \eng{\Mex{\Mthis(list)} creates a new binary tree whose recursive
    structure is encoded by \Mpar{list}. See \Mup{combinat::trees} for
    details on the structure of the list.}
\end{MDetails}


\begin{MDomEntries}
  \MDomEntry{zero}
  \eng{The empty labelled binary tree with zero nodes}
  \MDomEntry{one}
  \eng{The labelled binary tree with one single node with two empty subtrees}
\end{MDomEntries}

\MMethodInherited{size}{combinat::trees}
\MMethodInherited{nops}{combinat::trees}
\MMethodInherited{op}{combinat::trees}
\MMethodInherited{subsop}{combinat::trees}
\MMethodInherited{_index}{combinat::trees}
\MMethodInherited{set_index}{combinat::trees}
\MMethodInherited{expr}{combinat::trees}
\MMethodInherited{print}{combinat::trees}
\MMethodInherited{revert}{combinat::trees}

\begin{MMethodDetails}{fromShapeAndWord}
  \infoEng{creates a labelled binary tree from a given tree and a word}
  \call{\Mtype{binary tree} t, \Mtype{word} w\Mopt{, reading Order O}}%
  \eng{Returns the binary tree obtained by putting the letters of \Mpar{w}
    in a given order. This order can be: LeftPrefix=Prefix, RightPrefix,
    LeftPostfix=Postfix, RightPostfix, LeftInfix=Infix, RightInfix.}
  \eng{The defaut order is Prefix.}
\end{MMethodDetails} 

\begin{MMethodDetails}{toWord}
  \infoEng{reads a labelled binary tree in a given order}
  \call{\Mtype{labelled binary tree} t\Mopt{, reading Order O}}
  \eng{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.}
  \eng{The defaut order is Prefix.}
\end{MMethodDetails} 

\begin{MMethodDetails}{decreasingTree}
  \infoEng{insertion of a word in a decreasing tree}
  \call{\Mtype{word} w}%
  \eng{Returns the decreasing tree corresponding to the word \Mpar{w}. The
    algorithm works as follows: it first inserts the right-most greatest
    letter of \Mpar{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.}
\end{MMethodDetails}

\begin{MMethodDetails}{searchTreeInsertLetter}
  \infoEng{insertion of a letter in a binary search tree}
  \call{\Mtype{labelled binary tree} t,\Mtype{letter} l}%
  \eng{Returns the binary search tree obtained by inserting a letter \Mopt{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\leq r$ or $l>r$.}
\end{MMethodDetails}

\begin{MMethodDetails}{searchTreeInsertWord}
  \infoEng{insertion of a word in a binary search tree}
  \call{\Mtype{labelled binary tree} t,\Mtype{letter} l}%
  \eng{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.}
\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{lbt-toWord}
  \eng{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:}
  \begin{Mexin}
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);
  \end{Mexin}
  \begin{Mexout}
                             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]
  \end{Mexout}
\end{MExample}
%
\begin{MExample}{lbt-insertions}
  \eng{Let us now insert a word in an empty binary tree to create its
    decreasing tree:}
  \begin{Mexin}
combinat::labelledBinaryTrees::decreasingTree(
 [5, 1, 4, 8, 9, 3, 7, 2, 6]);
expr(%);
  \end{Mexin}
  \begin{Mexout}
                               9
                              / \
                              8 7
                             / / \
                             5 3 6
                              \ /
                              4 2
                             /
                             1

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

   [7, [3, [], []], [6, [2, [], []], []]]]
  \end{Mexout}
  \eng{We can also insert a word to obtain its corresponding binary search
    tree, and then, insert a new letter in it:}
  \begin{Mexin}
a:=combinat::labelledBinaryTrees::searchTreeInsertWord( 
  combinat::labelledBinaryTrees::zero(),
 [5, 1, 4, 8, 10, 3, 7, 2, 6]);
expr(%);
combinat::labelledBinaryTrees::searchTreeInsertWord(a,[9,0]);
expr(%);
  \end{Mexin}
  \begin{Mexout}
                              5
                            /   \
                            1   8
                             \ / \
                             4 7 10
                            / /
                            3 6
                           /
                           2

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

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

                              5
                            /   \
                            1   8
                           / \ / \
                           0 4 7 10
                            / / /
                            3 6 9
                           /
                           2

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

   [8, [7, [6, [], []], []], [10, [9, [], []], []]]]
  \end{Mexout}
\end{MExample}
\end{Mhelppage}
