This module deals with binary trees as mathematical (in particular immmutable) 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:
Bases: sage.combinat.abstract_tree.AbstractClonableTree, sage.structure.list_clone.ClonableArray
The class of binary trees
Binary trees here mean ordered (a.k.a. plane) binary trees, meaning that the children of each node are ordered.
INPUT:
EXAMPLES:
sage: BinaryTree()
.
sage: BinaryTree(None)
.
sage: BinaryTree([])
[., .]
sage: BinaryTree([None, None])
[., .]
sage: BinaryTree([None, []])
[., [., .]]
sage: BinaryTree([[], None])
[[., .], .]
sage: BinaryTree("[[], .]")
[[., .], .]
sage: BinaryTree([[], None, []])
Traceback (most recent call last):
...
ValueError: this is not a binary tree
TESTS:
sage: t1 = BinaryTree([[None, [[],[[], None]]],[[],[]]])
sage: t2 = BinaryTree([[[],[]],[]])
sage: with t1.clone() as t1c:
... t1c[1,1,1] = t2
sage: t1 == t1c
False
Return the same tree seen as an ordered tree. By default, leaves are transformed into actual nodes.
EXAMPLES:
sage: bt = BinaryTree([]); bt
[., .]
sage: bt.as_ordered_tree()
[[], []]
sage: bt.as_ordered_tree(with_leaves = False)
[]
sage: bt = bt.canonical_labelling(); bt
1[., .]
sage: bt.as_ordered_tree()
1[None[], None[]]
sage: bt.as_ordered_tree(with_leaves=False)
1[]
Return a labelled version of self.
The 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[., .]]]
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]
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 [DG], see also OEIS sequence A001181). We check this in small cases:
sage: [len([(u,v) for u in BinaryTrees(n) for v in BinaryTrees(n)
... if map(lambda x:1-x, u.canopee()) == v.canopee()])
... for n in range(1, 5)]
[1, 2, 6, 22]
Here is a less trivial implementation of this:
sage: from sage.sets.finite_set_map_cy import fibers
sage: from sage.misc.all import attrcall
sage: def baxter(n):
... f = fibers(lambda t: tuple(t.canopee()),
... BinaryTrees(n))
... return sum(len(f[i])*len(f[tuple(1-x for x in i)])
... for i in f)
sage: [baxter(n) for n in range(1, 7)]
[1, 2, 6, 22, 92, 422]
TESTS:
sage: t = BinaryTree().canopee()
Traceback (most recent call last):
...
ValueError: canopee is only defined for non empty binary trees
REFERENCES:
[DG] S. Dulucq and O, Guibert. Mots de piles, tableaux standards et permutations de Baxter, proceedings of Formal Power Series and Algebraic Combinatorics, 1994.
Checks that self is a binary tree
EXAMPLES:
sage: BinaryTree([[], []]) # indirect doctest
[[., .], [., .]]
sage: BinaryTree([[], [], []]) # indirect doctest
Traceback (most recent call last):
...
ValueError: this is not a binary tree
sage: BinaryTree([[]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: this is not a binary tree
Convert self to a digraph
EXAMPLE:
sage: t1 = BinaryTree([[], None])
sage: t1.graph()
Digraph on 5 vertices
sage: t1 = BinaryTree([[], [[], None]])
sage: t1.graph()
Digraph on 9 vertices
sage: t1.graph().edges()
[(0, 1, None), (0, 4, None), (1, 2, None), (1, 3, None), (4, 5, None), (4, 8, None), (5, 6, None), (5, 7, None)]
Return whether self is empty.
EXAMPLES:
sage: BinaryTree().is_empty()
True
sage: BinaryTree([]).is_empty()
False
sage: BinaryTree([[], None]).is_empty()
False
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[., .]]]
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()
[., [[., .], .]]
Modify self so that it became a leaf
Note
self must be in a mutable state.
See also
EXAMPLES:
sage: t = BinaryTree([None, None])
sage: t.make_leaf()
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with t.clone() as t1:
... t1.make_leaf()
sage: t, t1
([., .], .)
Modify self so that it becomes a node with children childlist
INPUT:
Note
self must be in a mutable state.
See also
EXAMPLES:
sage: t = BinaryTree()
sage: t.make_node([None, None])
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with t.clone() as t1:
... t1.make_node([None, None])
sage: t, t1
(., [., .])
sage: with t.clone() as t:
... t.make_node([BinaryTree(), BinaryTree(), BinaryTree([])])
Traceback (most recent call last):
...
ValueError: the list must have length 2
sage: with t1.clone() as t2:
... t2.make_node([t1, t1])
sage: with t2.clone() as t3:
... t3.make_node([t1, t2])
sage: t1, t2, t3
([., .], [[., .], [., .]], [[., .], [[., .], [., .]]])
TESTS:
sage: t1 = BinaryTree([[], [[], None]])
sage: t1.show()
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 sylester class of the tree. This permutation is the maximal element of this sylvester class.
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_132_avoiding_permutation()
[3, 1, 2]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_132_avoiding_permutation()
[8, 6, 7, 3, 4, 1, 2, 5]
TESTS:
sage: bt = BinaryTree([[],[]])
sage: bt == bt.to_132_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_132_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
Return a 312-avoiding permutation corresponding to the binary tree.
The linear extensions of a binary tree form an interval of the weak order called the sylester class of the tree. This permutation is the minimal element of this sylvester class.
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_312_avoiding_permutation()
[1, 3, 2]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_312_avoiding_permutation()
[1, 3, 4, 2, 6, 8, 7, 5]
TESTS:
sage: bt = BinaryTree([[],[]])
sage: bt == bt.to_312_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_312_avoiding_permutation().binary_search_tree_shape(left_to_right=False)
True
INPUT:
Return the Dyck word associated with self using the given map.
The bijection is defined recursively as follows:
EXAMPLES:
sage: BinaryTree().to_dyck_word()
[]
sage: BinaryTree([]).to_dyck_word()
[1, 0]
sage: BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word()
[1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word()
[1, 1, 0, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("1R0L")
[1, 0, 1, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("L1R0")
[1, 1, 0, 0, 1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("R1L0")
[1, 1, 0, 1, 0, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word("R10L")
Traceback (most recent call last):
...
ValueError: R10L is not a correct map
TESTS:
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt == bt.to_dyck_word().to_binary_tree()
True
sage: bt == bt.to_dyck_word("1R0L").to_binary_tree("1R0L")
True
sage: bt == bt.to_dyck_word("L1R0").to_binary_tree("L1R0")
True
sage: bt == bt.to_dyck_word("R1L0").to_binary_tree("R1L0")
True
Return the Dyck word associated with self in consistency with the Tamari order on dyck words and binary trees.
The bijection is defined recursively as follows:
EXAMPLES:
sage: BinaryTree().to_dyck_word_tamari()
[]
sage: BinaryTree([]).to_dyck_word_tamari()
[1, 0]
sage: BinaryTree([[None,[]],None]).to_dyck_word_tamari()
[1, 1, 0, 0, 1, 0]
sage: BinaryTree([[[], [[], None]], [[], []]]).to_dyck_word_tamari()
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
Return an ordered tree of size \(n+1\) by the following recursive rule:
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_ordered_tree_left_branch()
[[], [[]]]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_ordered_tree_left_branch()
[[], [[], []], [[], [[]]]]
Return an ordered tree of size n+1 by the following recursive rule:
EXAMPLES:
sage: bt = BinaryTree([[],[]])
sage: bt.to_ordered_tree_right_branch()
[[[]], []]
sage: bt = BinaryTree([[[], [[], None]], [[], []]])
sage: bt.to_ordered_tree_right_branch()
[[[[]], [[]]], [[]], []]
Return the poset obtained by interpreting the tree as a hasse diagram.
The default orientation is from leaves to root but you can pass root_to_leaf=True to obtain the inverse orientation.
Leafs are ignored by default but can set with_leaves to True to obtain the poset of the complete tree.
INPUT:
EXAMPLES:
sage: bt = BinaryTree([])
sage: bt.to_poset()
Finite poset containing 1 elements
sage: bt.to_poset(with_leaves=True)
Finite poset containing 3 elements
sage: bt.to_poset(with_leaves=True).cover_relations()
[[0, 2], [1, 2]]
sage: bt = BinaryTree([])
sage: bt.to_poset(with_leaves=True,root_to_leaf=True).cover_relations()
[[0, 1], [0, 2]]
If the tree is labelled, we use its labelling to label the poset. Otherwise, we use the poset canonical labelling:
sage: bt = BinaryTree([[],[None,[]]]).canonical_labelling()
sage: bt
2[1[., .], 3[., 4[., .]]]
sage: bt.to_poset().cover_relations()
[[4, 3], [3, 2], [1, 2]]
Return the undirected graph obtained from the tree nodes and edges. Leafs are ignored by default but can set with_leaves to True to obtain the graph of the complete tree.
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
If the tree is labelled, we use its labelling to label the graph. Otherwise, we use the graph canonical labelling which means that two different trees can have the same graph.
EXAMPLES:
sage: bt = BinaryTree([[],[None,[]]])
sage: bt.canonical_labelling()
2[1[., .], 3[., 4[., .]]]
sage: bt.canonical_labelling().to_undirected_graph().edges()
[(1, 2, None), (2, 3, None), (3, 4, None)]
sage: bt.to_undirected_graph().edges()
[(0, 3, None), (1, 2, None), (2, 3, None)]
sage: bt.canonical_labelling().to_undirected_graph() == bt.to_undirected_graph()
False
sage: BinaryTree([[],[]]).to_undirected_graph() == BinaryTree([[[],None],None]).to_undirected_graph()
True
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Factory for binary trees.
INPUT:
OUPUT:
EXAMPLES:
sage: BinaryTrees()
Binary trees
sage: BinaryTrees(2)
Binary trees of size 2
Note
this in a factory class whose constructor returns instances of subclasses.
Note
the fact that OrderedTrees is a class instead of a simple callable is an implementation detail. It could be changed in the future and one should not rely on it.
Return a left tree with self as parent.
EXAMPLES:
sage: BinaryTrees().leaf()
.
TEST:
sage: (BinaryTrees().leaf() is
... sage.combinat.binary_tree.BinaryTrees_all().leaf())
True
Bases: sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets, sage.combinat.binary_tree.BinaryTrees
TESTS:
sage: from sage.combinat.binary_tree import BinaryTrees_all
sage: B = BinaryTrees_all()
sage: B.cardinality()
+Infinity
sage: it = iter(B)
sage: (it.next(), it.next(), it.next(), it.next(), it.next())
(., [., .], [., [., .]], [[., .], .], [., [., [., .]]])
sage: it.next().parent()
Binary trees
sage: B([])
[., .]
sage: B is BinaryTrees_all()
True
sage: TestSuite(B).run()
alias of BinaryTree
Return the set of labelled trees associated to self
EXAMPLES:
sage: BinaryTrees().labelled_trees()
Labelled binary trees
Return the set of unlabelled trees associated to self
EXAMPLES:
sage: BinaryTrees().unlabelled_trees()
Binary trees
Bases: sage.combinat.binary_tree.BinaryTrees
The enumerated sets of binary trees of given size
TESTS:
sage: from sage.combinat.binary_tree import BinaryTrees_size
sage: for i in range(6): TestSuite(BinaryTrees_size(i)).run()
The cardinality of self
This is a Catalan number.
TESTS:
sage: BinaryTrees(0).cardinality()
1
sage: BinaryTrees(5).cardinality()
42
TESTS:
sage: S = BinaryTrees(3)
sage: S.element_class
<class 'sage.combinat.binary_tree.BinaryTrees_all_with_category.element_class'>
sage: S.first().__class__ == BinaryTrees().first().__class__
True
Bases: sage.combinat.abstract_tree.AbstractLabelledClonableTree, sage.combinat.binary_tree.BinaryTree
The class of labelled binary tree
EXAMPLE:
sage: LBT = LabelledBinaryTree
sage: t1 = LBT([[LBT([], label=2), None], None], label=4); t1
4[None[2[., .], .], .]
Insert a letter in a binary search tree
INPUT:
Note
self is supposed to be a binary search tree. No check is performed.
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[., .]]]
Bases: sage.combinat.ordered_tree.LabelledOrderedTrees
This is a parent stub to serve as a factory class for trees with various labels constraints
alias of LabelledBinaryTree
Return the set of labelled trees associated to self
EXAMPLES:
sage: LabelledBinaryTrees().labelled_trees()
Labelled binary trees
Return the set of unlabelled trees associated to self
EXAMPLES:
sage: LabelledBinaryTrees().unlabelled_trees()
Binary trees
This is used to compute the shape:
sage: t = LabelledBinaryTrees().an_element().shape(); t
[[[., .], [., .]], [[., .], [., .]]]
sage: t.parent()
Binary trees
TESTS:
sage: t = LabelledBinaryTrees().an_element()
sage: t.canonical_labelling()
4[2[1[., .], 3[., .]], 6[5[., .], 7[., .]]]