Ordered Rooted Trees

AUTHORS:

  • Florent Hivert (2010-2011): initial revision
  • Frederic Chapoton (2010): contributed some methods
class sage.combinat.ordered_tree.LabelledOrderedTree(parent, children, label=None, check=True)

Bases: sage.combinat.abstract_tree.AbstractLabelledClonableTree, sage.combinat.ordered_tree.OrderedTree

Labelled ordered trees

A labelled ordered tree is an ordered tree with a label attached at each node.

INPUT:

  • children – a list or tuple or more generally any iterable

    of trees or object convertible to trees

  • label – any Sage object default to None

EXAMPLES:

sage: x = LabelledOrderedTree([], label = 3); x
3[]
sage: LabelledOrderedTree([x, x, x], label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree((x, x, x), label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree([[],[[], []]], label = 3)
3[None[], None[None[], None[]]]
class sage.combinat.ordered_tree.LabelledOrderedTrees(category=None)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

This is a parent stub to serve as a factory class for trees with various labels constraints

EXAMPLES:

sage: LOT = LabelledOrderedTrees(); LOT
Labelled ordered trees
sage: x = LOT([], label = 3); x
3[]
sage: x.parent() is LOT
True
sage: y = LOT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.parent() is LOT
True
Element

alias of LabelledOrderedTree

cardinality()

Return the cardinality of \(self\)

EXAMPLE:

sage: LabelledOrderedTrees().cardinality()
+Infinity
labelled_trees()

Return the set of labelled trees associated to self

EXAMPLES:

sage: LabelledOrderedTrees().labelled_trees()
Labelled ordered trees
sage: LOT = LabelledOrderedTrees()
sage: x = LOT([], label = 3)
sage: y = LOT([x, x, x], label = 2)
sage: y.canonical_labelling()
1[2[], 3[], 4[]]
unlabelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: LabelledOrderedTrees().unlabelled_trees()
Ordered trees
class sage.combinat.ordered_tree.OrderedTree(parent=None, children=[], check=True)

Bases: sage.combinat.abstract_tree.AbstractClonableTree, sage.structure.list_clone.ClonableList

The class for (ordered rooted) Trees

An ordered tree is constructed from a node called the root on which one has grafted a possibly empty list of trees. There is a total order on the children of a node which is given by the order of the elements in the list. Note that there is no empty ordered tree.

INPUT:

One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree. Alternatively a string is also accepted. The syntax is the same as for printing: children are grouped by square brackets.

EXAMPLES:

sage: x = OrderedTree([])
sage: x1 = OrderedTree([x,x])
sage: x2 = OrderedTree([[],[]])
sage: x1 == x2
True
sage: tt1 = OrderedTree([x,x1,x2])
sage: tt2 = OrderedTree([[], [[], []], x2])
sage: tt1 == tt2
True

sage: OrderedTree([]) == OrderedTree()
True

TESTS:

sage: x1.__hash__() == x2.__hash__()
True
sage: tt1.__hash__() == tt2.__hash__()
True

Trees are usually immutable. However they inherits from sage.structure.list_clone.ClonableList. So that they can be modified using the clone protocol:

Trying to modify a non mutable tree raises an error:

sage: tt1[1] = tt2
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.

Here is the correct way to do it:

sage: with tt2.clone() as tt2:
...    tt2[1] = tt1
sage: tt2
[[], [[], [[], []], [[], []]], [[], []]]

It is also possible to append a child to a tree:

sage: with tt2.clone() as tt3:
...    tt3.append(OrderedTree([]))
sage: tt3
[[], [[], [[], []], [[], []]], [[], []], []]

Or to insert a child in a tree:

sage: with tt2.clone() as tt3:
...    tt3.insert(2, OrderedTree([]))
sage: tt3
[[], [[], [[], []], [[], []]], [], [[], []]]

We check that tt1 is not modified and that everything is correct with respect to equality:

sage: tt1
[[], [[], []], [[], []]]
sage: tt1 == tt2
False
sage: tt1.__hash__() == tt2.__hash__()
False

TESTS:

sage: tt1bis = OrderedTree(tt1)
sage: with tt1.clone() as tt1:
...    tt1[1] = tt1bis
sage: tt1
[[], [[], [[], []], [[], []]], [[], []]]
sage: tt1 == tt2
True
sage: tt1.__hash__() == tt2.__hash__()
True
sage: len(tt1)
3
sage: tt1[2]
[[], []]
sage: tt1[3]
Traceback (most recent call last):
...
IndexError: list index out of range
sage: tt1[1:2]
[[[], [[], []], [[], []]]]

Various tests involving construction, equality and hashing:

sage: OrderedTree() == OrderedTree()
True
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[],[[]]])
sage: t1 == t2
True
sage: t2 = OrderedTree(t1)
sage: t1 == t2
True
sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[[]],[]])
sage: t1 == t2
False

sage: t1 = OrderedTree([[],[[]]])
sage: t2 = OrderedTree([[],[[]]])
sage: t1.__hash__() == t2.__hash__()
True
sage: t2 = OrderedTree([[[]],[]])
sage: t1.__hash__() == t2.__hash__()
False
sage: OrderedTree().__hash__() == OrderedTree([]).__hash__()
True
sage: tt1 = OrderedTree([t1,t2,t1])
sage: tt2 = OrderedTree([t1, [[[]],[]], t1])
sage: tt1.__hash__() == tt2.__hash__()
True

Check that the hash value is correctly updated after modification:

sage: with tt2.clone() as tt2:
...    tt2[1,1] = tt1
sage: tt1.__hash__() == tt2.__hash__()
False
is_empty()

Return if self is the empty tree

For ordered trees, returns always False

Note

this is different from bool(t) which returns whether t has some child or not.

EXAMPLES:

sage: t = OrderedTrees(4)([[],[[]]])
sage: t.is_empty()
False
sage: bool(t)
True
left_right_symmetry(*args, **kwds)

Return the symmetric tree of self

EXAMPLES:

sage: T = OrderedTree([[],[[]]])
sage: T.left_right_symmetry()
[[[]], []]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.left_right_symmetry()
[[[[]], []], [[], []], []]
to_binary_tree_left_branch(*args, **kwds)

Return a binary tree of size \(n-1\) by the following recursive rule:

  • if \(x\) is the left brother of \(y\), \(x\) becomes the left child of \(y\)
  • if \(x\) is the last child of \(y\), \(x\) becomes the right child of \(y\)

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_left_branch()
[[., .], .]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_left_branch()
[[[., .], [[., .], .]], [[., .], [., .]]]

TESTS:

sage: T = OrderedTree([[],[]])
sage: T == T.to_binary_tree_left_branch().to_ordered_tree_left_branch()
True
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T == T.to_binary_tree_left_branch().to_ordered_tree_left_branch()
True
to_binary_tree_right_branch(*args, **kwds)

Return a binary tree of size n-1 by the following recursive rule:

  • if \(x\) is the right brother of \(y\), \(x\) becomes the right child of \(y\)
  • if \(x\) is the first child of \(y\), \(x\) becomes the left child of \(y\)

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_right_branch()
[., [., .]]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_right_branch()
[., [[., [., .]], [[., [[., .], .]], .]]]

TESTS:

sage: T = OrderedTree([[],[]])
sage: T == T.to_binary_tree_right_branch().to_ordered_tree_right_branch()
True
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T == T.to_binary_tree_right_branch().to_ordered_tree_right_branch()
True
to_dyck_word(*args, **kwds)

Return the dyck path corresponding to self where the maximal height of the Dyck path is the depth of self .

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_dyck_word()
[1, 0, 1, 0]
sage: T = OrderedTree([[],[[]]])
sage: T.to_dyck_word()
[1, 0, 1, 1, 0, 0]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_dyck_word()
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
to_poset(*args, **kwds)

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.

INPUT:

  • root_to_leaf – boolean, true if the poset orientation should be from root to leaves. It is false by default.

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_poset()
Finite poset containing 1 elements
sage: p = OrderedTree([[[]],[],[]]).to_poset()
sage: p.cover_relations()
[[0, 4], [1, 4], [2, 3], [3, 4]]
sage: p = OrderedTree([[[]],[],[]]).to_poset(root_to_leaf=True)
sage: p.cover_relations()
[[0, 2], [0, 3], [0, 4], [4, 1]]

If the tree is labelled, we use its labelling to label the poset. Otherwise, we use the poset canonical labelling:

sage: t = OrderedTree([[[]],[],[]]).canonical_labelling()
sage: t
1[2[3[]], 4[], 5[]]
sage: t.to_poset().cover_relations()
[[5, 1], [4, 1], [3, 2], [2, 1]]
to_undirected_graph(*args, **kwds)

Return the undirected graph obtained from the tree nodes and edges.

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_undirected_graph()
Graph on 1 vertex
sage: t = OrderedTree([[[]],[],[]])
sage: t.to_undirected_graph()
Graph on 5 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: t = OrderedTree([[[]],[],[]])
sage: t.canonical_labelling().to_undirected_graph()
Graph on 5 vertices
sage: t.canonical_labelling().to_undirected_graph() == t.to_undirected_graph()
False
sage: OrderedTree([[],[]]).to_undirected_graph() == OrderedTree([[[]]]).to_undirected_graph()
True
sage: OrderedTree([[],[],[]]).to_undirected_graph() == OrderedTree([[[[]]]]).to_undirected_graph()
False
class sage.combinat.ordered_tree.OrderedTrees

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

Factory for ordered trees

INPUT:

  • size – (optional) an integer

OUPUT:

  • the set of all ordered trees (of the given size if specified)

EXAMPLES:

sage: OrderedTrees()
Ordered trees

sage: OrderedTrees(2)
Ordered trees of size 2

Note

this is 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.

leaf()

Return a leaf tree with self as parent

EXAMPLES:

sage: OrderedTrees().leaf()
[]

TEST:

sage: (OrderedTrees().leaf() is
...    sage.combinat.ordered_tree.OrderedTrees_all().leaf())
True
class sage.combinat.ordered_tree.OrderedTrees_all

Bases: sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets, sage.combinat.ordered_tree.OrderedTrees

The set of all ordered trees

EXAMPLES:

sage: OT = OrderedTrees(); OT
Ordered trees
sage: OT.cardinality()
+Infinity
Element

alias of OrderedTree

labelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: OrderedTrees().labelled_trees()
Labelled ordered trees
unlabelled_trees()

Return the set of unlabelled trees associated to self

EXAMPLES:

sage: OrderedTrees().unlabelled_trees()
Ordered trees
class sage.combinat.ordered_tree.OrderedTrees_size(size)

Bases: sage.combinat.ordered_tree.OrderedTrees

The enumerated sets of binary trees of a given size

EXAMPLES:

sage: S = OrderedTrees(3); S
Ordered trees of size 3
sage: S.cardinality()
2
sage: S.list()
[[[], []], [[[]]]]
cardinality()

The cardinality of self

This is a Catalan number

TESTS:

sage: OrderedTrees(0).cardinality()
0
sage: OrderedTrees(1).cardinality()
1
sage: OrderedTrees(6).cardinality()
42
element_class()

The class of the element of self

EXAMPLES:

sage: from sage.combinat.ordered_tree import OrderedTrees_size, OrderedTrees_all
sage: S = OrderedTrees_size(3)
sage: S.element_class is OrderedTrees().element_class
True
sage: S.first().__class__ == OrderedTrees_all().first().__class__
True

Previous topic

Abstract Recursive Trees

Next topic

Binary trees

This Page