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.
sage.combinat.binary_tree.BinaryTree

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:

  • childrenNone (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 the BinaryTree() constructor, so that, e. g., BinaryTree([BinaryTree(None),BinaryTree(None)]) can be shortened to BinaryTree([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
sage.combinat.binary_tree.BinaryTrees

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 integer
  • full – (optional) a boolean

OUTPUT:

The set of all (full if full=True) binary trees (of the given size if specified).

See also

BinaryTree, BinaryTree.is_full()

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

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

Bases: sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets, sage.combinat.binary_tree.BinaryTrees

Element

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:

  • childrenNone (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 the BinaryTree() constructor, so that, e. g., BinaryTree([BinaryTree(None),BinaryTree(None)]) can be shortened to BinaryTree([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
labelled_trees()

Return the set of labelled trees associated to self.

EXAMPLES:

sage: BinaryTrees().labelled_trees()
Labelled binary trees
unlabelled_trees()

Return the set of unlabelled trees associated to self.

EXAMPLES:

sage: BinaryTrees().unlabelled_trees()
Binary trees
sage.combinat.binary_tree.BinaryTrees_size

The enumerated sets of binary trees of given size.

sage.combinat.binary_tree.FullBinaryTrees_all

All full binary trees.

sage.combinat.binary_tree.FullBinaryTrees_size

Full binary trees of a fixed size (number of nodes).

sage.combinat.binary_tree.LabelledBinaryTree

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:

  • childrenNone (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 to LabelledBinaryTree([None,None]). However, using this shorthand, it is impossible to label any vertex of the tree other than the root (because there is no way to pass a label variable without calling LabelledBinaryTree explicitly).

    It is also allowed to abbreviate [None, None] by [] if one does not want to label the leaves (which one should not do anyway!).

  • label – (default: None) the label to be put on the root of this tree.

  • check – (default: True) whether checks should be performed or not.

Todo

It is currently not possible to use LabelledBinaryTree() as a shorthand for LabelledBinaryTree(None) (in analogy to similar syntax in the BinaryTree class).

EXAMPLES:

sage: LabelledBinaryTree(None)
.
sage: LabelledBinaryTree(None, label="ae")    # not well supported
'ae'
sage: LabelledBinaryTree([])
None[., .]
sage: LabelledBinaryTree([], label=3)    # not well supported
3[., .]
sage: LabelledBinaryTree([None, None])
None[., .]
sage: LabelledBinaryTree([None, None], label=5)
5[., .]
sage: LabelledBinaryTree([None, []])
None[., None[., .]]
sage: LabelledBinaryTree([None, []], label=4)
4[., None[., .]]
sage: LabelledBinaryTree([[], None])
None[None[., .], .]
sage: LabelledBinaryTree("[[], .]", label=False)
False[None[., .], .]
sage: LabelledBinaryTree([None, LabelledBinaryTree([None, None], label=4)], label=3)
3[., 4[., .]]
sage: LabelledBinaryTree([None, BinaryTree([None, None])], label=3)
3[., None[., .]]

sage: LabelledBinaryTree([[], None, []])
Traceback (most recent call last):
...
ValueError: this is not a binary tree

sage: LBT = LabelledBinaryTree
sage: t1 = LBT([[LBT([], label=2), None], None], label=4); t1
4[None[2[., .], .], .]
sage.combinat.binary_tree.LabelledBinaryTrees

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

sage.combinat.binary_tree.binary_search_tree_shape(w, left_to_right=True)

Direct computation of the binary search tree shape of a list of integers.

INPUT:

  • w – a list of integers
  • left_to_right – boolean (default True)

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])
[[., [[., .], .]], .]

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)
[[., .], [., [., .]]]
sage.combinat.binary_tree.from_tamari_sorting_tuple(key)

Return a binary tree from its Tamari-sorting tuple.

See tamari_sorting_tuple()

INPUT:

  • key – a tuple of integers

EXEMPLES:

sage: from sage.combinat.binary_tree import from_tamari_sorting_tuple
sage: t = BinaryTrees(60).random_element()
sage: from_tamari_sorting_tuple(t.tamari_sorting_tuple()[0]) == t
True