[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

combinat::binaryTrees -- binary trees

Introduction

The library combinat::binaryTrees provides functions for counting, generating, and manipulating binary trees.

Details

Creating Elements


combinat::binaryTrees(list)

Parameters

list- A nested list of lists.

Details

Categories

Cat::DecomposableClass, Cat::CombinatorialClass

Related Domains

combinat::trees, combinat::decomposableObjects, combinat::dyckWords

Entries

zero

The empty binary tree with zero nodes

one

The binary tree with one single node with two empty subtrees

dummyLabel

The dummy label which is used for unlabelled binary trees

Method isA: test if an object is a binary tree

Method count: number of binary trees

Method generator: generator for binary trees

Method list: list of the binary trees

Method unrank: unranking of a binary tree

Method random: random tree

Method branchSlice: left or right branch slice of a binary tree

Method toDyckWord: Transformation of a tree into a Dyck word

Method shuffle: [DocState=alpha] shuffle product of two binary trees

Example 1

We introduce here a binary tree of size 5, and test its type:

>> bt:=combinat::binaryTrees([1, [1, [1, [1, [], []], []], 
                               [1, [], []]], []]);
   combinat::binaryTrees::isA(bt);
   combinat::binaryTrees::isA(bt,5);
   combinat::binaryTrees::isA(bt, 3);
     
                                       o
                                     /
                                    / \
                                   /
       
                                   TRUE
       
                                   TRUE
       
                                   FALSE
        

There is a strong difference between the binary tree and the list used in its construction:

>> combinat::binaryTrees::isA([1, [1, [1, [1, [], []], []], 
                                [1, [], []]], []]);
   domtype([1, [1, [1, [1, [], []], []], [1, [], []]], []]);
   domtype(bt);
     
                                   FALSE
       
                                 DOM_LIST
       
                           combinat::binaryTrees
        

Example 2

There are 5 trees of size 3:

>> combinat::binaryTrees::count(10);
     
                                   16796
        

If you want to run through the trees of size n, you can generate them one by one to save memory:

>> g := combinat::binaryTrees::generator(3):
   g();
   g(), g(), g(), g(), g();
     
                                    o
                                     \
                                      \
      
                         o     o     o    o
                           \, / \, /  ,  / , FAIL
                          /         \   /
        

Example 3

In this example, we list all the trees on 0 to 4 nodes:

>> for i from 0 to 4 do 
     print(combinat::binaryTrees::list(i))
   end_for
     
                                    [.]
      
                                    [o]
      
                                  o    o
                                 [ \, / ]
      
                       -- o    o     o     o    o --
                       |   \ ,   \, / \, /  ,  /   |
                       --   \   /         \   /   --
      
      -- o     o           o     o                                o
      |   \     \    o        \     \   o     o      o     o   /
      |    \ ,    \,   \ ,  /  ,   / , / \ , /  \, /  \,  / \,  \  ,
      --    \    /    / \    \    /       \    /    \    /       \
      
            o           o     o --
         /        o    /     /   |
           \ ,  /  , /   ,  /    |
          /    / \    \    /    --
        

We can directly get the sixth tree of size 4:

>> combinat::binaryTrees::unrank(6,4);
     
                                    o
                                   / \
                                      \
        

We can select a random binary tree by:

>> combinat::binaryTrees::random(10);
     
                                         o
                                        /
                                 /
                                /      \
                                   /
                                  /  \
                                    / \
        

We define a binary tree by hand:

>> t := combinat::binaryTrees([1, [1, [1, [], [1]], []], [1, [1]]])
     
                                     o
                                    /  \
                                  /   /
                                   \
        

The tree can be converted back into a list of lists. Note that the constructor added automatically the missing empty lists:

>> expr(t)
     
         [1, [1, [1, [], [1, [], []]], []], [1, [1, [], []], []]]
        

We can slice the left or the right branch of t:

>> combinat::binaryTrees::branchSlice(t, Left)
     
                             -- o       o  --
                             |    \, o,  \  |
                             --  /         --
        
>> combinat::binaryTrees::branchSlice(t, Right)
     
                              --    o     --
                              |    /    o  |
                              |  /   , /   |
                              --  \       --
        

Example 4

Let us start with a binary tree:

>> combinat::binaryTrees::unrank(12,7);
     
                                  o
                                   \
                                    \
                                        \
                                      /
                                     / \
        

We can compute its image under the usual bijection with Dyck words:

>> combinat::binaryTrees::toDyckWord(
         combinat::binaryTrees::unrank(12,7));
     
                [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0]
        

Super-Domain

combinat::trees

Axioms

Ax::normalRep, Ax::canonicalRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package