This module deals with binary trees as mathematical (in particular immutable) objects.
Note
If you need the data-structure for example to represent sets or hash tables with AVL trees, you should have a look at sage.misc.sagex_ds.
AUTHORS:
REFERENCES:
[LodayRonco] | Jean-Louis Loday and Maria O. Ronco. Hopf algebra of the planar binary trees, Advances in Mathematics, volume 139, issue 2, 10 November 1998, pp. 293-309. http://www.sciencedirect.com/science/article/pii/S0001870898917595 |
[HNT05] | (1, 2, 3, 4, 5, 6, 7) Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon. The algebra of binary search trees, Arxiv math/0401089v2. |
[CP12] | (1, 2) Gregory Chatel, Viviane Pons. Counting smaller trees in the Tamari order, Arxiv 1212.0751v1. |
Bases: sage.combinat.abstract_tree.AbstractClonableTree, sage.structure.list_clone.ClonableArray
Binary trees.
Binary trees here mean ordered (a.k.a. plane) finite binary trees, where “ordered” means that the children of each node are ordered.
Binary trees contain nodes and leaves, where each node has two
children while each leaf has no children. The number of leaves
of a binary tree always equals the number of nodes plus .
INPUT:
EXAMPLES:
sage: BinaryTree()
.
sage: BinaryTree(None)
.
sage: BinaryTree([])
[., .]
sage: BinaryTree([None, None])
[., .]
sage: BinaryTree([None, []])
[., [., .]]
sage: BinaryTree([[], None])
[[., .], .]
sage: BinaryTree("[[], .]")
[[., .], .]
sage: BinaryTree([None, BinaryTree([None, None])])
[., [., .]]
sage: BinaryTree([[], None, []])
Traceback (most recent call last):
...
ValueError: this is not a binary tree
TESTS:
sage: t1 = BinaryTree([[None, [[],[[], None]]],[[],[]]])
sage: t2 = BinaryTree([[[],[]],[]])
sage: with t1.clone() as t1c:
....: t1c[1,1,1] = t2
sage: t1 == t1c
False
Return the same tree seen as an ordered tree. By default, leaves are transformed into actual nodes, but this can be avoided by setting the optional variable with_leaves to False.
EXAMPLES:
sage: bt = BinaryTree([]); bt
[., .]
sage: bt.as_ordered_tree()
[[], []]
sage: bt.as_ordered_tree(with_leaves = False)
[]
sage: bt = bt.canonical_labelling(); bt
1[., .]
sage: bt.as_ordered_tree()
1[None[], None[]]
sage: bt.as_ordered_tree(with_leaves=False)
1[]
Return a labelled version of self.
The canonical labelling of a binary tree is a certain labelling of the
nodes (not the leaves) of the tree.
The actual canonical labelling is currently unspecified. However, it
is guaranteed to have labels in where
is the number of
nodes of the tree. Moreover, two (unlabelled) trees compare as equal if
and only if their canonical labelled trees compare as equal.
EXAMPLES:
sage: BinaryTree().canonical_labelling()
.
sage: BinaryTree([]).canonical_labelling()
1[., .]
sage: BinaryTree([[[], [[], None]], [[], []]]).canonical_labelling()
5[2[1[., .], 4[3[., .], .]], 7[6[., .], 8[., .]]]
Return the canopee of self.
The canopee of a non-empty binary tree with
internal nodes is
the list
of
and
of length
obtained by going along the
leaves of
from left to right except the two extremal ones, writing
if the leaf is a right leaf and
if the leaf is a left leaf.
EXAMPLES:
sage: BinaryTree([]).canopee()
[]
sage: BinaryTree([None, []]).canopee()
[1]
sage: BinaryTree([[], None]).canopee()
[0]
sage: BinaryTree([[], []]).canopee()
[0, 1]
sage: BinaryTree([[[], [[], None]], [[], []]]).canopee()
[0, 1, 0, 0, 1, 0, 1]
The number of pairs of binary trees of size
such that
the canopee of
is the complementary of the canopee of
is
also the number of Baxter permutations (see [DG94], see
also OEIS sequence A001181). We check this in small cases:
sage: [len([(u,v) for u in BinaryTrees(n) for v in BinaryTrees(n)
....: if map(lambda x:1-x, u.canopee()) == v.canopee()])
....: for n in range(1, 5)]
[1, 2, 6, 22]
Here is a less trivial implementation of this:
sage: from sage.sets.finite_set_map_cy import fibers
sage: from sage.misc.all import attrcall
sage: def baxter(n):
....: f = fibers(lambda t: tuple(t.canopee()),
....: BinaryTrees(n))
....: return sum(len(f[i])*len(f[tuple(1-x for x in i)])
....: for i in f)
sage: [baxter(n) for n in range(1, 7)]
[1, 2, 6, 22, 92, 422]
TESTS:
sage: t = BinaryTree().canopee()
Traceback (most recent call last):
...
ValueError: canopee is only defined for non empty binary trees
REFERENCES:
[DG94] | S. Dulucq and O. Guibert. Mots de piles, tableaux standards et permutations de Baxter, proceedings of Formal Power Series and Algebraic Combinatorics, 1994. |
Check that self is a binary tree.
EXAMPLES:
sage: BinaryTree([[], []]) # indirect doctest
[[., .], [., .]]
sage: BinaryTree([[], [], []]) # indirect doctest
Traceback (most recent call last):
...
ValueError: this is not a binary tree
sage: BinaryTree([[]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: this is not a binary tree
Convert self to a digraph. By default, this graph contains both nodes and leaves, hence is never empty. To obtain a graph which contains only the nodes, the with_leaves optional keyword variable has to be set to False.
INPUT:
EXAMPLES:
sage: t1 = BinaryTree([[], None])
sage: t1.graph()
Digraph on 5 vertices
sage: t1.graph(with_leaves=False)
Digraph on 2 vertices
sage: t1 = BinaryTree([[], [[], None]])
sage: t1.graph()
Digraph on 9 vertices
sage: t1.graph().edges()
[(0, 1, None), (0, 4, None), (1, 2, None), (1, 3, None), (4, 5, None), (4, 8, None), (5, 6, None), (5, 7, None)]
sage: t1.graph(with_leaves=False)
Digraph on 4 vertices
sage: t1.graph(with_leaves=False).edges()
[(0, 1, None), (0, 2, None), (2, 3, None)]
sage: t1 = BinaryTree()
sage: t1.graph()
Digraph on 1 vertex
sage: t1.graph(with_leaves=False)
Digraph on 0 vertices
sage: BinaryTree([]).graph()
Digraph on 3 vertices
sage: BinaryTree([]).graph(with_leaves=False)
Digraph on 1 vertex
sage: t1 = BinaryTree([[], [[], []]])
sage: t1.graph(with_leaves=False)
Digraph on 5 vertices
sage: t1.graph(with_leaves=False).edges()
[(0, 1, None), (0, 2, None), (2, 3, None), (2, 4, None)]
Explore the binary tree self using the depth-first infix-order traversal algorithm, executing the node_action function whenever traversing a node and executing the leaf_action function whenever traversing a leaf.
In more detail, what this method does to a tree is the
following:
if the root of `T` is a node:
apply in_order_traversal to the left subtree of `T`
(with the same node_action and leaf_action);
apply node_action to the root of `T`;
apply in_order_traversal to the right subtree of `T`
(with the same node_action and leaf_action);
else:
apply leaf_action to the root of `T`.
For example on the following binary tree , where we denote
leaves by
and nodes by
:
| ____3____ |
| / \ |
| 1 __7__ |
| / \ / \ |
| a 2 _5_ 8 |
| / \ / \ / \ |
| b c 4 6 h i |
| / \ / \ |
| d e f g |
this method first applies leaf_action to , then applies
node_action to
, then leaf_action to
, then
node_action to
, etc., with the vertices being traversed
in the order
.
See in_order_traversal_iter() for a version of this algorithm which only iterates through the vertices rather than applying any function to them.
INPUT:
TESTS:
sage: nb_leaf = 0
sage: def l_action(_):
....: global nb_leaf
....: nb_leaf += 1
sage: nb_node = 0
sage: def n_action(_):
....: global nb_node
....: nb_node += 1
sage: BinaryTree().in_order_traversal(n_action, l_action)
sage: nb_leaf, nb_node
(1, 0)
sage: nb_leaf, nb_node = 0, 0
sage: b = BinaryTree([[],[[],[]]]); b
[[., .], [[., .], [., .]]]
sage: b.in_order_traversal(n_action, l_action)
sage: nb_leaf, nb_node
(6, 5)
sage: nb_leaf, nb_node = 0, 0
sage: b = b.canonical_labelling()
sage: b.in_order_traversal(n_action, l_action)
sage: nb_leaf, nb_node
(6, 5)
sage: l = []
sage: b.in_order_traversal(lambda node: l.append( node.label() ))
sage: l
[1, 2, 3, 4, 5]
sage: leaf = 'a'
sage: l = []
sage: def l_action(_):
....: global leaf, l
....: l.append(leaf)
....: leaf = chr( ord(leaf)+1 )
sage: n_action = lambda node: l.append( node.label() )
sage: b = BinaryTree([[None,[]],[[[],[]],[]]]).\
....: canonical_labelling()
sage: b.in_order_traversal(n_action, l_action)
sage: l
['a', 1, 'b', 2, 'c', 3, 'd', 4, 'e', 5, 'f', 6, 'g', 7, 'h', 8,
'i']
The depth-first infix-order traversal iterator for the binary tree self.
This method iters each vertex (node and leaf alike) of the given binary tree following the depth-first infix order traversal algorithm.
The depth-first infix order traversal algorithm iterates through a binary tree as follows:
iterate through the left subtree (by the depth-first infix
order traversal algorithm);
yield the root;
iterate through the right subtree (by the depth-first infix
order traversal algorithm).
For example on the following binary tree , where we denote
leaves by
and nodes by
:
| ____3____ |
| / \ |
| 1 __7__ |
| / \ / \ |
| a 2 _5_ 8 |
| / \ / \ / \ |
| b c 4 6 h i |
| / \ / \ |
| d e f g |
the depth-first infix-order traversal algorithm iterates through
the vertices of in the following order:
.
See in_order_traversal() for a version of this algorithm which not only iterates through, but actually does something at the vertices of tree.
TESTS:
sage: b = BinaryTree([[],[[],[]]]); ascii_art([b])
[ _o_ ]
[ / \ ]
[ o o ]
[ / \ ]
[ o o ]
sage: ascii_art(list(b.in_order_traversal_iter()))
[ ]
[ , o, , _o_ o o o ]
[ / \ / \ ]
[ o o o o ]
[ / \ ]
[ o o, , , , , , , ]
sage: ascii_art(filter(lambda node: node.label() is not None,
....: b.canonical_labelling().in_order_traversal_iter()))
[ ]
[ 1, _2_ 3 4 5 ]
[ / \ / \ ]
[ 1 4 3 5 ]
[ / \ ]
[ 3 5, , , ]
sage: list(BinaryTree(None).in_order_traversal_iter())
[.]
Return True if self is complete, else return False.
In a nutshell, a complete binary tree is a perfect binary tree except possibly in the last level, with all nodes in the last level “flush to the left”.
In more detail:
A complete binary tree (also called binary heap) is a binary tree in
which every level, except possibly the last one (the deepest), is
completely filled. At depth , all nodes must be as far left as
possible.
For example:
| ___o___ |
| / \ |
| __o__ o |
| / \ |
| o o |
| / \ / \ |
| o o o o |
is not complete but the following ones are:
| __o__ _o_ ___o___ |
| / \ / \ / \ |
| o o o o __o__ o |
| / \ / \ / \ / \ / \ |
| o o o o, o o , o o o o |
| / \ / |
| o o o |
EXAMPLES:
sage: lst = lambda i: filter(lambda bt: bt.is_complete(), BinaryTrees(i))
sage: for i in range(9): ascii_art(lst(i)) # long time
[ ]
[ o ]
[ o ]
[ / ]
[ o ]
[ o ]
[ / \ ]
[ o o ]
[ o ]
[ / \ ]
[ o o ]
[ / ]
[ o ]
[ _o_ ]
[ / \ ]
[ o o ]
[ / \ ]
[ o o ]
[ __o__ ]
[ / \ ]
[ o o ]
[ / \ / ]
[ o o o ]
[ __o__ ]
[ / \ ]
[ o o ]
[ / \ / \ ]
[ o o o o ]
[ __o__ ]
[ / \ ]
[ o o ]
[ / \ / \ ]
[ o o o o ]
[ / ]
[ o ]
Return whether self is empty.
The notion of emptiness employed here is the one which defines a binary tree to be empty if its root is a leaf. There is precisely one empty binary tree.
EXAMPLES:
sage: BinaryTree().is_empty()
True
sage: BinaryTree([]).is_empty()
False
sage: BinaryTree([[], None]).is_empty()
False
Return True if self is full, else return False.
A full binary tree is a tree in which every node either has two child nodes or has two child leaves.
This is also known as proper binary tree or 2-tree or strictly binary tree.
For example:
| __o__ |
| / \ |
| o o |
| / \ |
| o o |
| / \ |
| o o |
is not full but the next one is:
| ___o___ |
| / \ |
| __o__ o |
| / \ |
| o o |
| / \ / \ |
| o o o o |
EXAMPLES:
sage: BinaryTree([[[[],None],[None,[]]], []]).is_full()
False
sage: BinaryTree([[[[],[]],[[],[]]], []]).is_full()
True
sage: ascii_art(filter(lambda bt: bt.is_full(), BinaryTrees(5)))
[ _o_ _o_ ]
[ / \ / \ ]
[ o o o o ]
[ / \ / \ ]
[ o o, o o ]
Return True if self is perfect, else return False.
A perfect binary tree is a full tree in which all leaves are at the same depth.
For example:
| ___o___ |
| / \ |
| __o__ o |
| / \ |
| o o |
| / \ / \ |
| o o o o |
is not perfect but the next one is:
| __o__ |
| / \ |
| o o |
| / \ / \ |
| o o o o |
EXAMPLES:
sage: lst = lambda i: filter(lambda bt: bt.is_perfect(), BinaryTrees(i))
sage: for i in range(10): ascii_art(lst(i)) # long time
[ ]
[ o ]
[ ]
[ o ]
[ / \ ]
[ o o ]
[ ]
[ ]
[ ]
[ __o__ ]
[ / \ ]
[ o o ]
[ / \ / \ ]
[ o o o o ]
[ ]
[ ]
Return the tree where a symmetry has been applied recursively on
all left borders. If a tree is made of three trees on its left border, it becomes
where
same symmetry has been applied to
.
EXAMPLES:
sage: BinaryTree().left_border_symmetry()
.
sage: BinaryTree([]).left_border_symmetry()
[., .]
sage: BinaryTree([[None,[]],None]).left_border_symmetry()
[[., .], [., .]]
sage: BinaryTree([[None,[None,[]]],None]).left_border_symmetry()
[[., .], [., [., .]]]
sage: bt = BinaryTree([[None,[None,[]]],None]).canonical_labelling()
sage: bt
4[1[., 2[., 3[., .]]], .]
sage: bt.left_border_symmetry()
1[4[., .], 2[., 3[., .]]]
Return the left-right symmetrized tree of self.
EXAMPLES:
sage: BinaryTree().left_right_symmetry()
.
sage: BinaryTree([]).left_right_symmetry()
[., .]
sage: BinaryTree([[],None]).left_right_symmetry()
[., [., .]]
sage: BinaryTree([[None, []],None]).left_right_symmetry()
[., [[., .], .]]
Return the result of left rotation applied to the binary tree self.
Left rotation on binary trees is defined as follows:
Let be a binary tree such that the right child of the
root of
is a node. Let
be the left
child of the root of
, and let
and
be the
left and right children of the right child of the root
of
. (Keep in mind that nodes of trees are identified
with the subtrees consisting of their descendants.)
Then, the left rotation of
is the binary tree in
which the right child of the root is
, whereas
the left child of the root is a node whose left and right
children are
and
. In pictures:
| * * |
| / \ / \ |
| A * -left-rotate-> * C |
| / \ / \ |
| B C A B |
where asterisks signify a single node each (but ,
and
might be empty).
For example,
| _o_ o |
| / \ / |
| o o -left-rotate-> o |
| / / \ |
| o o o |
<BLANKLINE>
| __o__ o |
| / \ / |
| o o -left-rotate-> o |
| / \ / |
| o o o |
| / \ / \ |
| o o o o |
| / \ |
| o o |
Left rotation is the inverse operation to right rotation (right_rotate()).
See also
EXAMPLES:
sage: b = BinaryTree([[],[[],None]]); ascii_art([b])
[ _o_ ]
[ / \ ]
[ o o ]
[ / ]
[ o ]
sage: ascii_art([b.left_rotate()])
[ o ]
[ / ]
[ o ]
[ / \ ]
[ o o ]
sage: b.left_rotate().right_rotate() == b
True
Modify self so that it becomes a leaf (i. e., an empty tree).
Note
self must be in a mutable state.
See also
EXAMPLES:
sage: t = BinaryTree([None, None])
sage: t.make_leaf()
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with t.clone() as t1:
....: t1.make_leaf()
sage: t, t1
([., .], .)
Modify self so that it becomes a node with children child_list.
INPUT:
Note
self must be in a mutable state.
See also
EXAMPLES:
sage: t = BinaryTree()
sage: t.make_node([None, None])
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with t.clone() as t1:
....: t1.make_node([None, None])
sage: t, t1
(., [., .])
sage: with t.clone() as t:
....: t.make_node([BinaryTree(), BinaryTree(), BinaryTree([])])
Traceback (most recent call last):
...
ValueError: the list must have length 2
sage: with t1.clone() as t2:
....: t2.make_node([t1, t1])
sage: with t2.clone() as t3:
....: t3.make_node([t1, t2])
sage: t1, t2, t3
([., .], [[., .], [., .]], [[., .], [[., .], [., .]]])
Return self over bt, where “over” is the over
() operation.
If and
are two binary trees, then
over
(written
) is defined as the tree obtained by grafting
on the rightmost leaf of
. More precisely,
is
defined by identifying the root of the
with the rightmost
leaf of
. See section 4.5 of [HNT05].
If is empty, then
.
The definition of this “over” operation goes back to
Loday-Ronco [LodRon0102066] (Definition 2.2), but it is
denoted by and called the “under” operation there.
In fact, trees in sage have their root at the top, contrary to
the trees in [LodRon0102066] which are growing upwards. For
this reason, the names of the over and under operations are
swapped, in order to keep a graphical meaning.
(Our notation follows that of section 4.5 of [HNT05].)
See also
EXAMPLES:
Showing only the nodes of a binary tree, here is an example for the over operation:
| o __o__ _o_ |
| / \ / / \ = / \ |
| o o o o o o |
| \ / \ |
| o o __o__ |
| / \ |
| o o |
| \ / |
| o o |
A Sage example:
sage: b1 = BinaryTree([[],[[],[]]])
sage: b2 = BinaryTree([[None, []],[]])
sage: ascii_art((b1, b2, b1/b2))
( _o_ _o_ _o_ )
( / \ / \ / \ )
( o o o o o o_ )
( / \ \ / \ )
( o o, o , o o )
( \ )
( _o_ )
( / \ )
( o o )
( \ )
( o )
TESTS:
sage: b1 = BinaryTree([[],[]]); ascii_art([b1])
[ o ]
[ / \ ]
[ o o ]
sage: b2 = BinaryTree([[None,[]],[[],None]]); ascii_art([b2])
[ __o__ ]
[ / \ ]
[ o o ]
[ \ / ]
[ o o ]
sage: ascii_art([b1.over(b2)])
[ _o_ ]
[ / \ ]
[ o o ]
[ \ ]
[ __o__ ]
[ / \ ]
[ o o ]
[ \ / ]
[ o o ]
The same in the labelled case:
sage: b1 = b1.canonical_labelling()
sage: b2 = b2.canonical_labelling()
sage: ascii_art([b1.over(b2)])
[ _2_ ]
[ / \ ]
[ 1 3 ]
[ \ ]
[ __3__ ]
[ / \ ]
[ 1 5 ]
[ \ / ]
[ 2 4 ]
Compute the q-hook length fraction of the binary tree self, with an additional “q-factor” if desired.
If is a (plane) binary tree and
is a polynomial
indeterminate over some ring, then the
-hook length fraction
of
is defined by
where the product ranges over all nodes of
, where
denotes the subtree of
consisting of
and its all
descendants, and where for every tree
, we denote by
the number of nodes of
. While this
definition only shows that
is a rational function
in
, it is in fact easy to show that
is
actually a polynomial in
, and thus makes sense when any
element of a commutative ring is substituted for
.
This can also be explicitly seen from the following recursive
formula for
:
where is any nonempty binary tree, and
and
are
the two child trees of the root of
, and where
denotes a
-binomial coefficient.
A variation of the -hook length fraction is the following
“
-hook length fraction with
-factor”:
where for every node , we denote by
the
right child of
.
This
differs from
only in a
multiplicative factor, which is a power of
.
When , both
and
equal the number
of permutations whose binary search tree (see [HNT05] for the
definition) is
(after dropping the labels). For example,
there are
permutations which give a binary tree of the
following shape:
| __o__ |
| / \ |
| o o |
| / \ / |
| o o o |
by the binary search insertion algorithm, in accordance with
the fact that this tree satisfies .
When is considered as a polynomial indeterminate,
is the generating function for all permutations
whose binary search tree is
(after dropping the labels)
with respect to the number of inversions (i. e., the Coxeter
length) of the permutations.
Objects similar to also make sense for general
ordered forests (rather than just binary trees), see e. g.
[BW88], Theorem 9.1.
INPUT:
REFERENCES:
[BW88] | Anders Bjoerner, Michelle L. Wachs, Generalized quotients in Coxeter groups. Transactions of the American Mathematical Society, vol. 308, no. 1, July 1988. http://www.ams.org/journals/tran/1988-308-01/S0002-9947-1988-0946427-X/S0002-9947-1988-0946427-X.pdf |
EXAMPLES:
Let us start with a simple example. Actually, let us start with the easiest possible example – the binary tree with only one vertex (which is a leaf):
sage: b = BinaryTree()
sage: b.q_hook_length_fraction()
1
sage: b.q_hook_length_fraction(q_factor=True)
1
Nothing different for a tree with one node and two leaves:
sage: b = BinaryTree([]); b
[., .]
sage: b.q_hook_length_fraction()
1
sage: b.q_hook_length_fraction(q_factor=True)
1
Let us get to a more interesting tree:
sage: b = BinaryTree([[[],[]],[[],None]]); b
[[[., .], [., .]], [[., .], .]]
sage: b.q_hook_length_fraction()(q=1)
20
sage: b.q_hook_length_fraction()
q^7 + 2*q^6 + 3*q^5 + 4*q^4 + 4*q^3 + 3*q^2 + 2*q + 1
sage: b.q_hook_length_fraction(q_factor=True)
q^10 + 2*q^9 + 3*q^8 + 4*q^7 + 4*q^6 + 3*q^5 + 2*q^4 + q^3
sage: b.q_hook_length_fraction(q=2)
465
sage: b.q_hook_length_fraction(q=2, q_factor=True)
3720
sage: q = PolynomialRing(ZZ, 'q').gen()
sage: b.q_hook_length_fraction(q=q**2)
q^14 + 2*q^12 + 3*q^10 + 4*q^8 + 4*q^6 + 3*q^4 + 2*q^2 + 1
Let us check the fact that is the generating function
for all permutations whose binary search tree is
(after
dropping the labels) with respect to the number of inversions of
the permutations:
sage: def q_hook_length_fraction_2(T):
....: P = PolynomialRing(ZZ, 'q')
....: q = P.gen()
....: res = P.zero()
....: for w in T.sylvester_class():
....: res += q ** Permutation(w).length()
....: return res
sage: def test_genfun(i):
....: return all( q_hook_length_fraction_2(T)
....: == T.q_hook_length_fraction(q_factor=True)
....: for T in BinaryTrees(i) )
sage: test_genfun(4)
True
Return the result of right rotation applied to the binary tree self.
Right rotation on binary trees is defined as follows:
Let be a binary tree such that the left child of the
root of
is a node. Let
be the right
child of the root of
, and let
and
be the
left and right children of the left child of the root
of
. (Keep in mind that nodes of trees are identified
with the subtrees consisting of their descendants.)
Then, the right rotation of
is the binary tree in
which the left child of the root is
, whereas
the right child of the root is a node whose left and right
children are
and
. In pictures:
| * * |
| / \ / \ |
| * C -right-rotate-> A * |
| / \ / \ |
| A B B C |
where asterisks signify a single node each (but ,
and
might be empty).
For example,
| o _o_ |
| / / \ |
| o -right-rotate-> o o |
| / \ / |
| o o o |
<BLANKLINE>
| __o__ _o__ |
| / \ / \ |
| o o -right-rotate-> o _o_ |
| / \ / / \ |
| o o o o o |
| / \ \ |
| o o o |
Right rotation is the inverse operation to left rotation (left_rotate()).
The right rotation operation introduced here is the one defined in Definition 2.1 of [CP12].
See also
EXAMPLES:
sage: b = BinaryTree([[[],[]], None]); ascii_art([b])
[ o ]
[ / ]
[ o ]
[ / \ ]
[ o o ]
sage: ascii_art([b.right_rotate()])
[ _o_ ]
[ / \ ]
[ o o ]
[ / ]
[ o ]
sage: b = BinaryTree([[[[],None],[None,[]]], []]); ascii_art([b])
[ __o__ ]
[ / \ ]
[ o o ]
[ / \ ]
[ o o ]
[ / \ ]
[ o o ]
sage: ascii_art([b.right_rotate()])
[ _o__ ]
[ / \ ]
[ o _o_ ]
[ / / \ ]
[ o o o ]
[ \ ]
[ o ]
Show the binary tree show, with or without leaves depending on the Boolean keyword variable with_leaves.
Warning
Left and right children might get interchanged in the actual picture. Moreover, for a labelled binary tree, the labels shown in the picture are not (in general) the ones given by the labelling!
Use _latex_(), view, _ascii_art_() or pretty_print for more faithful representations of the data of the tree.
TESTS:
sage: t1 = BinaryTree([[], [[], None]])
sage: t1.show()
Iterate over the sylvester class corresponding to the binary tree self.
The sylvester class of a tree is the set of permutations
whose right-to-left binary search tree (a notion defined
in [HNT05], Definition 7) is
after forgetting the labels.
This is an equivalence class of the sylvester congruence (the
congruence on words which holds two words
and
congruent whenever
,
,
are letters satisfying
, and extends by transitivity) on the symmetric
group.
For example the following tree’s sylvester class consists of the
permutations and
:
[ o ]
[ / \ ]
[ o o ]
(only the nodes are drawn here).
The right-to-left binary search tree of a word is constructed by an RSK-like insertion algorithm which proceeds as follows: Start with an empty labelled binary tree, and read the word from right to left. Each time a letter is read from the word, insert this letter in the existing tree using binary search tree insertion (binary_search_insert()). This is what the binary_search_tree() method computes if it is given the keyword left_to_right=False.
Here are two more descriptions of the sylvester class of a binary search tree:
If the optional keyword variable left_to_right is set to
True, then the left sylvester class of self is
returned instead. This is the set of permutations whose
left-to-right binary search tree (that is, the result of the
binary_search_tree()
with left_to_right set to True) is self. It is an
equivalence class of the left sylvester congruence.
Warning
This method yields the elements of the sylvester class as raw lists, not as permutations!
EXAMPLES:
Verifying the claim that the right-to-left binary search trees of
the permutations in the sylvester class of a tree all equal
:
sage: def test_bst_of_sc(n, left_to_right):
....: for t in BinaryTrees(n):
....: for p in t.sylvester_class(left_to_right=left_to_right):
....: p_per = Permutation(p)
....: tree = p_per.binary_search_tree(left_to_right=left_to_right)
....: if not BinaryTree(tree) == t:
....: return False
....: return True
sage: test_bst_of_sc(4, False)
True
sage: test_bst_of_sc(5, False) # long time
True
sage: test_bst_of_sc(6, False) # long time
True
The same with the left-to-right version of binary search:
sage: test_bst_of_sc(4, True)
True
sage: test_bst_of_sc(5, True) # long time
True
sage: test_bst_of_sc(6, True) # long time
True
Checking that the sylvester class is the set of linear extensions of the poset of the tree:
sage: all( sorted(t.canonical_labelling().sylvester_class())
....: == sorted(list(v) for v in t.canonical_labelling().to_poset().linear_extensions())
....: for t in BinaryTrees(4) )
True
TESTS:
sage: list(BinaryTree([[],[]]).sylvester_class())
[[1, 3, 2], [3, 1, 2]]
sage: bt = BinaryTree([[[],None],[[],[]]])
sage: l = list(bt.sylvester_class()); l
[[1, 2, 4, 6, 5, 3],
[1, 4, 2, 6, 5, 3],
[1, 4, 6, 2, 5, 3],
[1, 4, 6, 5, 2, 3],
[4, 1, 2, 6, 5, 3],
[4, 1, 6, 2, 5, 3],
[4, 1, 6, 5, 2, 3],
[4, 6, 1, 2, 5, 3],
[4, 6, 1, 5, 2, 3],
[4, 6, 5, 1, 2, 3],
[1, 2, 6, 4, 5, 3],
[1, 6, 2, 4, 5, 3],
[1, 6, 4, 2, 5, 3],
[1, 6, 4, 5, 2, 3],
[6, 1, 2, 4, 5, 3],
[6, 1, 4, 2, 5, 3],
[6, 1, 4, 5, 2, 3],
[6, 4, 1, 2, 5, 3],
[6, 4, 1, 5, 2, 3],
[6, 4, 5, 1, 2, 3]]
sage: len(l) == Integer(bt.q_hook_length_fraction()(q=1))
True
Border cases:
sage: list(BinaryTree().sylvester_class())
[[]]
sage: list(BinaryTree([]).sylvester_class())
[[1]]
The list of all trees greater or equal to self in the Tamari order.
This is the order filter of the Tamari order generated by self.
See tamari_lequal() for the definition of the Tamari poset.
See also
EXAMPLES:
For example, the tree:
| __o__ |
| / \ |
| o o |
| / \ / |
| o o o |
has these trees greater or equal to it:
|o , o , o , o , o , o ,|
| \ \ \ \ \ \ |
| o o o o _o_ __o__ |
| \ \ \ \ / \ / \ |
| o o o _o_ o o o o |
| \ \ / \ / \ \ \ \ / |
| o o o o o o o o o o |
| \ \ \ / |
| o o o o |
| \ / |
| o o |
<BLANKLINE>
| o , o , _o_ , _o__ , __o__ , ___o___ ,|
| / \ / \ / \ / \ / \ / \ |
| o o o o o o o _o_ o o o o |
| \ \ / \ / \ \ \ \ / |
| o o o o o o o o o o |
| \ \ \ / \ \ |
| o o o o o o |
| \ / |
| o o |
<BLANKLINE>
| _o_ , __o__ |
| / \ / \ |
| o o o o|
| / \ \ / \ / |
| o o o o o o |
TESTS:
sage: B = BinaryTree
sage: b = B([None, B([None, B([None, B([])])])]);b
[., [., [., [., .]]]]
sage: b.tamari_greater()
[[., [., [., [., .]]]]]
sage: b = B([B([B([B([]), None]), None]), None]);b
[[[[., .], .], .], .]
sage: b.tamari_greater()
[[., [., [., [., .]]]], [., [., [[., .], .]]],
[., [[., .], [., .]]], [., [[., [., .]], .]],
[., [[[., .], .], .]], [[., .], [., [., .]]],
[[., .], [[., .], .]], [[., [., .]], [., .]],
[[., [., [., .]]], .], [[., [[., .], .]], .],
[[[., .], .], [., .]], [[[., .], [., .]], .],
[[[., [., .]], .], .], [[[[., .], .], .], .]]
Return the Tamari interval between self and other as a TamariIntervalPoset.
A “Tamari interval” is an interval in the Tamari poset. See tamari_lequal() for the definition of the Tamari poset.
INPUT:
EXAMPLES:
sage: bt = BinaryTree([[None, [[], None]], None])
sage: ip = bt.tamari_interval(BinaryTree([None, [[None, []], None]])); ip
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)]
sage: ip.lower_binary_tree()
[[., [[., .], .]], .]
sage: ip.upper_binary_tree()
[., [[., [., .]], .]]
sage: ip.interval_cardinality()
4
sage: ip.number_of_tamari_inversions()
2
sage: list(ip.binary_trees())
[[., [[., [., .]], .]],
[[., [., [., .]]], .],
[., [[[., .], .], .]],
[[., [[., .], .]], .]]
sage: bt.tamari_interval(BinaryTree([[None,[]],[]]))
Traceback (most recent call last):
...
ValueError: The two binary trees are not comparable on the Tamari lattice.
TESTS:
Setting other equal to bt gives an interval consisting of just one element:
sage: ip = bt.tamari_interval(bt)
sage: ip
The tamari interval of size 4 induced by relations [(1, 4), (2, 3), (3, 4), (3, 1), (2, 1)]
sage: list(ip.binary_trees())
[[[., [[., .], .]], .]]
Empty trees work well:
sage: bt = BinaryTree()
sage: ip = bt.tamari_interval(bt)
sage: ip
The tamari interval of size 0 induced by relations []
sage: list(ip.binary_trees())
[.]
Return True if self is less or equal to another binary tree t2 (of the same size as self) in the Tamari order.
The Tamari order on binary trees of size is the partial order
on the set of all binary trees of size
generated by the
following requirement: If a binary tree
is obtained by
right rotation (see right_rotate()) from a binary tree
,
then
.
This not only is a well-defined partial order, but actually is
a lattice structure on the set of binary trees of size
, and
is a quotient of the weak order on the
-th symmetric group
(also known as the right permutohedron order, see
permutohedron_lequal()).
See [CP12]. The set of binary trees of size
equipped with
the Tamari order is called the
-th Tamari poset.
The Tamari order can equivalently be defined as follows:
If and
are two binary trees of size
, then the
following four statements are equivalent:
EXAMPLES:
This tree:
| o |
| / \ |
| o o |
| / |
| o |
| / \ |
| o o |
is Tamari- to the following tree:
| _o_ |
| / \ |
| o o |
| / \ \ |
| o o o |
Checking this:
sage: b = BinaryTree([[[[], []], None], []])
sage: c = BinaryTree([[[],[]],[None,[]]])
sage: b.tamari_lequal(c)
True
TESTS:
sage: for T in BinaryTrees(4):
....: for S in T.tamari_smaller():
....: if S != T and T.tamari_lequal(S):
....: print "FAILURE"
....: if not S.tamari_lequal(T):
....: print "FAILURE"
Compute the list of predecessors of self in the Tamari poset.
This list is computed by performing all left rotates possible on its nodes.
See tamari_lequal() for the definition of the Tamari poset.
EXAMPLES:
For this tree:
| __o__ |
| / \ |
| o o |
| / \ / |
| o o o |
the list is:
| o , _o_ |
| / / \ |
| _o_ o o |
| / \ / / |
| o o o o |
| / \ / |
| o o o |
TESTS:
sage: B = BinaryTree
sage: b = B([B([B([B([]), None]), None]), None]);b
[[[[., .], .], .], .]
sage: b.tamari_pred()
[]
sage: b = B([None, B([None, B([None, B([])])])]);b
[., [., [., [., .]]]]
sage: b.tamari_pred()
[[[., .], [., [., .]]], [., [[., .], [., .]]], [., [., [[., .], .]]]]
The list of all trees smaller or equal to self in the Tamari order.
This is the order ideal of the Tamari order generated by self.
See tamari_lequal() for the definition of the Tamari poset.
See also
EXAMPLES:
The tree:
| __o__ |
| / \ |
| o o |
| / \ / |
| o o o |
has these trees smaller or equal to it:
| __o__ , _o_ , o , o, o, o |
| / \ / \ / / / / |
| o o o o _o_ o o o |
| / \ / / / / \ / \ / / |
|o o o o o o o o o o o |
| / / \ / / / |
| o o o o o o |
| / / \ / |
| o o o o |
| / |
| o |
TESTS:
sage: B = BinaryTree
sage: b = B([None, B([None, B([None, B([])])])]);b
[., [., [., [., .]]]]
sage: b.tamari_smaller()
[[., [., [., [., .]]]], [., [., [[., .], .]]],
[., [[., .], [., .]]], [., [[., [., .]], .]],
[., [[[., .], .], .]], [[., .], [., [., .]]],
[[., .], [[., .], .]], [[., [., .]], [., .]],
[[., [., [., .]]], .], [[., [[., .], .]], .],
[[[., .], .], [., .]], [[[., .], [., .]], .],
[[[., [., .]], .], .], [[[[., .], .], .], .]]
sage: b = B([B([B([B([]), None]), None]), None]);b
[[[[., .], .], .], .]
sage: b.tamari_smaller()
[[[[[., .], .], .], .]]
Compute the list of successors of self in the Tamari poset.
This is the list of all trees obtained by a right rotate of one of its nodes.
See tamari_lequal() for the definition of the Tamari poset.
EXAMPLES:
The list of successors of:
| __o__ |
| / \ |
| o o |
| / \ / |
| o o o |
is:
| _o__ , ___o___ , _o_ |
| / \ / \ / \ |
| o _o_ o o o o |
| / \ \ / / \ \ |
| o o o o o o o |
| / \ |
| o o |
TESTS:
sage: B = BinaryTree
sage: b = B([B([B([B([]), None]), None]), None]);b
[[[[., .], .], .], .]
sage: b.tamari_succ()
[[[[., .], .], [., .]], [[[., .], [., .]], .], [[[., [., .]], .], .]]
sage: b = B([])
sage: b.tamari_succ()
[]
sage: b = B([[],[]])
sage: b.tamari_succ()
[[., [., [., .]]]]
Return a 132-avoiding permutation corresponding to the binary tree.
The linear extensions of a binary tree form an interval of the weak order called the sylvester class of the tree. This permutation is the maximal element of this sylvester class.
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_132_avoiding_permutation()
[3, 1, 2]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_132_avoiding_permutation()
[8, 6, 7, 3, 4, 1, 2, 5]
TESTS:
sage: bt = BinaryTree([[],[]])
sage: bt == bt.to_132_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_132_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
Return a 312-avoiding permutation corresponding to the binary tree.
The linear extensions of a binary tree form an interval of the weak order called the sylvester class of the tree. This permutation is the minimal element of this sylvester class.
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_312_avoiding_permutation()
[1, 3, 2]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_312_avoiding_permutation()
[1, 3, 4, 2, 6, 8, 7, 5]
TESTS:
sage: bt = BinaryTree([[],[]])
sage: bt == bt.to_312_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_312_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
Return the Dyck word associated with self using the given map.
INPUT:
The bijection is defined recursively as follows:
EXAMPLES:
sage: BinaryTree().to_dyck_word()
[]
sage: BinaryTree([]).to_dyck_word()
[1, 0]
sage: BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word()
[1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word()
[1, 1, 0, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("1R0L")
[1, 0, 1, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("L1R0")
[1, 1, 0, 0, 1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("R1L0")
[1, 1, 0, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("R10L")
Traceback (most recent call last):
...
ValueError: R10L is not a correct map
TESTS:
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_dyck_word().to_binary_tree()
True
sage: bt == bt.to_dyck_word("1R0L").to_binary_tree("1R0L")
True
sage: bt == bt.to_dyck_word("L1R0").to_binary_tree("L1R0")
True
sage: bt == bt.to_dyck_word("R1L0").to_binary_tree("R1L0")
True
Return the Dyck word associated with self in consistency with the Tamari order on Dyck words and binary trees.
The bijection is defined recursively as follows:
EXAMPLES:
sage: BinaryTree().to_dyck_word_tamari()
[]
sage: BinaryTree([]).to_dyck_word_tamari()
[1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word_tamari()
[1, 1, 0, 0, 1, 0]
sage: BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word_tamari()
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
Return an ordered tree of size by the following recursive rule:
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_ordered_tree_left_branch()
[[], [[]]]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_ordered_tree_left_branch()
[[], [[], []], [[], [[]]]]
Return an ordered tree of size by the following recursive rule:
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_ordered_tree_right_branch()
[[[]], []]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_ordered_tree_right_branch()
[[[[]], [[]]], [[]], []]
Return the poset obtained by interpreting the tree as a Hasse diagram.
The default orientation is from leaves to root but you can pass root_to_leaf=True to obtain the inverse orientation.
Leaves are ignored by default, but one can set with_leaves to True to obtain the poset of the complete tree.
INPUT:
EXAMPLES:
sage: bt = BinaryTree([])
sage: bt.to_poset()
Finite poset containing 1 elements
sage: bt.to_poset(with_leaves=True)
Finite poset containing 3 elements
sage: bt.to_poset(with_leaves=True).cover_relations()
[[1, 2], [0, 2]]
sage: bt = BinaryTree([])
sage: bt.to_poset(with_leaves=True,root_to_leaf=True).cover_relations()
[[0, 1], [0, 2]]
If the tree is labelled, we use its labelling to label the poset. Otherwise, we use the poset canonical labelling:
sage: bt = BinaryTree([[],[None,[]]]).canonical_labelling()
sage: bt
2[1[., .], 3[., 4[., .]]]
sage: bt.to_poset().cover_relations()
[[4, 3], [3, 2], [1, 2]]
Let us check that the empty binary tree is correctly handled:
sage: bt = BinaryTree()
sage: bt.to_poset()
Finite poset containing 0 elements
sage: bt.to_poset(with_leaves=True)
Finite poset containing 1 elements
Return the undirected graph obtained from the tree nodes and edges.
Leaves are ignored by default, but one can set with_leaves to True to obtain the graph of the complete tree.
INPUT:
EXAMPLES:
sage: bt = BinaryTree([])
sage: bt.to_undirected_graph()
Graph on 1 vertex
sage: bt.to_undirected_graph(with_leaves=True)
Graph on 3 vertices
sage: bt = BinaryTree()
sage: bt.to_undirected_graph()
Graph on 0 vertices
sage: bt.to_undirected_graph(with_leaves=True)
Graph on 1 vertex
If the tree is labelled, we use its labelling to label the graph. Otherwise, we use the graph canonical labelling which means that two different trees can have the same graph.
EXAMPLES:
sage: bt = BinaryTree([[],[None,[]]])
sage: bt.canonical_labelling()
2[1[., .], 3[., 4[., .]]]
sage: bt.canonical_labelling().to_undirected_graph().edges()
[(1, 2, None), (2, 3, None), (3, 4, None)]
sage: bt.to_undirected_graph().edges()
[(0, 3, None), (1, 2, None), (2, 3, None)]
sage: bt.canonical_labelling().to_undirected_graph() == bt.to_undirected_graph()
False
sage: BinaryTree([[],[]]).to_undirected_graph() == BinaryTree([[[],None],None]).to_undirected_graph()
True
Return self under bt, where “under” is the under
() operation.
If and
are two binary trees, then
under
(written
) is defined as the tree obtained
by grafting
on the leftmost leaf of
. More precisely,
is defined by identifying the root of
with the leftmost leaf of
.
If is empty, then
.
The definition of this “under” operation goes back to
Loday-Ronco [LodRon0102066] (Definition 2.2), but it is
denoted by and called the “over” operation there. In fact,
trees in sage have their root at the top, contrary to the trees
in [LodRon0102066] which are growing upwards. For this reason,
the names of the over and under operations are swapped, in
order to keep a graphical meaning.
(Our notation follows that of section 4.5 of [HNT05].)
See also
EXAMPLES:
Showing only the nodes of a binary tree, here is an example for the under operation:
sage: b1 = BinaryTree([[],[]])
sage: b2 = BinaryTree([None,[]])
sage: ascii_art((b1, b2, b1 \ b2))
( o o _o_ )
( / \ \ / \ )
( o o, o, o o )
( / \ )
( o o )
TESTS:
sage: b1 = BinaryTree([[],[[None,[]],None]]); ascii_art([b1])
[ _o_ ]
[ / \ ]
[ o o ]
[ / ]
[ o ]
[ \ ]
[ o ]
sage: b2 = BinaryTree([[],[None,[]]]); ascii_art([b2])
[ o ]
[ / \ ]
[ o o ]
[ \ ]
[ o ]
sage: ascii_art([b1.under(b2)])
[ o_ ]
[ / \ ]
[ o o ]
[ / \ ]
[ _o_ o ]
[ / \ ]
[ o o ]
[ / ]
[ o ]
[ \ ]
[ o ]
The same in the labelled case:
sage: b1 = b1.canonical_labelling()
sage: b2 = b2.canonical_labelling()
sage: ascii_art([b1.under(b2)])
[ 2_ ]
[ / \ ]
[ 1 3 ]
[ / \ ]
[ _2_ 4 ]
[ / \ ]
[ 1 5 ]
[ / ]
[ 3 ]
[ \ ]
[ 4 ]
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Factory for binary trees.
INPUT:
OUPUT:
EXAMPLES:
sage: BinaryTrees()
Binary trees
sage: BinaryTrees(2)
Binary trees of size 2
Note
this is a factory class whose constructor returns instances of subclasses.
Note
the fact that BinaryTrees is a class instead of a simple callable is an implementation detail. It could be changed in the future and one should not rely on it.
Return a leaf tree with self as parent.
EXAMPLES:
sage: BinaryTrees().leaf()
.
TEST:
sage: (BinaryTrees().leaf() is
....: sage.combinat.binary_tree.BinaryTrees_all().leaf())
True
Bases: sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets, sage.combinat.binary_tree.BinaryTrees
TESTS:
sage: from sage.combinat.binary_tree import BinaryTrees_all
sage: B = BinaryTrees_all()
sage: B.cardinality()
+Infinity
sage: it = iter(B)
sage: (it.next(), it.next(), it.next(), it.next(), it.next())
(., [., .], [., [., .]], [[., .], .], [., [., [., .]]])
sage: it.next().parent()
Binary trees
sage: B([])
[., .]
sage: B is BinaryTrees_all()
True
sage: TestSuite(B).run() # long time
alias of BinaryTree
Return the set of labelled trees associated to self.
EXAMPLES:
sage: BinaryTrees().labelled_trees()
Labelled binary trees
Return the set of unlabelled trees associated to self.
EXAMPLES:
sage: BinaryTrees().unlabelled_trees()
Binary trees
Bases: sage.combinat.binary_tree.BinaryTrees
The enumerated sets of binary trees of given size
TESTS:
sage: from sage.combinat.binary_tree import BinaryTrees_size
sage: for i in range(6): TestSuite(BinaryTrees_size(i)).run()
The cardinality of self
This is a Catalan number.
TESTS:
sage: BinaryTrees(0).cardinality()
1
sage: BinaryTrees(5).cardinality()
42
TESTS:
sage: S = BinaryTrees(3)
sage: S.element_class
<class 'sage.combinat.binary_tree.BinaryTrees_all_with_category.element_class'>
sage: S.first().__class__ == BinaryTrees().first().__class__
True
Return a random BinaryTree with uniform probability.
This method generates a random DyckWord and then uses a bijection between Dyck words and binary trees.
EXAMPLES:
sage: BinaryTrees(5).random_element() # random
[., [., [., [., [., .]]]]]
sage: BinaryTrees(0).random_element()
.
sage: BinaryTrees(1).random_element()
[., .]
TESTS:
sage: all([BinaryTrees(10).random_element() in BinaryTrees(10) for i in range(20)])
True
Bases: sage.combinat.abstract_tree.AbstractLabelledClonableTree, sage.combinat.binary_tree.BinaryTree
Labelled binary trees.
A labelled binary tree is a binary tree (see BinaryTree for the meaning of this) with a label assigned to each node. The labels need not be integers, nor are they required to be distinct. None can be used as a label.
Warning
While it is possible to assign values to leaves (not just nodes) using this class, these labels are disregarded by various methods such as labels(), map_labels(), and (ironically) leaf_labels().
INPUT:
children – None (default) or a list, tuple or iterable of
length of labelled binary trees or convertible objects. This
corresponds to the standard recursive definition of a labelled
binary tree as being either a leaf, or a pair of:
(The label is specified in the keyword variable label; see below.)
Syntactic sugar allows leaving out all but the outermost calls of the LabelledBinaryTree() constructor, so that, e. g., LabelledBinaryTree([LabelledBinaryTree(None),LabelledBinaryTree(None)]) can be shortened to LabelledBinaryTree([None,None]). However, using this shorthand, it is impossible to label any vertex of the tree other than the root (because there is no way to pass a label variable without calling LabelledBinaryTree explicitly).
It is also allowed to abbreviate [None, None] by [] if one does not want to label the leaves (which one should not do anyway!).
label – (default: None) the label to be put on the root of this tree.
check – (default: True) whether checks should be performed or not.
Todo
It is currently not possible to use LabelledBinaryTree() as a shorthand for LabelledBinaryTree(None) (in analogy to similar syntax in the BinaryTree class).
EXAMPLES:
sage: LabelledBinaryTree(None)
.
sage: LabelledBinaryTree(None, label="ae") # not well supported
'ae'
sage: LabelledBinaryTree([])
None[., .]
sage: LabelledBinaryTree([], label=3) # not well supported
3[., .]
sage: LabelledBinaryTree([None, None])
None[., .]
sage: LabelledBinaryTree([None, None], label=5)
5[., .]
sage: LabelledBinaryTree([None, []])
None[., None[., .]]
sage: LabelledBinaryTree([None, []], label=4)
4[., None[., .]]
sage: LabelledBinaryTree([[], None])
None[None[., .], .]
sage: LabelledBinaryTree("[[], .]", label=False)
False[None[., .], .]
sage: LabelledBinaryTree([None, LabelledBinaryTree([None, None], label=4)], label=3)
3[., 4[., .]]
sage: LabelledBinaryTree([None, BinaryTree([None, None])], label=3)
3[., None[., .]]
sage: LabelledBinaryTree([[], None, []])
Traceback (most recent call last):
...
ValueError: this is not a binary tree
sage: LBT = LabelledBinaryTree
sage: t1 = LBT([[LBT([], label=2), None], None], label=4); t1
4[None[2[., .], .], .]
TESTS:
sage: t1 = LabelledBinaryTree([[None, [[],[[], None]]],[[],[]]])
sage: t2 = LabelledBinaryTree([[[],[]],[]])
sage: with t1.clone() as t1c:
....: t1c[1,1,1] = t2
sage: t1 == t1c
False
We check for trac ticket #16314:
sage: t1 = LBT([ LBT([LBT([], label=2),
....: LBT([], label=5)], label=6),
....: None], label=4); t1
4[6[2[., .], 5[., .]], .]
sage: class Foo(LabelledBinaryTree):
....: pass
sage: t2 = Foo(t1.parent(), t1); t2
4[6[2[., .], 5[., .]], .]
sage: t2.label()
4
sage: t2[0].label()
6
sage: t2.__class__, t2[0].__class__
(<class '__main__.Foo'>, <class '__main__.Foo'>)
Return the result of inserting a letter letter into the right strict binary search tree self.
INPUT:
OUTPUT:
The right strict binary search tree self with letter inserted into it according to the binary search insertion algorithm.
Note
self is supposed to be a binary search tree. This is not being checked!
A right strict binary search tree is defined to be a labelled
binary tree such that for each node with label
,
every descendant of the left child of
has a label
,
and every descendant of the right child of
has a label
. (Here, only nodes count as descendants, and every node
counts as its own descendant too.) Leaves are assumed to have
no labels.
Given a right strict binary search tree and a letter
,
the result of inserting
into
(denoted
in
the following) is defined recursively as follows:
See, for example, [HNT05] for properties of this algorithm.
Warning
If is nonempty, then inserting
into
does not
change the root label of
. Hence, as opposed to
algorithms like Robinson-Schensted-Knuth, binary
search tree insertion involves no bumping.
EXAMPLES:
The example from Fig. 2 of [HNT05]:
sage: LBT = LabelledBinaryTree
sage: x = LBT(None)
sage: x
.
sage: x = x.binary_search_insert("b"); x
b[., .]
sage: x = x.binary_search_insert("d"); x
b[., d[., .]]
sage: x = x.binary_search_insert("e"); x
b[., d[., e[., .]]]
sage: x = x.binary_search_insert("a"); x
b[a[., .], d[., e[., .]]]
sage: x = x.binary_search_insert("b"); x
b[a[., b[., .]], d[., e[., .]]]
sage: x = x.binary_search_insert("d"); x
b[a[., b[., .]], d[d[., .], e[., .]]]
sage: x = x.binary_search_insert("a"); x
b[a[a[., .], b[., .]], d[d[., .], e[., .]]]
sage: x = x.binary_search_insert("c"); x
b[a[a[., .], b[., .]], d[d[c[., .], .], e[., .]]]
Other examples:
sage: LBT = LabelledBinaryTree
sage: LBT(None).binary_search_insert(3)
3[., .]
sage: LBT([], label = 1).binary_search_insert(3)
1[., 3[., .]]
sage: LBT([], label = 3).binary_search_insert(1)
3[1[., .], .]
sage: res = LBT(None)
sage: for i in [3,1,5,2,4,6]:
....: res = res.binary_search_insert(i)
sage: res
3[1[., 2[., .]], 5[4[., .], 6[., .]]]
Return the result of inserting a letter l into the binary heap (tree) self.
A binary heap is a labelled complete binary tree such that for each node, the label at the node is greater or equal to the label of each of its child nodes. (More precisely, this is called a max-heap.)
For example:
| _7_ |
| / \ |
| 5 6 |
| / \ |
| 3 4 |
is a binary heap.
See Wikipedia article Binary_heap#Insert for a description of how to insert a letter into a binary heap. The result is another binary heap.
INPUT:
Note
self is assumed to be a binary heap (tree). No check is performed.
TESTS:
sage: h = LabelledBinaryTree(None)
sage: h = h.heap_insert(3); ascii_art([h])
[ 3 ]
sage: h = h.heap_insert(4); ascii_art([h])
[ 4 ]
[ / ]
[ 3 ]
sage: h = h.heap_insert(6); ascii_art([h])
[ 6 ]
[ / \ ]
[ 3 4 ]
sage: h = h.heap_insert(2); ascii_art([h])
[ 6 ]
[ / \ ]
[ 3 4 ]
[ / ]
[ 2 ]
sage: ascii_art([h.heap_insert(5)])
[ _6_ ]
[ / \ ]
[ 5 4 ]
[ / \ ]
[ 2 3 ]
Return the result of left rotation applied to the labelled binary tree self.
Left rotation on labelled binary trees is defined as
follows: Let be a labelled binary tree such that the
right child of the root of
is a node. Let
be the left child of the root of
, and let
and
be the left and right children of the right child
of the root of
. (Keep in mind that nodes of trees are
identified with the subtrees consisting of their
descendants.) Furthermore, let
be the label at the
root of
, and
be the label at the right child of the
root of
.
Then, the left rotation of
is the labelled binary tree
in which the root is labelled
, the right child of the
root is
, whereas the left child of the root is a node
labelled
whose left and right children are
and
.
In pictures:
| y x |
| / \ / \ |
| x C <-left-rotate- A y |
| / \ / \ |
| A B B C |
Left rotation is the inverse operation to right rotation (right_rotate()).
TESTS:
sage: LB = LabelledBinaryTree
sage: b = LB([LB([LB([],"A"), LB([],"B")],"x"),LB([],"C")], "y"); b
y[x[A[., .], B[., .]], C[., .]]
sage: b == b.right_rotate().left_rotate()
True
Return the result of right rotation applied to the labelled binary tree self.
Right rotation on labelled binary trees is defined as
follows: Let be a labelled binary tree such that the
left child of the root of
is a node. Let
be the right child of the root of
, and let
and
be the left and right children of the left child
of the root of
. (Keep in mind that nodes of trees are
identified with the subtrees consisting of their
descendants.) Furthermore, let
be the label at the
root of
, and
be the label at the left child of the
root of
.
Then, the right rotation of
is the labelled binary
tree in which the root is labelled
, the left child of
the root is
, whereas the right child of the root is a
node labelled
whose left and right children are
and
. In pictures:
| y x |
| / \ / \ |
| x C -right-rotate-> A y |
| / \ / \ |
| A B B C |
Right rotation is the inverse operation to left rotation (left_rotate()).
TESTS:
sage: LB = LabelledBinaryTree
sage: b = LB([LB([LB([],"A"), LB([],"B")],"x"),LB([],"C")], "y"); b
y[x[A[., .], B[., .]], C[., .]]
sage: b.right_rotate()
x[A[., .], y[B[., .], C[., .]]]
Return the result of inserting a letter letter into the semistandard tree self using the bumping algorithm.
INPUT:
OUTPUT:
The semistandard tree self with letter inserted into it according to the bumping algorithm.
Note
self is supposed to be a semistandard tree. This is not being checked!
A semistandard tree is defined to be a labelled binary tree
such that for each node with label
, every descendant of
the left child of
has a label
, and every descendant
of the right child of
has a label
. (Here, only
nodes count as descendants, and every node counts as its own
descendant too.) Leaves are assumed to have no labels.
Given a semistandard tree and a letter
, the result of
inserting
into
(denoted
in the following)
is defined recursively as follows:
This algorithm is similar to the Robinson-Schensted-Knuth insertion algorithm for semistandard Young tableaux.
AUTHORS:
EXAMPLES:
sage: LBT = LabelledBinaryTree
sage: x = LBT(None)
sage: x
.
sage: x = x.semistandard_insert("b"); x
b[., .]
sage: x = x.semistandard_insert("d"); x
b[., d[., .]]
sage: x = x.semistandard_insert("e"); x
b[., d[., e[., .]]]
sage: x = x.semistandard_insert("a"); x
a[b[., .], d[., e[., .]]]
sage: x = x.semistandard_insert("b"); x
a[b[., .], b[d[., .], e[., .]]]
sage: x = x.semistandard_insert("d"); x
a[b[., .], b[d[., .], d[e[., .], .]]]
sage: x = x.semistandard_insert("a"); x
a[b[., .], a[b[d[., .], .], d[e[., .], .]]]
sage: x = x.semistandard_insert("c"); x
a[b[., .], a[b[d[., .], .], c[d[e[., .], .], .]]]
Other examples:
sage: LBT = LabelledBinaryTree
sage: LBT(None).semistandard_insert(3)
3[., .]
sage: LBT([], label = 1).semistandard_insert(3)
1[., 3[., .]]
sage: LBT([], label = 3).semistandard_insert(1)
1[3[., .], .]
sage: res = LBT(None)
sage: for i in [3,1,5,2,4,6]:
....: res = res.semistandard_insert(i)
sage: res
1[3[., .], 2[5[., .], 4[., 6[., .]]]]
Bases: sage.combinat.ordered_tree.LabelledOrderedTrees
This is a parent stub to serve as a factory class for trees with various labels constraints.
alias of LabelledBinaryTree
Return the set of labelled trees associated to self.
EXAMPLES:
sage: LabelledBinaryTrees().labelled_trees()
Labelled binary trees
Return the set of unlabelled trees associated to self.
EXAMPLES:
sage: LabelledBinaryTrees().unlabelled_trees()
Binary trees
This is used to compute the shape:
sage: t = LabelledBinaryTrees().an_element().shape(); t
[[[., .], [., .]], [[., .], [., .]]]
sage: t.parent()
Binary trees
TESTS:
sage: t = LabelledBinaryTrees().an_element()
sage: t.canonical_labelling()
4[2[1[., .], 3[., .]], 6[5[., .], 7[., .]]]