[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

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

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

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

Method decreasingTree: insertion of a word in a decreasing tree

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

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

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