
Math.Combinat.Trees.Binary 




Description 
Binary trees, forests, etc. See:
Donald E. Knuth: The Art of Computer Programming, vol 4, prefascicle 4A.


Synopsis 




Types



A binary tree with leaves decorated with type a.
 Constructors   Instances  





A binary tree with leaves and internal nodes decorated
with types a and b, respectively.
 Constructors   Instances  




module Data.Tree 


Constructors   Instances  






Bijections


















Nested parentheses



Synonym for fasc4A_algorithm_P.



Synonym for fasc4A_algorithm_W.



Synonym for fasc4A_algorithm_U.





Generates all sequences of nested parentheses of length 2n.
Order is lexigraphic (when right parentheses are considered
smaller then left ones).
Based on "Algorithm P" in Knuth, but less efficient because of
the "idiomatic" code.



Generates a uniformly random sequence of nested parentheses of length 2n.
Based on "Algorithm W" in Knuth.



:: Int  n
 > Integer  N; should satisfy 1 <= N <= C(n)
 > [Paren]   Nth sequence of nested parentheses of length 2n.
The order is the same as in fasc4A_algorithm_P.
Based on "Algorithm U" in Knuth.



Binary trees



Generates all binary trees with n nodes.
At the moment just a synonym for binaryTreesNaive.



# = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }.
This is also the counting function for forests and nested parentheses.



Generates all binary trees with n nodes. The naive algorithm.



Generates an uniformly random binary tree, using fasc4A_algorithm_R.



Grows a uniformly random binary tree.
"Algorithm R" (Remy's procudere) in Knuth.
Nodes are decorated with odd numbers, leaves with even numbers (from the
set [0..2n]). Uses mutable arrays internally.


Produced by Haddock version 2.6.1 