Binary Trees#
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:
Florent Hivert (2010-2011): initial implementation.
Adrien Boussicault (2015): Hook statistics.
- class sage.combinat.binary_tree.BinaryTree(parent, children=None, check=True)[source]#
Bases:
AbstractClonableTree
,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 \(1\).
INPUT:
children
–None
(default) or a list, tuple or iterable of length \(2\) of binary trees or convertible objects. This corresponds to the standard recursive definition of a binary tree as either a leaf or a pair of binary trees. Syntactic sugar allows leaving out all but the outermost calls of theBinaryTree()
constructor, so that, e. g.,BinaryTree([BinaryTree(None),BinaryTree(None)])
can be shortened toBinaryTree([None,None])
. It is also allowed to abbreviate[None, None]
by[]
.check
– (default:True
) whether check for binary should be performed or not.
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
>>> from sage.all import * >>> BinaryTree() . >>> BinaryTree(None) . >>> BinaryTree([]) [., .] >>> BinaryTree([None, None]) [., .] >>> BinaryTree([None, []]) [., [., .]] >>> BinaryTree([[], None]) [[., .], .] >>> BinaryTree("[[], .]") [[., .], .] >>> BinaryTree([None, BinaryTree([None, None])]) [., [., .]] >>> BinaryTree([[], None, []]) Traceback (most recent call last): ... ValueError: this is not a binary tree
- as_ordered_tree(with_leaves=True)[source]#
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
toFalse
.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[]
>>> from sage.all import * >>> bt = BinaryTree([]); bt [., .] >>> bt.as_ordered_tree() [[], []] >>> bt.as_ordered_tree(with_leaves = False) [] >>> bt = bt.canonical_labelling(); bt 1[., .] >>> bt.as_ordered_tree() 1[None[], None[]] >>> bt.as_ordered_tree(with_leaves=False) 1[]
- canonical_labelling(shift=1)[source]#
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 \(1...n\) where \(n\) 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[., .]]]
>>> from sage.all import * >>> BinaryTree().canonical_labelling() . >>> BinaryTree([]).canonical_labelling() 1[., .] >>> BinaryTree([[[], [[], None]], [[], []]]).canonical_labelling() 5[2[1[., .], 4[3[., .], .]], 7[6[., .], 8[., .]]]
- canopee()[source]#
Return the canopee of
self
.The canopee of a non-empty binary tree \(T\) with \(n\) internal nodes is the list \(l\) of \(0\) and \(1\) of length \(n-1\) obtained by going along the leaves of \(T\) from left to right except the two extremal ones, writing \(0\) if the leaf is a right leaf and \(1\) 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]
>>> from sage.all import * >>> BinaryTree([]).canopee() [] >>> BinaryTree([None, []]).canopee() [1] >>> BinaryTree([[], None]).canopee() [0] >>> BinaryTree([[], []]).canopee() [0, 1] >>> BinaryTree([[[], [[], None]], [[], []]]).canopee() [0, 1, 0, 0, 1, 0, 1]
The number of pairs \((t_1, t_2)\) of binary trees of size \(n\) such that the canopee of \(t_1\) is the complementary of the canopee of \(t_2\) is also the number of Baxter permutations (see [DG1994], 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 [1 - x for x in u.canopee()] == v.canopee()]) ....: for n in range(1, 5)] [1, 2, 6, 22]
>>> from sage.all import * >>> [len([(u,v) for u in BinaryTrees(n) for v in BinaryTrees(n) ... if [Integer(1) - x for x in u.canopee()] == v.canopee()]) ... for n in range(Integer(1), Integer(5))] [1, 2, 6, 22]
Here is a less trivial implementation of this:
sage: from sage.sets.finite_set_map_cy import fibers 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]
>>> from sage.all import * >>> from sage.sets.finite_set_map_cy import fibers >>> def baxter(n): ... f = fibers(lambda t: tuple(t.canopee()), ... BinaryTrees(n)) ... return sum(len(f[i])*len(f[tuple(Integer(1)-x for x in i)]) ... for i in f) >>> [baxter(n) for n in range(Integer(1), Integer(7))] [1, 2, 6, 22, 92, 422]
- check()[source]#
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
>>> from sage.all import * >>> BinaryTree([[], []]) # indirect doctest [[., .], [., .]] >>> BinaryTree([[], [], []]) # indirect doctest Traceback (most recent call last): ... ValueError: this is not a binary tree >>> BinaryTree([[]]) # indirect doctest Traceback (most recent call last): ... ValueError: this is not a binary tree
- comb(side='left')[source]#
Return the comb of a tree.
There are two combs in a binary tree: a left comb and a right comb.
Consider all the vertices of the leftmost (resp. rightmost) branch of the root. The left (resp. right) comb is the list of right (resp. left) subtrees of each of these vertices.
INPUT:
side
– (default: ‘left’) set to ‘left’ to obtain a left comb, and to ‘right’ to obtain a right comb.
OUTPUT:
A list of binary trees.
See also
EXAMPLES:
sage: BT = BinaryTree( '.' ) sage: [BT.comb('left'), BT.comb('right')] [[], []] sage: BT = BinaryTree( '[.,.]' ) sage: [BT.comb('left'), BT.comb('right')] [[], []] sage: BT = BinaryTree( '[[[.,.], .], [.,.]]' ) sage: BT.comb('left') [., .] sage: BT.comb('right') [.] sage: BT = BinaryTree( '[[[[., [., .]], .], [[., .], [[[., .], [., .]], [., .]]]], [., [[[., .], [[[., .], [., .]], .]], .]]]' ) sage: ascii_art(BT) ________o________ / \ __o__ o / \ \ o __o___ o / / \ / o o _o_ __o__ \ / \ / \ o o o o o / \ / o o o / \ o o sage: BT.comb('left') [[[., .], [[[., .], [., .]], [., .]]], ., [., .]] sage: ascii_art(BT.comb('left')) [ __o___ , , o ] [ / \ ] [ o _o_ ] [ / \ ] [ o o ] [ / \ ] [ o o ] sage: BT.comb('right') [., [[., .], [[[., .], [., .]], .]]] sage: ascii_art(BT.comb('right')) [ , __o__ ] [ / \ ] [ o o ] [ / ] [ o ] [ / \ ] [ o o ]
>>> from sage.all import * >>> BT = BinaryTree( '.' ) >>> [BT.comb('left'), BT.comb('right')] [[], []] >>> BT = BinaryTree( '[.,.]' ) >>> [BT.comb('left'), BT.comb('right')] [[], []] >>> BT = BinaryTree( '[[[.,.], .], [.,.]]' ) >>> BT.comb('left') [., .] >>> BT.comb('right') [.] >>> BT = BinaryTree( '[[[[., [., .]], .], [[., .], [[[., .], [., .]], [., .]]]], [., [[[., .], [[[., .], [., .]], .]], .]]]' ) >>> ascii_art(BT) ________o________ / \ __o__ o / \ \ o __o___ o / / \ / o o _o_ __o__ \ / \ / \ o o o o o / \ / o o o / \ o o >>> BT.comb('left') [[[., .], [[[., .], [., .]], [., .]]], ., [., .]] >>> ascii_art(BT.comb('left')) [ __o___ , , o ] [ / \ ] [ o _o_ ] [ / \ ] [ o o ] [ / \ ] [ o o ] >>> BT.comb('right') [., [[., .], [[[., .], [., .]], .]]] >>> ascii_art(BT.comb('right')) [ , __o__ ] [ / \ ] [ o o ] [ / ] [ o ] [ / \ ] [ o o ]
- dendriform_shuffle(other)[source]#
Return the list of terms in the dendriform product.
This is the list of all binary trees that can be obtained by identifying the rightmost path in
self
and the leftmost path inother
. Every term corresponds to a shuffle of the vertices on the rightmost path inself
and the vertices on the leftmost path inother
.EXAMPLES:
sage: u = BinaryTree() sage: g = BinaryTree([]) sage: l = BinaryTree([g, u]) sage: r = BinaryTree([u, g]) sage: list(g.dendriform_shuffle(g)) # needs sage.combinat [[[., .], .], [., [., .]]] sage: list(l.dendriform_shuffle(l)) # needs sage.combinat [[[[[., .], .], .], .], [[[., .], [., .]], .], [[., .], [[., .], .]]] sage: list(l.dendriform_shuffle(r)) # needs sage.combinat [[[[., .], .], [., .]], [[., .], [., [., .]]]]
>>> from sage.all import * >>> u = BinaryTree() >>> g = BinaryTree([]) >>> l = BinaryTree([g, u]) >>> r = BinaryTree([u, g]) >>> list(g.dendriform_shuffle(g)) # needs sage.combinat [[[., .], .], [., [., .]]] >>> list(l.dendriform_shuffle(l)) # needs sage.combinat [[[[[., .], .], .], .], [[[., .], [., .]], .], [[., .], [[., .], .]]] >>> list(l.dendriform_shuffle(r)) # needs sage.combinat [[[[., .], .], [., .]], [[., .], [., [., .]]]]
- graph(with_leaves=True)[source]#
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 toFalse
.The resulting digraph is endowed with a combinatorial embedding, in order to be displayed correctly.
INPUT:
with_leaves
– (default:True
) a Boolean, determining whether the resulting graph will be formed from the leaves and the nodes ofself
(ifTrue
), or only from the nodes ofself
(ifFalse
)
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(sort=True) [(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(sort=True) [(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(sort=True) [(0, 1, None), (0, 2, None), (2, 3, None), (2, 4, None)]
>>> from sage.all import * >>> t1 = BinaryTree([[], None]) >>> t1.graph() Digraph on 5 vertices >>> t1.graph(with_leaves=False) Digraph on 2 vertices >>> t1 = BinaryTree([[], [[], None]]) >>> t1.graph() Digraph on 9 vertices >>> t1.graph().edges(sort=True) [(0, 1, None), (0, 4, None), (1, 2, None), (1, 3, None), (4, 5, None), (4, 8, None), (5, 6, None), (5, 7, None)] >>> t1.graph(with_leaves=False) Digraph on 4 vertices >>> t1.graph(with_leaves=False).edges(sort=True) [(0, 1, None), (0, 2, None), (2, 3, None)] >>> t1 = BinaryTree() >>> t1.graph() Digraph on 1 vertex >>> t1.graph(with_leaves=False) Digraph on 0 vertices >>> BinaryTree([]).graph() Digraph on 3 vertices >>> BinaryTree([]).graph(with_leaves=False) Digraph on 1 vertex >>> t1 = BinaryTree([[], [[], []]]) >>> t1.graph(with_leaves=False) Digraph on 5 vertices >>> t1.graph(with_leaves=False).edges(sort=True) [(0, 1, None), (0, 2, None), (2, 3, None), (2, 4, None)]
- hook_number()[source]#
Return the number of hooks.
Recalling that a branch is a path from a vertex of the tree to a leaf, the leftmost (resp. rightmost) branch of a vertex \(v\) is the branch from \(v\) made only of left (resp. right) edges.
The hook of a vertex \(v\) is a set of vertices formed by the union of \({v}\), and the vertices of its leftmost and rightmost branches.
There is a unique way to partition the set of vertices in hooks. The number of hooks in such a partition is the hook number of the tree.
We can obtain this partition recursively by extracting the root’s hook and iterating the processus on each tree of the remaining forest.
EXAMPLES:
sage: BT = BinaryTree( '.' ) sage: BT.hook_number() 0 sage: BT = BinaryTree( '[.,.]' ) sage: BT.hook_number() 1 sage: BT = BinaryTree( '[[[.,.], .], [.,.]]' ); ascii_art(BT) o / \ o o / o sage: BT.hook_number() 1 sage: BT = BinaryTree( '[[[[., [., .]], .], [[., .], [[[., .], [., .]], [., .]]]], [., [[[., .], [[[., .], [., .]], .]], .]]]' ) sage: ascii_art(BT) ________o________ / \ __o__ o / \ \ o __o___ o / / \ / o o _o_ __o__ \ / \ / \ o o o o o / \ / o o o / \ o o sage: BT.hook_number() 6
>>> from sage.all import * >>> BT = BinaryTree( '.' ) >>> BT.hook_number() 0 >>> BT = BinaryTree( '[.,.]' ) >>> BT.hook_number() 1 >>> BT = BinaryTree( '[[[.,.], .], [.,.]]' ); ascii_art(BT) o / \ o o / o >>> BT.hook_number() 1 >>> BT = BinaryTree( '[[[[., [., .]], .], [[., .], [[[., .], [., .]], [., .]]]], [., [[[., .], [[[., .], [., .]], .]], .]]]' ) >>> ascii_art(BT) ________o________ / \ __o__ o / \ \ o __o___ o / / \ / o o _o_ __o__ \ / \ / \ o o o o o / \ / o o o / \ o o >>> BT.hook_number() 6
- in_order_traversal(node_action=None, leaf_action=None)[source]#
Explore the binary tree
self
using the depth-first infix-order traversal algorithm, executing thenode_action
function whenever traversing a node and executing theleaf_action
function whenever traversing a leaf.In more detail, what this method does to a tree \(T\) 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 \(T\), where we denote leaves by \(a, b, c, \ldots\) and nodes by \(1, 2, 3, \ldots\):
| ____3____ | | / \ | | 1 __7__ | | / \ / \ | | a 2 _5_ 8 | | / \ / \ / \ | | b c 4 6 h i | | / \ / \ | | d e f g |
this method first applies
leaf_action
to \(a\), then appliesnode_action
to \(1\), thenleaf_action
to \(b\), thennode_action
to \(2\), etc., with the vertices being traversed in the order \(a,1,b,2,c,3,d,4,e,5,f,6,g,7,h,8,i\).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:
node_action
– (optional) a function which takes a node in input and does something during the explorationleaf_action
– (optional) a function which takes a leaf in input and does something during the exploration
- in_order_traversal_iter()[source]#
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 \(T\), where we denote leaves by \(a, b, c, \ldots\) and nodes by \(1, 2, 3, \ldots\):
| ____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 \(T\) in the following order: \(a,1,b,2,c,3,d,4,e,5,f,6,g,7,h,8,i\).
See
in_order_traversal()
for a version of this algorithm which not only iterates through, but actually does something at the vertices of tree.
- is_complete()[source]#
Return
True
ifself
is complete, else returnFalse
.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 \(n\), 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: def lst(i): ....: return [bt for bt in BinaryTrees(i) if bt.is_complete()] sage: for i in range(8): 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 ]
>>> from sage.all import * >>> def lst(i): ... return [bt for bt in BinaryTrees(i) if bt.is_complete()] >>> for i in range(Integer(8)): 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 ]
- is_empty()[source]#
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
>>> from sage.all import * >>> BinaryTree().is_empty() True >>> BinaryTree([]).is_empty() False >>> BinaryTree([[], None]).is_empty() False
- is_full()[source]#
Return
True
ifself
is full, else returnFalse
.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([bt for bt in BinaryTrees(5) if bt.is_full()]) [ _o_ , _o_ ] [ / \ / \ ] [ o o o o ] [ / \ / \ ] [ o o o o ]
>>> from sage.all import * >>> BinaryTree([[[[],None],[None,[]]], []]).is_full() False >>> BinaryTree([[[[],[]],[[],[]]], []]).is_full() True >>> ascii_art([bt for bt in BinaryTrees(Integer(5)) if bt.is_full()]) [ _o_ , _o_ ] [ / \ / \ ] [ o o o o ] [ / \ / \ ] [ o o o o ]
- is_perfect()[source]#
Return
True
ifself
is perfect, else returnFalse
.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: def lst(i): ....: return [bt for bt in BinaryTrees(i) if bt.is_perfect()] sage: for i in range(8): ascii_art(lst(i)) # long time [ ] [ o ] [ ] [ o ] [ / \ ] [ o o ] [ ] [ ] [ ] [ __o__ ] [ / \ ] [ o o ] [ / \ / \ ] [ o o o o ]
>>> from sage.all import * >>> def lst(i): ... return [bt for bt in BinaryTrees(i) if bt.is_perfect()] >>> for i in range(Integer(8)): ascii_art(lst(i)) # long time [ ] [ o ] [ ] [ o ] [ / \ ] [ o o ] [ ] [ ] [ ] [ __o__ ] [ / \ ] [ o o ] [ / \ / \ ] [ o o o o ]
- left_border_symmetry()[source]#
Return the tree where a symmetry has been applied recursively on all left borders. If a tree is made of three trees \([T_1, T_2, T_3]\) on its left border, it becomes \([T_3', T_2', T_1']\) where same symmetry has been applied to \(T_1, T_2, T_3\).
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[., .]]]
>>> from sage.all import * >>> BinaryTree().left_border_symmetry() . >>> BinaryTree([]).left_border_symmetry() [., .] >>> BinaryTree([[None,[]],None]).left_border_symmetry() [[., .], [., .]] >>> BinaryTree([[None,[None,[]]],None]).left_border_symmetry() [[., .], [., [., .]]] >>> bt = BinaryTree([[None,[None,[]]],None]).canonical_labelling() >>> bt 4[1[., 2[., 3[., .]]], .] >>> bt.left_border_symmetry() 1[4[., .], 2[., 3[., .]]]
- left_children_node_number(direction='left')[source]#
Return the number of nodes which are left children in
self
.Every node (except the root) is either the left child or the right child of its parent node. The total number of nodes is \(1\) plus the number of left-children nodes plus the number of right-children nodes.
INPUT:
direction
– either'left'
(default) or'right'
; if set to'right'
, instead count nodes that are right children
EXAMPLES:
sage: bt = BinaryTree([[None,[[],[]]],[None,[[],None]]]) sage: ascii_art(bt) __o__ / \ o o \ \ o o / \ / o o o sage: bt.left_children_node_number('left') 3 sage: bt.left_children_node_number('right') 4 sage: all(5 == 1 + bt.left_children_node_number() ....: + bt.left_children_node_number('right') ....: for bt in BinaryTrees(5)) True
>>> from sage.all import * >>> bt = BinaryTree([[None,[[],[]]],[None,[[],None]]]) >>> ascii_art(bt) __o__ / \ o o \ \ o o / \ / o o o >>> bt.left_children_node_number('left') 3 >>> bt.left_children_node_number('right') 4 >>> all(Integer(5) == Integer(1) + bt.left_children_node_number() ... + bt.left_children_node_number('right') ... for bt in BinaryTrees(Integer(5))) True
- left_right_symmetry()[source]#
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() [., [[., .], .]]
>>> from sage.all import * >>> BinaryTree().left_right_symmetry() . >>> BinaryTree([]).left_right_symmetry() [., .] >>> BinaryTree([[],None]).left_right_symmetry() [., [., .]] >>> BinaryTree([[None, []],None]).left_right_symmetry() [., [[., .], .]]
- left_rotate()[source]#
Return the result of left rotation applied to the binary tree
self
.Left rotation on binary trees is defined as follows: Let \(T\) be a binary tree such that the right child of the root of \(T\) is a node. Let \(A\) be the left child of the root of \(T\), and let \(B\) and \(C\) be the left and right children of the right child of the root of \(T\). (Keep in mind that nodes of trees are identified with the subtrees consisting of their descendants.) Then, the left rotation of \(T\) is the binary tree in which the right child of the root is \(C\), whereas the left child of the root is a node whose left and right children are \(A\) and \(B\). In pictures:
| * * | | / \ / \ | | A * -left-rotate-> * C | | / \ / \ | | B C A B |
where asterisks signify a single node each (but \(A\), \(B\) and \(C\) 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
>>> from sage.all import * >>> b = BinaryTree([[],[[],None]]); ascii_art([b]) [ _o_ ] [ / \ ] [ o o ] [ / ] [ o ] >>> ascii_art([b.left_rotate()]) [ o ] [ / ] [ o ] [ / \ ] [ o o ] >>> b.left_rotate().right_rotate() == b True
- make_leaf()[source]#
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 ([., .], .)
>>> from sage.all import * >>> t = BinaryTree([None, None]) >>> t.make_leaf() Traceback (most recent call last): ... ValueError: object is immutable; please change a copy instead. >>> with t.clone() as t1: ... t1.make_leaf() >>> t, t1 ([., .], .)
- make_node(child_list=[None, None])[source]#
Modify
self
so that it becomes a node with childrenchild_list
.INPUT:
child_list
– a pair of binary trees (or objects convertible to)
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 ([., .], [[., .], [., .]], [[., .], [[., .], [., .]]])
>>> from sage.all import * >>> t = BinaryTree() >>> t.make_node([None, None]) Traceback (most recent call last): ... ValueError: object is immutable; please change a copy instead. >>> with t.clone() as t1: ... t1.make_node([None, None]) >>> t, t1 (., [., .]) >>> with t.clone() as t: ... t.make_node([BinaryTree(), BinaryTree(), BinaryTree([])]) Traceback (most recent call last): ... ValueError: the list must have length 2 >>> with t1.clone() as t2: ... t2.make_node([t1, t1]) >>> with t2.clone() as t3: ... t3.make_node([t1, t2]) >>> t1, t2, t3 ([., .], [[., .], [., .]], [[., .], [[., .], [., .]]])
- over(bt)[source]#
Return
self
overbt
, where “over” is theover
(\(/\)) operation.If \(T\) and \(T'\) are two binary trees, then \(T\) over \(T'\) (written \(T / T'\)) is defined as the tree obtained by grafting \(T'\) on the rightmost leaf of \(T\). More precisely, \(T / T'\) is defined by identifying the root of the \(T'\) with the rightmost leaf of \(T\). See section 4.5 of [HNT2005].
If \(T\) is empty, then \(T / T' = T'\).
The definition of this “over” operation goes back to Loday-Ronco [LR0102066] (Definition 2.2), but it is denoted by \(\backslash\) and called the “under” operation there. In fact, trees in sage have their root at the top, contrary to the trees in [LR0102066] 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 [HNT2005].)
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 )
>>> from sage.all import * >>> b1 = BinaryTree([[],[[],[]]]) >>> b2 = BinaryTree([[None, []],[]]) >>> ascii_art((b1, b2, b1/b2)) ( _o_ , _o_ , _o_ ) ( / \ / \ / \ ) ( o o o o o o_ ) ( / \ \ / \ ) ( o o o o o ) ( \ ) ( _o_ ) ( / \ ) ( o o ) ( \ ) ( o )
- over_decomposition()[source]#
Return the unique maximal decomposition as an over product.
This means that the tree is cut along all edges of its rightmost path.
Beware that the factors are ordered starting from the root.
See also
EXAMPLES:
sage: g = BinaryTree([]) sage: r = g.over(g); r [., [., .]] sage: l = g.under(g); l [[., .], .] sage: r.over_decomposition() [[., .], [., .]] sage: l.over_decomposition() == [l] True sage: x = g.over(l).over(l).over(g).over(g) sage: ascii_art(x) o _o_ / o o / o o o sage: x.over_decomposition() == [g,l,l,g,g] True
>>> from sage.all import * >>> g = BinaryTree([]) >>> r = g.over(g); r [., [., .]] >>> l = g.under(g); l [[., .], .] >>> r.over_decomposition() [[., .], [., .]] >>> l.over_decomposition() == [l] True >>> x = g.over(l).over(l).over(g).over(g) >>> ascii_art(x) o _o_ / o o / o o o >>> x.over_decomposition() == [g,l,l,g,g] True
- prune()[source]#
Return the binary tree obtained by deleting each leaf of
self
.The operation of pruning is the left inverse of attaching as many leaves as possible to each node of a binary tree. That is to say, for all binary trees
bt
, we have:bt == bt.to_full().prune()
However, it is only a right inverse if and only if
bt
is a full binary tree:bt == bt.prune().to_full()
OUTPUT:
A binary tree.
See also
EXAMPLES:
sage: bt = BinaryTree([[[None, []], [[], []]], None]) sage: ascii_art(bt) o / __o__ / \ o o \ / \ o o o sage: ascii_art(bt.prune()) o / o / \ o o
>>> from sage.all import * >>> bt = BinaryTree([[[None, []], [[], []]], None]) >>> ascii_art(bt) o / __o__ / \ o o \ / \ o o o >>> ascii_art(bt.prune()) o / o / \ o o
We check the relationship with
to_full()
:sage: bt = BinaryTree([[[], [[None, []], []]], [[],[]]]) sage: bt == bt.to_full().prune() True sage: bt == bt.prune().to_full() False sage: bt = BinaryTree([[[], []], [[], [[[], []], []]]]) sage: bt.is_full() True sage: bt == bt.prune().to_full() True
>>> from sage.all import * >>> bt = BinaryTree([[[], [[None, []], []]], [[],[]]]) >>> bt == bt.to_full().prune() True >>> bt == bt.prune().to_full() False >>> bt = BinaryTree([[[], []], [[], [[[], []], []]]]) >>> bt.is_full() True >>> bt == bt.prune().to_full() True
Pruning the empty tree is again the empty tree:
sage: bt = BinaryTree(None) sage: bt.prune() .
>>> from sage.all import * >>> bt = BinaryTree(None) >>> bt.prune() .
- q_hook_length_fraction(q=None, q_factor=False)[source]#
Compute the
q
-hook length fraction of the binary treeself
, with an additional “q-factor” if desired.If \(T\) is a (plane) binary tree and \(q\) is a polynomial indeterminate over some ring, then the \(q\)-hook length fraction \(h_{q} (T)\) of \(T\) is defined by
\[h_{q} (T) = \frac{[\lvert T \rvert]_q!}{\prod_{t \in T} [\lvert T_t \rvert]_q},\]where the product ranges over all nodes \(t\) of \(T\), where \(T_t\) denotes the subtree of \(T\) consisting of \(t\) and its all descendants, and where for every tree \(S\), we denote by \(\lvert S \rvert\) the number of nodes of \(S\). While this definition only shows that \(h_{q} (T)\) is a rational function in \(T\), it is in fact easy to show that \(h_{q} (T)\) is actually a polynomial in \(T\), and thus makes sense when any element of a commutative ring is substituted for \(q\). This can also be explicitly seen from the following recursive formula for \(h_{q} (T)\):
\[h_{q} (T) = \binom{ \lvert T \rvert - 1 }{ \lvert T_1 \rvert }_q h_{q} (T_1) h_{q} (T_2),\]where \(T\) is any nonempty binary tree, and \(T_1\) and \(T_2\) are the two child trees of the root of \(T\), and where \(\binom{a}{b}_q\) denotes a \(q\)-binomial coefficient.
A variation of the \(q\)-hook length fraction is the following “\(q\)-hook length fraction with \(q\)-factor”:
\[f_{q} (T) = h_{q} (T) \cdot \prod_{t \in T} q^{\lvert T_{\mathrm{right}(t)} \rvert},\]where for every node \(t\), we denote by \(\mathrm{right}(t)\) the right child of \(t\). This \(f_{q} (T)\) differs from \(h_{q} (T)\) only in a multiplicative factor, which is a power of \(q\).
When \(q = 1\), both \(f_{q} (T)\) and \(h_{q} (T)\) equal the number of permutations whose binary search tree (see [HNT2005] for the definition) is \(T\) (after dropping the labels). For example, there are \(20\) 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 \(f_{1} (T) = 20\).
When \(q\) is considered as a polynomial indeterminate, \(f_{q} (T)\) is the generating function for all permutations whose binary search tree is \(T\) (after dropping the labels) with respect to the number of inversions (i. e., the Coxeter length) of the permutations.
Objects similar to \(h_{q} (T)\) also make sense for general ordered forests (rather than just binary trees), see e. g. [BW1988], Theorem 9.1.
INPUT:
q
– a ring element which is to be substituted as \(q\) into the \(q\)-hook length fraction (by default, this is set to be the indeterminate \(q\) in the polynomial ring \(\ZZ[q]\))q_factor
– a Boolean (default:False
) which determines whether to compute \(h_{q} (T)\) or to compute \(f_{q} (T)\) (namely, \(h_{q} (T)\) is obtained whenq_factor == False
, and \(f_{q} (T)\) is obtained whenq_factor == True
)
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() # needs sage.combinat 1 sage: b.q_hook_length_fraction(q_factor=True) # needs sage.combinat 1
>>> from sage.all import * >>> b = BinaryTree() >>> b.q_hook_length_fraction() # needs sage.combinat 1 >>> b.q_hook_length_fraction(q_factor=True) # needs sage.combinat 1
Nothing different for a tree with one node and two leaves:
sage: b = BinaryTree([]); b [., .] sage: b.q_hook_length_fraction() # needs sage.combinat 1 sage: b.q_hook_length_fraction(q_factor=True) # needs sage.combinat 1
>>> from sage.all import * >>> b = BinaryTree([]); b [., .] >>> b.q_hook_length_fraction() # needs sage.combinat 1 >>> b.q_hook_length_fraction(q_factor=True) # needs sage.combinat 1
Let us get to a more interesting tree:
sage: # needs sage.combinat 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
>>> from sage.all import * >>> # needs sage.combinat >>> b = BinaryTree([[[],[]],[[],None]]); b [[[., .], [., .]], [[., .], .]] >>> b.q_hook_length_fraction()(q=Integer(1)) 20 >>> 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 >>> 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 >>> b.q_hook_length_fraction(q=Integer(2)) 465 >>> b.q_hook_length_fraction(q=Integer(2), q_factor=True) 3720 >>> q = PolynomialRing(ZZ, 'q').gen() >>> b.q_hook_length_fraction(q=q**Integer(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 \(f_{q} (T)\) is the generating function for all permutations whose binary search tree is \(T\) (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) # needs sage.combinat True
>>> from sage.all import * >>> 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 >>> 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) ) >>> test_genfun(Integer(4)) # needs sage.combinat True
- right_rotate()[source]#
Return the result of right rotation applied to the binary tree
self
.Right rotation on binary trees is defined as follows: Let \(T\) be a binary tree such that the left child of the root of \(T\) is a node. Let \(C\) be the right child of the root of \(T\), and let \(A\) and \(B\) be the left and right children of the left child of the root of \(T\). (Keep in mind that nodes of trees are identified with the subtrees consisting of their descendants.) Then, the right rotation of \(T\) is the binary tree in which the left child of the root is \(A\), whereas the right child of the root is a node whose left and right children are \(B\) and \(C\). In pictures:
| * * | | / \ / \ | | * C -right-rotate-> A * | | / \ / \ | | A B B C |
where asterisks signify a single node each (but \(A\), \(B\) and \(C\) 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 [CP2012].
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 ]
>>> from sage.all import * >>> b = BinaryTree([[[],[]], None]); ascii_art([b]) [ o ] [ / ] [ o ] [ / \ ] [ o o ] >>> ascii_art([b.right_rotate()]) [ _o_ ] [ / \ ] [ o o ] [ / ] [ o ] >>> b = BinaryTree([[[[],None],[None,[]]], []]); ascii_art([b]) [ __o__ ] [ / \ ] [ o o ] [ / \ ] [ o o ] [ / \ ] [ o o ] >>> ascii_art([b.right_rotate()]) [ _o__ ] [ / \ ] [ o _o_ ] [ / / \ ] [ o o o ] [ \ ] [ o ]
- show(with_leaves=False)[source]#
Show the binary tree
show
, with or without leaves depending on the Boolean keyword variablewith_leaves
.Warning
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_()
orpretty_print
for more faithful representations of the data of the tree.
- single_edge_cut_shapes()[source]#
Return the list of possible single-edge cut shapes for the binary tree.
This is used in
sage.combinat.interval_posets.TamariIntervalPoset.is_new()
.OUTPUT:
a list of triples \((m, i, n)\) of integers
This is a list running over all inner edges (i.e., edges joining two non-leaf vertices) of the binary tree. The removal of each inner edge defines two binary trees (connected components), the root-tree and the sub-tree. Thus, to every inner edge, we can assign three positive integers: \(m\) is the node number of the root-tree \(R\), and \(n\) is the node number of the sub-tree \(S\). The integer \(i\) is the index of the leaf of \(R\) on which \(S\) is grafted to obtain the original tree. The leaves of \(R\) are numbered starting from \(1\) (from left to right), hence \(1 \leq i \leq m+1\).
In fact, each of \(m\) and \(n\) determines the other, as the total node number of \(R\) and \(S\) is the node number of
self
.EXAMPLES:
sage: BT = BinaryTrees(3) sage: [t.single_edge_cut_shapes() for t in BT] [[(2, 3, 1), (1, 2, 2)], [(2, 2, 1), (1, 2, 2)], [(2, 1, 1), (2, 3, 1)], [(2, 2, 1), (1, 1, 2)], [(2, 1, 1), (1, 1, 2)]] sage: BT = BinaryTrees(2) sage: [t.single_edge_cut_shapes() for t in BT] [[(1, 2, 1)], [(1, 1, 1)]] sage: BT = BinaryTrees(1) sage: [t.single_edge_cut_shapes() for t in BT] [[]]
>>> from sage.all import * >>> BT = BinaryTrees(Integer(3)) >>> [t.single_edge_cut_shapes() for t in BT] [[(2, 3, 1), (1, 2, 2)], [(2, 2, 1), (1, 2, 2)], [(2, 1, 1), (2, 3, 1)], [(2, 2, 1), (1, 1, 2)], [(2, 1, 1), (1, 1, 2)]] >>> BT = BinaryTrees(Integer(2)) >>> [t.single_edge_cut_shapes() for t in BT] [[(1, 2, 1)], [(1, 1, 1)]] >>> BT = BinaryTrees(Integer(1)) >>> [t.single_edge_cut_shapes() for t in BT] [[]]
- sylvester_class(left_to_right=False)[source]#
Iterate over the sylvester class corresponding to the binary tree
self
.The sylvester class of a tree \(T\) is the set of permutations \(\sigma\) whose right-to-left binary search tree (a notion defined in [HNT2005], Definition 7) is \(T\) after forgetting the labels. This is an equivalence class of the sylvester congruence (the congruence on words which holds two words \(uacvbw\) and \(ucavbw\) congruent whenever \(a\), \(b\), \(c\) are letters satisfying \(a \leq b < c\), and extends by transitivity) on the symmetric group.
For example the following tree’s sylvester class consists of the permutations \((1,3,2)\) and \((3,1,2)\):
[ 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 thebinary_search_tree()
method computes if it is given the keywordleft_to_right=False
.Here are two more descriptions of the sylvester class of a binary search tree:
The sylvester class of a binary search tree \(T\) is the set of all linear extensions of the poset corresponding to \(T\) (that is, of the poset whose Hasse diagram is \(T\), with the root on top), provided that the nodes of \(T\) are labelled with \(1, 2, \ldots, n\) in a binary-search-tree way (i.e., every left descendant of a node has a label smaller than that of the node, and every right descendant of a node has a label higher than that of the node).
The sylvester class of a binary search tree \(T\) (with vertex labels \(1, 2, \ldots, n\)) is the interval \([u, v]\) in the right permutohedron order (
permutohedron_lequal()
), where \(u\) is the 312-avoiding permutation corresponding to \(T\) (to_312_avoiding_permutation()
), and where \(v\) is the 132-avoiding permutation corresponding to \(T\) (to_132_avoiding_permutation()
).
If the optional keyword variable
left_to_right
is set toTrue
, then the left sylvester class ofself
is returned instead. This is the set of permutations \(\sigma\) whose left-to-right binary search tree (that is, the result of thebinary_search_tree()
withleft_to_right
set toTrue
) isself
. 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 \(t\) all equal \(t\):
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) # needs sage.combinat True sage: test_bst_of_sc(5, False) # long time # needs sage.combinat True
>>> from sage.all import * >>> 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 >>> test_bst_of_sc(Integer(4), False) # needs sage.combinat True >>> test_bst_of_sc(Integer(5), False) # long time # needs sage.combinat True
The same with the left-to-right version of binary search:
sage: test_bst_of_sc(4, True) # needs sage.combinat True sage: test_bst_of_sc(5, True) # long time # needs sage.combinat True
>>> from sage.all import * >>> test_bst_of_sc(Integer(4), True) # needs sage.combinat True >>> test_bst_of_sc(Integer(5), True) # long time # needs sage.combinat 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()) # needs sage.combinat sage.modules ....: == sorted(list(v) ....: for v in t.canonical_labelling().to_poset().linear_extensions()) ....: for t in BinaryTrees(4)) True
>>> from sage.all import * >>> all(sorted(t.canonical_labelling().sylvester_class()) # needs sage.combinat sage.modules ... == sorted(list(v) ... for v in t.canonical_labelling().to_poset().linear_extensions()) ... for t in BinaryTrees(Integer(4))) True
- tamari_greater()[source]#
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 |
- tamari_interval(other)[source]#
Return the Tamari interval between
self
andother
as aTamariIntervalPoset
.A “Tamari interval” is an interval in the Tamari poset. See
tamari_lequal()
for the definition of the Tamari poset.INPUT:
other
– a binary tree greater or equal toself
in the Tamari order
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
>>> from sage.all import * >>> bt = BinaryTree([[None, [[], None]], None]) >>> 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)] >>> ip.lower_binary_tree() [[., [[., .], .]], .] >>> ip.upper_binary_tree() [., [[., [., .]], .]] >>> ip.interval_cardinality() 4 >>> ip.number_of_tamari_inversions() 2 >>> list(ip.binary_trees()) [[., [[., [., .]], .]], [[., [., [., .]]], .], [., [[[., .], .], .]], [[., [[., .], .]], .]] >>> bt.tamari_interval(BinaryTree([[None,[]],[]])) Traceback (most recent call last): ... ValueError: the two binary trees are not comparable on the Tamari lattice
- tamari_join(other)[source]#
Return the join of the binary trees
self
andother
(of equal size) in the \(n\)-th Tamari poset (where \(n\) is the size of these trees).The \(n\)-th Tamari poset (defined in
tamari_lequal()
) is known to be a lattice, and the map from the \(n\)-th symmetric group \(S_n\) to the \(n\)-th Tamari poset defined by sending every permutation \(p \in S_n\) to the binary search tree of \(p\) (more precisely, top.binary_search_tree_shape()
) is a lattice homomorphism. (See Theorem 6.2 in [Rea2004].)See also
AUTHORS:
Viviane Pons and Darij Grinberg, 18 June 2014; Frédéric Chapoton, 9 January 2018.
EXAMPLES:
sage: a = BinaryTree([None, [None, []]]) sage: b = BinaryTree([None, [[], None]]) sage: c = BinaryTree([[None, []], None]) sage: d = BinaryTree([[[], None], None]) sage: e = BinaryTree([[], []]) sage: a.tamari_join(c) == a True sage: b.tamari_join(c) == b True sage: c.tamari_join(e) == a True sage: d.tamari_join(e) == e True sage: e.tamari_join(b) == a True sage: e.tamari_join(a) == a True
>>> from sage.all import * >>> a = BinaryTree([None, [None, []]]) >>> b = BinaryTree([None, [[], None]]) >>> c = BinaryTree([[None, []], None]) >>> d = BinaryTree([[[], None], None]) >>> e = BinaryTree([[], []]) >>> a.tamari_join(c) == a True >>> b.tamari_join(c) == b True >>> c.tamari_join(e) == a True >>> d.tamari_join(e) == e True >>> e.tamari_join(b) == a True >>> e.tamari_join(a) == a True
sage: b1 = BinaryTree([None, [[[], None], None]]) sage: b2 = BinaryTree([[[], None], []]) sage: b1.tamari_join(b2) [., [[., .], [., .]]] sage: b3 = BinaryTree([[], [[], None]]) sage: b1.tamari_join(b3) [., [., [[., .], .]]] sage: b2.tamari_join(b3) [[., .], [., [., .]]]
>>> from sage.all import * >>> b1 = BinaryTree([None, [[[], None], None]]) >>> b2 = BinaryTree([[[], None], []]) >>> b1.tamari_join(b2) [., [[., .], [., .]]] >>> b3 = BinaryTree([[], [[], None]]) >>> b1.tamari_join(b3) [., [., [[., .], .]]] >>> b2.tamari_join(b3) [[., .], [., [., .]]]
The universal property of the meet operation is satisfied:
sage: def test_uni_join(p, q): ....: j = p.tamari_join(q) ....: if not p.tamari_lequal(j): ....: return False ....: if not q.tamari_lequal(j): ....: return False ....: for r in p.tamari_greater(): ....: if q.tamari_lequal(r) and not j.tamari_lequal(r): ....: return False ....: return True sage: all( test_uni_join(p, q) for p in BinaryTrees(3) for q in BinaryTrees(3) ) True sage: p = BinaryTrees(6).random_element() # needs sage.combinat sage: q = BinaryTrees(6).random_element() # needs sage.combinat sage: test_uni_join(p, q) # needs sage.combinat True
>>> from sage.all import * >>> def test_uni_join(p, q): ... j = p.tamari_join(q) ... if not p.tamari_lequal(j): ... return False ... if not q.tamari_lequal(j): ... return False ... for r in p.tamari_greater(): ... if q.tamari_lequal(r) and not j.tamari_lequal(r): ... return False ... return True >>> all( test_uni_join(p, q) for p in BinaryTrees(Integer(3)) for q in BinaryTrees(Integer(3)) ) True >>> p = BinaryTrees(Integer(6)).random_element() # needs sage.combinat >>> q = BinaryTrees(Integer(6)).random_element() # needs sage.combinat >>> test_uni_join(p, q) # needs sage.combinat True
Border cases:
sage: b = BinaryTree(None) sage: b.tamari_join(b) . sage: b = BinaryTree([]) sage: b.tamari_join(b) [., .]
>>> from sage.all import * >>> b = BinaryTree(None) >>> b.tamari_join(b) . >>> b = BinaryTree([]) >>> b.tamari_join(b) [., .]
- tamari_lequal(t2)[source]#
Return
True
ifself
is less or equal to another binary treet2
(of the same size asself
) in the Tamari order.The Tamari order on binary trees of size \(n\) is the partial order on the set of all binary trees of size \(n\) generated by the following requirement: If a binary tree \(T'\) is obtained by right rotation (see
right_rotate()
) from a binary tree \(T\), then \(T < T'\). This not only is a well-defined partial order, but actually is a lattice structure on the set of binary trees of size \(n\), and is a quotient of the weak order on the \(n\)-th symmetric group (also known as the right permutohedron order, seepermutohedron_lequal()
). See [CP2012]. The set of binary trees of size \(n\) equipped with the Tamari order is called the \(n\)-th Tamari poset.The Tamari order can equivalently be defined as follows:
If \(T\) and \(S\) are two binary trees of size \(n\), then the following four statements are equivalent:
We have \(T \leq S\) in the Tamari order.
There exist elements \(t\) and \(s\) of the Sylvester classes (
sylvester_class()
) of \(T\) and \(S\), respectively, such that \(t \leq s\) in the weak order on the symmetric group.The 132-avoiding permutation corresponding to \(T\) (see
to_132_avoiding_permutation()
) is \(\leq\) to the 132-avoiding permutation corresponding to \(S\) in the weak order on the symmetric group.The 312-avoiding permutation corresponding to \(T\) (see
to_312_avoiding_permutation()
) is \(\leq\) to the 312-avoiding permutation corresponding to \(S\) in the weak order on the symmetric group.
EXAMPLES:
This tree:
| o | | / \ | | o o | | / | | o | | / \ | | o o |
is Tamari-\(\leq\) 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
>>> from sage.all import * >>> b = BinaryTree([[[[], []], None], []]) >>> c = BinaryTree([[[],[]],[None,[]]]) >>> b.tamari_lequal(c) True
- tamari_meet(other, side='right')[source]#
Return the meet of the binary trees
self
andother
(of equal size) in the \(n\)-th Tamari poset (where \(n\) is the size of these trees).The \(n\)-th Tamari poset (defined in
tamari_lequal()
) is known to be a lattice, and the map from the \(n\)-th symmetric group \(S_n\) to the \(n\)-th Tamari poset defined by sending every permutation \(p \in S_n\) to the binary search tree of \(p\) (more precisely, top.binary_search_tree_shape()
) is a lattice homomorphism. (See Theorem 6.2 in [Rea2004].)See also
AUTHORS:
Viviane Pons and Darij Grinberg, 18 June 2014.
EXAMPLES:
sage: a = BinaryTree([None, [None, []]]) sage: b = BinaryTree([None, [[], None]]) sage: c = BinaryTree([[None, []], None]) sage: d = BinaryTree([[[], None], None]) sage: e = BinaryTree([[], []]) sage: a.tamari_meet(c) == c True sage: b.tamari_meet(c) == c True sage: c.tamari_meet(e) == d True sage: d.tamari_meet(e) == d True sage: e.tamari_meet(b) == d True sage: e.tamari_meet(a) == e True
>>> from sage.all import * >>> a = BinaryTree([None, [None, []]]) >>> b = BinaryTree([None, [[], None]]) >>> c = BinaryTree([[None, []], None]) >>> d = BinaryTree([[[], None], None]) >>> e = BinaryTree([[], []]) >>> a.tamari_meet(c) == c True >>> b.tamari_meet(c) == c True >>> c.tamari_meet(e) == d True >>> d.tamari_meet(e) == d True >>> e.tamari_meet(b) == d True >>> e.tamari_meet(a) == e True
sage: b1 = BinaryTree([None, [[[], None], None]]) sage: b2 = BinaryTree([[[], None], []]) sage: b1.tamari_meet(b2) [[[[., .], .], .], .] sage: b3 = BinaryTree([[], [[], None]]) sage: b1.tamari_meet(b3) [[[[., .], .], .], .] sage: b2.tamari_meet(b3) [[[[., .], .], .], .]
>>> from sage.all import * >>> b1 = BinaryTree([None, [[[], None], None]]) >>> b2 = BinaryTree([[[], None], []]) >>> b1.tamari_meet(b2) [[[[., .], .], .], .] >>> b3 = BinaryTree([[], [[], None]]) >>> b1.tamari_meet(b3) [[[[., .], .], .], .] >>> b2.tamari_meet(b3) [[[[., .], .], .], .]
The universal property of the meet operation is satisfied:
sage: def test_uni_meet(p, q): ....: m = p.tamari_meet(q) ....: if not m.tamari_lequal(p): ....: return False ....: if not m.tamari_lequal(q): ....: return False ....: for r in p.tamari_smaller(): ....: if r.tamari_lequal(q) and not r.tamari_lequal(m): ....: return False ....: return True sage: all( test_uni_meet(p, q) for p in BinaryTrees(3) for q in BinaryTrees(3) ) True sage: p = BinaryTrees(6).random_element() # needs sage.combinat sage: q = BinaryTrees(6).random_element() # needs sage.combinat sage: test_uni_meet(p, q) # needs sage.combinat True
>>> from sage.all import * >>> def test_uni_meet(p, q): ... m = p.tamari_meet(q) ... if not m.tamari_lequal(p): ... return False ... if not m.tamari_lequal(q): ... return False ... for r in p.tamari_smaller(): ... if r.tamari_lequal(q) and not r.tamari_lequal(m): ... return False ... return True >>> all( test_uni_meet(p, q) for p in BinaryTrees(Integer(3)) for q in BinaryTrees(Integer(3)) ) True >>> p = BinaryTrees(Integer(6)).random_element() # needs sage.combinat >>> q = BinaryTrees(Integer(6)).random_element() # needs sage.combinat >>> test_uni_meet(p, q) # needs sage.combinat True
Border cases:
sage: b = BinaryTree(None) sage: b.tamari_meet(b) . sage: b = BinaryTree([]) sage: b.tamari_meet(b) [., .]
>>> from sage.all import * >>> b = BinaryTree(None) >>> b.tamari_meet(b) . >>> b = BinaryTree([]) >>> b.tamari_meet(b) [., .]
- tamari_pred()[source]#
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 |
- tamari_smaller()[source]#
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 |
- tamari_sorting_tuple(reverse=False)[source]#
Return the Tamari sorting tuple of
self
and the size ofself
.This is a pair \((w, n)\), where \(n\) is the number of nodes of
self
, and \(w\) is an \(n\)-tuple whose \(i\)-th entry is the number of all nodes among the descendants of the right child of the \(i\)-th node ofself
. Here, the nodes ofself
are numbered from left to right.INPUT:
reverse
– boolean (defaultFalse
) ifTrue
, return instead the result for the left-right symmetric of the binary tree
OUTPUT:
a pair \((w, n)\), where \(w\) is a tuple of integers, and \(n\) the size
Two binary trees of the same size are comparable in the Tamari order if and only if the associated tuples \(w\) are componentwise comparable. (This is essentially the Theorem in [HT1972].) This is used in
tamari_lequal()
.EXAMPLES:
sage: [t.tamari_sorting_tuple() for t in BinaryTrees(3)] [((2, 1, 0), 3), ((2, 0, 0), 3), ((0, 1, 0), 3), ((1, 0, 0), 3), ((0, 0, 0), 3)] sage: t = BinaryTrees(10).random_element() # needs sage.combinat sage: u = t.left_right_symmetry() # needs sage.combinat sage: t.tamari_sorting_tuple(True) == u.tamari_sorting_tuple() # needs sage.combinat True
>>> from sage.all import * >>> [t.tamari_sorting_tuple() for t in BinaryTrees(Integer(3))] [((2, 1, 0), 3), ((2, 0, 0), 3), ((0, 1, 0), 3), ((1, 0, 0), 3), ((0, 0, 0), 3)] >>> t = BinaryTrees(Integer(10)).random_element() # needs sage.combinat >>> u = t.left_right_symmetry() # needs sage.combinat >>> t.tamari_sorting_tuple(True) == u.tamari_sorting_tuple() # needs sage.combinat True
REFERENCES:
- tamari_succ()[source]#
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 |
- to_132_avoiding_permutation()[source]#
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]
>>> from sage.all import * >>> bt = BinaryTree([[],[]]) >>> bt.to_132_avoiding_permutation() [3, 1, 2] >>> bt = BinaryTree([[[], [[], None]], [[], []]]) >>> bt.to_132_avoiding_permutation() [8, 6, 7, 3, 4, 1, 2, 5]
- to_312_avoiding_permutation()[source]#
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]
>>> from sage.all import * >>> bt = BinaryTree([[],[]]) >>> bt.to_312_avoiding_permutation() [1, 3, 2] >>> bt = BinaryTree([[[], [[], None]], [[], []]]) >>> bt.to_312_avoiding_permutation() [1, 3, 4, 2, 6, 8, 7, 5]
- to_dyck_word(usemap='1L0R')[source]#
Return the Dyck word associated with
self
using the given map.INPUT:
usemap
– a string, either1L0R
,1R0L
,L1R0
,R1L0
The bijection is defined recursively as follows:
a leaf is associated to the empty Dyck Word
a tree with children \(l,r\) is associated with the Dyck word described by
usemap
where \(L\) and \(R\) are respectively the Dyck words associated with the trees \(l\) and \(r\).
EXAMPLES:
sage: # needs sage.combinat 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
>>> from sage.all import * >>> # needs sage.combinat >>> BinaryTree().to_dyck_word() [] >>> BinaryTree([]).to_dyck_word() [1, 0] >>> BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word() [1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0] >>> BinaryTree([[None,[]],None]).to_dyck_word() [1, 1, 0, 1, 0, 0] >>> BinaryTree([[None,[]],None]).to_dyck_word("1R0L") [1, 0, 1, 1, 0, 0] >>> BinaryTree([[None,[]],None]).to_dyck_word("L1R0") [1, 1, 0, 0, 1, 0] >>> BinaryTree([[None,[]],None]).to_dyck_word("R1L0") [1, 1, 0, 1, 0, 0] >>> BinaryTree([[None,[]],None]).to_dyck_word("R10L") Traceback (most recent call last): ... ValueError: R10L is not a correct map
- to_dyck_word_tamari()[source]#
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:
a leaf is associated with an empty Dyck word;
a tree with children \(l,r\) is associated with the Dyck word \(T(l) 1 T(r) 0\).
EXAMPLES:
sage: # needs sage.combinat 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]
>>> from sage.all import * >>> # needs sage.combinat >>> BinaryTree().to_dyck_word_tamari() [] >>> BinaryTree([]).to_dyck_word_tamari() [1, 0] >>> BinaryTree([[None,[]],None]).to_dyck_word_tamari() [1, 1, 0, 0, 1, 0] >>> BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word_tamari() [1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
- to_full()[source]#
Return the full binary tree constructed from
self
.Let \(T\) be a binary tree with \(n\) nodes. We construct a full binary tree \(F\) from \(T\) by attaching a leaf to each node of \(T\) which does not have 2 children. The resulting tree will have \(2n + 1\) nodes.
OUTPUT:
A full binary tree. See
is_full()
for the definition of full.See also
EXAMPLES:
sage: bt = BinaryTree([[None,[]],None]) sage: bt.to_full().is_full() True sage: ascii_art(bt) o / o \ o sage: ascii_art(bt.to_full()) __o___ / \ _o_ o / \ o o / \ o o sage: bt = BinaryTree([[],[]]) sage: ascii_art(bt) o / \ o o sage: ascii_art(bt.to_full()) __o__ / \ o o / \ / \ o o o o sage: BinaryTree(None).to_full() [., .]
>>> from sage.all import * >>> bt = BinaryTree([[None,[]],None]) >>> bt.to_full().is_full() True >>> ascii_art(bt) o / o \ o >>> ascii_art(bt.to_full()) __o___ / \ _o_ o / \ o o / \ o o >>> bt = BinaryTree([[],[]]) >>> ascii_art(bt) o / \ o o >>> ascii_art(bt.to_full()) __o__ / \ o o / \ / \ o o o o >>> BinaryTree(None).to_full() [., .]
- to_ordered_tree_left_branch()[source]#
Return an ordered tree of size \(n+1\) by the following recursive rule:
if \(x\) is the left child of \(y\), \(x\) becomes the left brother of \(y\)
if \(x\) is the right child of \(y\), \(x\) becomes the last child of \(y\)
EXAMPLES:
sage: bt = BinaryTree([[],[]]) sage: bt.to_ordered_tree_left_branch() [[], [[]]] sage: bt = BinaryTree([[[], [[], None]], [[], []]]) sage: bt.to_ordered_tree_left_branch() [[], [[], []], [[], [[]]]]
>>> from sage.all import * >>> bt = BinaryTree([[],[]]) >>> bt.to_ordered_tree_left_branch() [[], [[]]] >>> bt = BinaryTree([[[], [[], None]], [[], []]]) >>> bt.to_ordered_tree_left_branch() [[], [[], []], [[], [[]]]]
- to_ordered_tree_right_branch()[source]#
Return an ordered tree of size \(n+1\) by the following recursive rule:
if \(x\) is the right child of \(y\), \(x\) becomes the right brother of \(y\)
if \(x\) is the left child of \(y\), \(x\) becomes the first child of \(y\)
EXAMPLES:
sage: bt = BinaryTree([[],[]]) sage: bt.to_ordered_tree_right_branch() [[[]], []] sage: bt = BinaryTree([[[], [[], None]], [[], []]]) sage: bt.to_ordered_tree_right_branch() [[[[]], [[]]], [[]], []]
>>> from sage.all import * >>> bt = BinaryTree([[],[]]) >>> bt.to_ordered_tree_right_branch() [[[]], []] >>> bt = BinaryTree([[[], [[], None]], [[], []]]) >>> bt.to_ordered_tree_right_branch() [[[[]], [[]]], [[]], []]
- to_poset(with_leaves=False, root_to_leaf=False)[source]#
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
toTrue
to obtain the poset of the complete tree.INPUT:
with_leaves
– (default:False
) a Boolean, determining whether the resulting poset will be formed from the leaves and the nodes ofself
(ifTrue
), or only from the nodes ofself
(ifFalse
)root_to_leaf
– (default:False
) a Boolean, determining whether the poset orientation should be from root to leaves (ifTrue
) or from leaves to root (ifFalse
).
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: P1 = bt.to_poset(with_leaves=True) sage: len(P1.maximal_elements()) 1 sage: len(P1.minimal_elements()) 2 sage: bt = BinaryTree([]) sage: P2 = bt.to_poset(with_leaves=True,root_to_leaf=True) sage: len(P2.maximal_elements()) 2 sage: len(P2.minimal_elements()) 1
>>> from sage.all import * >>> bt = BinaryTree([]) >>> bt.to_poset() Finite poset containing 1 elements >>> bt.to_poset(with_leaves=True) Finite poset containing 3 elements >>> P1 = bt.to_poset(with_leaves=True) >>> len(P1.maximal_elements()) 1 >>> len(P1.minimal_elements()) 2 >>> bt = BinaryTree([]) >>> P2 = bt.to_poset(with_leaves=True,root_to_leaf=True) >>> len(P2.maximal_elements()) 2 >>> len(P2.minimal_elements()) 1
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]]
>>> from sage.all import * >>> bt = BinaryTree([[],[None,[]]]).canonical_labelling() >>> bt 2[1[., .], 3[., 4[., .]]] >>> 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
>>> from sage.all import * >>> bt = BinaryTree() >>> bt.to_poset() Finite poset containing 0 elements >>> bt.to_poset(with_leaves=True) Finite poset containing 1 elements
- to_tilting()[source]#
Transform a binary tree into a tilting object.
Let \(t\) be a binary tree with \(n\) nodes. There exists a unique depiction of \(t\) (above the diagonal) such that all leaves are regularly distributed on the diagonal line from \((0,0)\) to \((n,n)\) and all edges are either horizontal or vertical. This method provides the coordinates of this depiction, with the root as the top-left vertex.
OUTPUT:
a list of pairs of integers.
Every vertex of the binary tree is mapped to a pair of integers. The conventions are the following. The root has coordinates \((0, n)\) where \(n\) is the node number. If a vertex is the left (right) son of another vertex, they share the first (second) coordinate.
EXAMPLES:
sage: t = BinaryTrees(1)[0] sage: t.to_tilting() [(0, 1)] sage: for t in BinaryTrees(2): ....: print(t.to_tilting()) [(1, 2), (0, 2)] [(0, 1), (0, 2)] sage: from sage.combinat.abstract_tree import from_hexacode sage: t = from_hexacode('2020222002000', BinaryTrees()) sage: print(t.to_tilting()) [(0, 1), (2, 3), (4, 5), (6, 7), (4, 7), (8, 9), (10, 11), (8, 11), (4, 11), (12, 13), (4, 13), (2, 13), (0, 13)] sage: w = DyckWord([1,1,1,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,1,1,0,0,0,0,0,0]) # needs sage.combinat sage: t2 = w.to_binary_tree() # needs sage.combinat sage: len(t2.to_tilting()) == t2.node_number() # needs sage.combinat True
>>> from sage.all import * >>> t = BinaryTrees(Integer(1))[Integer(0)] >>> t.to_tilting() [(0, 1)] >>> for t in BinaryTrees(Integer(2)): ... print(t.to_tilting()) [(1, 2), (0, 2)] [(0, 1), (0, 2)] >>> from sage.combinat.abstract_tree import from_hexacode >>> t = from_hexacode('2020222002000', BinaryTrees()) >>> print(t.to_tilting()) [(0, 1), (2, 3), (4, 5), (6, 7), (4, 7), (8, 9), (10, 11), (8, 11), (4, 11), (12, 13), (4, 13), (2, 13), (0, 13)] >>> w = DyckWord([Integer(1),Integer(1),Integer(1),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)]) # needs sage.combinat >>> t2 = w.to_binary_tree() # needs sage.combinat >>> len(t2.to_tilting()) == t2.node_number() # needs sage.combinat True
- to_undirected_graph(with_leaves=False)[source]#
Return the undirected graph obtained from the tree nodes and edges.
Leaves are ignored by default, but one can set
with_leaves
toTrue
to obtain the graph of the complete tree.INPUT:
with_leaves
– (default:False
) a Boolean, determining whether the resulting graph will be formed from the leaves and the nodes ofself
(ifTrue
), or only from the nodes ofself
(ifFalse
)
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
>>> from sage.all import * >>> bt = BinaryTree([]) >>> bt.to_undirected_graph() Graph on 1 vertex >>> bt.to_undirected_graph(with_leaves=True) Graph on 3 vertices >>> bt = BinaryTree() >>> bt.to_undirected_graph() Graph on 0 vertices >>> 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().to_undirected_graph() == bt.to_undirected_graph() False sage: BinaryTree([[],[]]).to_undirected_graph() == BinaryTree([[[],None],None]).to_undirected_graph() True
>>> from sage.all import * >>> bt = BinaryTree([[],[None,[]]]) >>> bt.canonical_labelling().to_undirected_graph() == bt.to_undirected_graph() False >>> BinaryTree([[],[]]).to_undirected_graph() == BinaryTree([[[],None],None]).to_undirected_graph() True
- twisting_number()[source]#
Return a pair (number of maximal left branches, number of maximal right branches).
Recalling that a branch of a vertex \(v\) is a path from a vertex of the tree to a leaf, a left (resp. right) branch is a branch made only of left (resp. right) edges. The length of a branch is the number of edges composing it. A left (resp. right) branch is maximal if it is not included in a strictly longer left (resp. right) branch.
OUTPUT:
A list of two integers
EXAMPLES:
sage: BT = BinaryTree( '.' ) sage: BT.twisting_number() [0, 0] sage: BT = BinaryTree( '[.,.]' ) sage: BT.twisting_number() [0, 0] sage: BT = BinaryTree( '[[[.,.], .], [.,.]]' ); ascii_art(BT) o / \ o o / o sage: BT.twisting_number() [1, 1] sage: BT = BinaryTree( '[[[[., [., .]], .], [[., .], [[[., .], [., .]], [., .]]]], [., [[[., .], [[[., .], [., .]], .]], .]]]' ) sage: ascii_art(BT) ________o________ / \ __o__ o / \ \ o __o___ o / / \ / o o _o_ __o__ \ / \ / \ o o o o o / \ / o o o / \ o o sage: BT.twisting_number() [5, 6] sage: BT = BinaryTree( '[.,[[[.,.],.],.]]' ); ascii_art(BT) o \ o / o / o sage: BT.twisting_number() [1, 1]
>>> from sage.all import * >>> BT = BinaryTree( '.' ) >>> BT.twisting_number() [0, 0] >>> BT = BinaryTree( '[.,.]' ) >>> BT.twisting_number() [0, 0] >>> BT = BinaryTree( '[[[.,.], .], [.,.]]' ); ascii_art(BT) o / \ o o / o >>> BT.twisting_number() [1, 1] >>> BT = BinaryTree( '[[[[., [., .]], .], [[., .], [[[., .], [., .]], [., .]]]], [., [[[., .], [[[., .], [., .]], .]], .]]]' ) >>> ascii_art(BT) ________o________ / \ __o__ o / \ \ o __o___ o / / \ / o o _o_ __o__ \ / \ / \ o o o o o / \ / o o o / \ o o >>> BT.twisting_number() [5, 6] >>> BT = BinaryTree( '[.,[[[.,.],.],.]]' ); ascii_art(BT) o \ o / o / o >>> BT.twisting_number() [1, 1]
- under(bt)[source]#
Return
self
underbt
, where “under” is theunder
(\(\backslash\)) operation.If \(T\) and \(T'\) are two binary trees, then \(T\) under \(T'\) (written \(T \backslash T'\)) is defined as the tree obtained by grafting \(T\) on the leftmost leaf of \(T'\). More precisely, \(T \backslash T'\) is defined by identifying the root of \(T\) with the leftmost leaf of \(T'\).
If \(T'\) is empty, then \(T \backslash T' = T\).
The definition of this “under” operation goes back to Loday-Ronco [LR0102066] (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 [LR0102066] 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 [HNT2005].)
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.under(b2))) ( o , o , _o_ ) ( / \ \ / \ ) ( o o o o o ) ( / \ ) ( o o )
>>> from sage.all import * >>> b1 = BinaryTree([[],[]]) >>> b2 = BinaryTree([None,[]]) >>> ascii_art((b1, b2, b1.under(b2))) ( o , o , _o_ ) ( / \ \ / \ ) ( o o o o o ) ( / \ ) ( o o )
- under_decomposition()[source]#
Return the unique maximal decomposition as an under product.
This means that the tree is cut along all edges of its leftmost path.
Beware that the factors are ordered starting from the root.
See also
EXAMPLES:
sage: g = BinaryTree([]) sage: r = g.over(g); r [., [., .]] sage: l = g.under(g); l [[., .], .] sage: l.under_decomposition() [[., .], [., .]] sage: r.under_decomposition() == [r] True sage: x = r.under(g).under(r).under(g) sage: ascii_art(x) o / o / \ o o / o \ o sage: x.under_decomposition() == [g,r,g,r] True
>>> from sage.all import * >>> g = BinaryTree([]) >>> r = g.over(g); r [., [., .]] >>> l = g.under(g); l [[., .], .] >>> l.under_decomposition() [[., .], [., .]] >>> r.under_decomposition() == [r] True >>> x = r.under(g).under(r).under(g) >>> ascii_art(x) o / o / \ o o / o \ o >>> x.under_decomposition() == [g,r,g,r] True
- class sage.combinat.binary_tree.BinaryTrees[source]#
Bases:
UniqueRepresentation
,Parent
Factory for binary trees.
A binary tree is a tree with at most 2 children. The binary trees considered here are also ordered (a.k.a. planar), that is to say, their children are ordered.
A full binary tree is a binary tree with no nodes with 1 child.
INPUT:
size
– (optional) an integerfull
– (optional) a boolean
OUTPUT:
The set of all (full if
full=True
) binary trees (of the givensize
if specified).See also
EXAMPLES:
sage: BinaryTrees() Binary trees sage: BinaryTrees(2) Binary trees of size 2 sage: BinaryTrees(full=True) Full binary trees sage: BinaryTrees(3, full=True) Full binary trees of size 3 sage: BinaryTrees(4, full=True) Traceback (most recent call last): ... ValueError: n must be 0 or odd
>>> from sage.all import * >>> BinaryTrees() Binary trees >>> BinaryTrees(Integer(2)) Binary trees of size 2 >>> BinaryTrees(full=True) Full binary trees >>> BinaryTrees(Integer(3), full=True) Full binary trees of size 3 >>> BinaryTrees(Integer(4), full=True) Traceback (most recent call last): ... ValueError: n must be 0 or odd
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.
- class sage.combinat.binary_tree.BinaryTrees_all[source]#
Bases:
DisjointUnionEnumeratedSets
,BinaryTrees
- Element[source]#
alias of
BinaryTree
- class sage.combinat.binary_tree.BinaryTrees_size(size)[source]#
Bases:
BinaryTrees
The enumerated sets of binary trees of given size.
- random_element()[source]#
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 # needs sage.combinat [., [., [., [., [., .]]]]] sage: BinaryTrees(0).random_element() # needs sage.combinat . sage: BinaryTrees(1).random_element() # needs sage.combinat [., .]
>>> from sage.all import * >>> BinaryTrees(Integer(5)).random_element() # random # needs sage.combinat [., [., [., [., [., .]]]]] >>> BinaryTrees(Integer(0)).random_element() # needs sage.combinat . >>> BinaryTrees(Integer(1)).random_element() # needs sage.combinat [., .]
- class sage.combinat.binary_tree.FullBinaryTrees_all[source]#
Bases:
DisjointUnionEnumeratedSets
,BinaryTrees
All full binary trees.
- class sage.combinat.binary_tree.FullBinaryTrees_size(size)[source]#
Bases:
BinaryTrees
Full binary trees of a fixed size (number of nodes).
- random_element()[source]#
Return a random
FullBinaryTree
with uniform probability.This method generates a random
DyckWord
of size \((s-1) / 2\), where \(s\) is the size ofself
, which uses a bijection between Dyck words and binary trees to get a binary tree, and convert it to a full binary tree.EXAMPLES:
sage: BinaryTrees(5, full=True).random_element() # random # needs sage.combinat [[], [[], []]] sage: BinaryTrees(0, full=True).random_element() # needs sage.combinat . sage: BinaryTrees(1, full=True).random_element() # needs sage.combinat [., .]
>>> from sage.all import * >>> BinaryTrees(Integer(5), full=True).random_element() # random # needs sage.combinat [[], [[], []]] >>> BinaryTrees(Integer(0), full=True).random_element() # needs sage.combinat . >>> BinaryTrees(Integer(1), full=True).random_element() # needs sage.combinat [., .]
- class sage.combinat.binary_tree.LabelledBinaryTree(parent, children, label=None, check=True)[source]#
Bases:
AbstractLabelledClonableTree
,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 \(2\) 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:a pair of labelled binary trees,
and a label.
(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 toLabelledBinaryTree([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 alabel
variable without callingLabelledBinaryTree
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 forLabelledBinaryTree(None)
(in analogy to similar syntax in theBinaryTree
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[., .], .], .]
>>> from sage.all import * >>> LabelledBinaryTree(None) . >>> LabelledBinaryTree(None, label="ae") # not well supported 'ae' >>> LabelledBinaryTree([]) None[., .] >>> LabelledBinaryTree([], label=Integer(3)) # not well supported 3[., .] >>> LabelledBinaryTree([None, None]) None[., .] >>> LabelledBinaryTree([None, None], label=Integer(5)) 5[., .] >>> LabelledBinaryTree([None, []]) None[., None[., .]] >>> LabelledBinaryTree([None, []], label=Integer(4)) 4[., None[., .]] >>> LabelledBinaryTree([[], None]) None[None[., .], .] >>> LabelledBinaryTree("[[], .]", label=False) False[None[., .], .] >>> LabelledBinaryTree([None, LabelledBinaryTree([None, None], label=Integer(4))], label=Integer(3)) 3[., 4[., .]] >>> LabelledBinaryTree([None, BinaryTree([None, None])], label=Integer(3)) 3[., None[., .]] >>> LabelledBinaryTree([[], None, []]) Traceback (most recent call last): ... ValueError: this is not a binary tree >>> LBT = LabelledBinaryTree >>> t1 = LBT([[LBT([], label=Integer(2)), None], None], label=Integer(4)); t1 4[None[2[., .], .], .]
- binary_search_insert(letter)[source]#
Return the result of inserting a letter
letter
into the right strict binary search treeself
.INPUT:
letter
– any object comparable with the labels ofself
OUTPUT:
The right strict binary search tree
self
withletter
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 \(n\) with label \(x\), every descendant of the left child of \(n\) has a label \(\leq x\), and every descendant of the right child of \(n\) has a label \(> x\). (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 \(t\) and a letter \(i\), the result of inserting \(i\) into \(t\) (denoted \(Ins(i, t)\) in the following) is defined recursively as follows:
If \(t\) is empty, then \(Ins(i, t)\) is the tree with one node only, and this node is labelled with \(i\).
Otherwise, let \(j\) be the label of the root of \(t\). If \(i > j\), then \(Ins(i, t)\) is obtained by replacing the right child of \(t\) by \(Ins(i, r)\) in \(t\), where \(r\) denotes the right child of \(t\). If \(i \leq j\), then \(Ins(i, t)\) is obtained by replacing the left child of \(t\) by \(Ins(i, l)\) in \(t\), where \(l\) denotes the left child of \(t\).
See, for example, [HNT2005] for properties of this algorithm.
Warning
If \(t\) is nonempty, then inserting \(i\) into \(t\) does not change the root label of \(t\). Hence, as opposed to algorithms like Robinson-Schensted-Knuth, binary search tree insertion involves no bumping.
EXAMPLES:
The example from Fig. 2 of [HNT2005]:
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[., .]]]
>>> from sage.all import * >>> LBT = LabelledBinaryTree >>> x = LBT(None) >>> x . >>> x = x.binary_search_insert("b"); x b[., .] >>> x = x.binary_search_insert("d"); x b[., d[., .]] >>> x = x.binary_search_insert("e"); x b[., d[., e[., .]]] >>> x = x.binary_search_insert("a"); x b[a[., .], d[., e[., .]]] >>> x = x.binary_search_insert("b"); x b[a[., b[., .]], d[., e[., .]]] >>> x = x.binary_search_insert("d"); x b[a[., b[., .]], d[d[., .], e[., .]]] >>> x = x.binary_search_insert("a"); x b[a[a[., .], b[., .]], d[d[., .], e[., .]]] >>> 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[., .]]]
>>> from sage.all import * >>> LBT = LabelledBinaryTree >>> LBT(None).binary_search_insert(Integer(3)) 3[., .] >>> LBT([], label = Integer(1)).binary_search_insert(Integer(3)) 1[., 3[., .]] >>> LBT([], label = Integer(3)).binary_search_insert(Integer(1)) 3[1[., .], .] >>> res = LBT(None) >>> for i in [Integer(3),Integer(1),Integer(5),Integer(2),Integer(4),Integer(6)]: ... res = res.binary_search_insert(i) >>> res 3[1[., 2[., .]], 5[4[., .], 6[., .]]]
- heap_insert(l)[source]#
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:
letter
– any object comparable with the labels ofself
Note
self
is assumed to be a binary heap (tree). No check is performed.
- left_rotate()[source]#
Return the result of left rotation applied to the labelled binary tree
self
.Left rotation on labelled binary trees is defined as follows: Let \(T\) be a labelled binary tree such that the right child of the root of \(T\) is a node. Let \(A\) be the left child of the root of \(T\), and let \(B\) and \(C\) be the left and right children of the right child of the root of \(T\). (Keep in mind that nodes of trees are identified with the subtrees consisting of their descendants.) Furthermore, let \(x\) be the label at the root of \(T\), and \(y\) be the label at the right child of the root of \(T\). Then, the left rotation of \(T\) is the labelled binary tree in which the root is labelled \(y\), the right child of the root is \(C\), whereas the left child of the root is a node labelled \(x\) whose left and right children are \(A\) and \(B\). 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()
).
- right_rotate()[source]#
Return the result of right rotation applied to the labelled binary tree
self
.Right rotation on labelled binary trees is defined as follows: Let \(T\) be a labelled binary tree such that the left child of the root of \(T\) is a node. Let \(C\) be the right child of the root of \(T\), and let \(A\) and \(B\) be the left and right children of the left child of the root of \(T\). (Keep in mind that nodes of trees are identified with the subtrees consisting of their descendants.) Furthermore, let \(y\) be the label at the root of \(T\), and \(x\) be the label at the left child of the root of \(T\). Then, the right rotation of \(T\) is the labelled binary tree in which the root is labelled \(x\), the left child of the root is \(A\), whereas the right child of the root is a node labelled \(y\) whose left and right children are \(B\) and \(C\). 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()
).
- semistandard_insert(letter)[source]#
Return the result of inserting a letter
letter
into the semistandard treeself
using the bumping algorithm.INPUT:
letter
– any object comparable with the labels ofself
OUTPUT:
The semistandard tree
self
withletter
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 \(n\) with label \(x\), every descendant of the left child of \(n\) has a label \(> x\), and every descendant of the right child of \(n\) has a label \(\geq x\). (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 \(t\) and a letter \(i\), the result of inserting \(i\) into \(t\) (denoted \(Ins(i, t)\) in the following) is defined recursively as follows:
If \(t\) is empty, then \(Ins(i, t)\) is the tree with one node only, and this node is labelled with \(i\).
Otherwise, let \(j\) be the label of the root of \(t\). If \(i \geq j\), then \(Ins(i, t)\) is obtained by replacing the right child of \(t\) by \(Ins(i, r)\) in \(t\), where \(r\) denotes the right child of \(t\). If \(i < j\), then \(Ins(i, t)\) is obtained by replacing the label at the root of \(t\) by \(i\), and replacing the left child of \(t\) by \(Ins(j, l)\) in \(t\), where \(l\) denotes the left child of \(t\).
This algorithm is similar to the Robinson-Schensted-Knuth insertion algorithm for semistandard Young tableaux.
AUTHORS:
Darij Grinberg (10 Nov 2013).
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[., .], .], .]]]
>>> from sage.all import * >>> LBT = LabelledBinaryTree >>> x = LBT(None) >>> x . >>> x = x.semistandard_insert("b"); x b[., .] >>> x = x.semistandard_insert("d"); x b[., d[., .]] >>> x = x.semistandard_insert("e"); x b[., d[., e[., .]]] >>> x = x.semistandard_insert("a"); x a[b[., .], d[., e[., .]]] >>> x = x.semistandard_insert("b"); x a[b[., .], b[d[., .], e[., .]]] >>> x = x.semistandard_insert("d"); x a[b[., .], b[d[., .], d[e[., .], .]]] >>> x = x.semistandard_insert("a"); x a[b[., .], a[b[d[., .], .], d[e[., .], .]]] >>> 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[., .]]]]
>>> from sage.all import * >>> LBT = LabelledBinaryTree >>> LBT(None).semistandard_insert(Integer(3)) 3[., .] >>> LBT([], label = Integer(1)).semistandard_insert(Integer(3)) 1[., 3[., .]] >>> LBT([], label = Integer(3)).semistandard_insert(Integer(1)) 1[3[., .], .] >>> res = LBT(None) >>> for i in [Integer(3),Integer(1),Integer(5),Integer(2),Integer(4),Integer(6)]: ... res = res.semistandard_insert(i) >>> res 1[3[., .], 2[5[., .], 4[., 6[., .]]]]
- class sage.combinat.binary_tree.LabelledBinaryTrees(category=None)[source]#
Bases:
LabelledOrderedTrees
This is a parent stub to serve as a factory class for trees with various labels constraints.
- Element[source]#
alias of
LabelledBinaryTree
- labelled_trees()[source]#
Return the set of labelled trees associated to
self
.EXAMPLES:
sage: LabelledBinaryTrees().labelled_trees() Labelled binary trees
>>> from sage.all import * >>> LabelledBinaryTrees().labelled_trees() Labelled binary trees
- unlabelled_trees()[source]#
Return the set of unlabelled trees associated to
self
.EXAMPLES:
sage: LabelledBinaryTrees().unlabelled_trees() Binary trees
>>> from sage.all import * >>> LabelledBinaryTrees().unlabelled_trees() Binary trees
This is used to compute the shape:
sage: t = LabelledBinaryTrees().an_element().shape(); t [[[., .], [., .]], [[., .], [., .]]] sage: t.parent() Binary trees
>>> from sage.all import * >>> t = LabelledBinaryTrees().an_element().shape(); t [[[., .], [., .]], [[., .], [., .]]] >>> t.parent() Binary trees
- sage.combinat.binary_tree.binary_search_tree_shape(w, left_to_right=True)[source]#
Direct computation of the binary search tree shape of a list of integers.
INPUT:
w
– a list of integersleft_to_right
– boolean (defaultTrue
)
OUTPUT: a non labelled binary tree
This is used under the same name as a method for permutations.
EXAMPLES:
sage: from sage.combinat.binary_tree import binary_search_tree_shape sage: binary_search_tree_shape([1,4,3,2]) [., [[[., .], .], .]] sage: binary_search_tree_shape([5,1,3,2]) [[., [[., .], .]], .]
>>> from sage.all import * >>> from sage.combinat.binary_tree import binary_search_tree_shape >>> binary_search_tree_shape([Integer(1),Integer(4),Integer(3),Integer(2)]) [., [[[., .], .], .]] >>> binary_search_tree_shape([Integer(5),Integer(1),Integer(3),Integer(2)]) [[., [[., .], .]], .]
By passing the option
left_to_right=False
one can have the insertion going from right to left:sage: binary_search_tree_shape([1,6,4,2], False) [[., .], [., [., .]]]
>>> from sage.all import * >>> binary_search_tree_shape([Integer(1),Integer(6),Integer(4),Integer(2)], False) [[., .], [., [., .]]]
- sage.combinat.binary_tree.from_tamari_sorting_tuple(key)[source]#
Return a binary tree from its Tamari-sorting tuple.
INPUT:
key
– a tuple of integers
EXAMPLES:
sage: from sage.combinat.binary_tree import from_tamari_sorting_tuple sage: t = BinaryTrees(60).random_element() # needs sage.combinat sage: from_tamari_sorting_tuple(t.tamari_sorting_tuple()[0]) == t # needs sage.combinat True
>>> from sage.all import * >>> from sage.combinat.binary_tree import from_tamari_sorting_tuple >>> t = BinaryTrees(Integer(60)).random_element() # needs sage.combinat >>> from_tamari_sorting_tuple(t.tamari_sorting_tuple()[Integer(0)]) == t # needs sage.combinat True