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:
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
-
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 integerfull
– (optional) a boolean
OUTPUT:
The set of all (full if
full=True
) binary trees (of the givensize
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:
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
-
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:
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[., .], .], .]
-
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 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]) [[., [[., .], .]], .]
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