2015_Pycon.sagews

bt = BinaryTree([[None,[]],[[],[[[],[]],[None,[]]]]])
latex.eval(latex(bt))

''

bt.node_number()
bt.depth()
bt.is_complete()

11 5 False

BT = BinaryTrees()
BT

Binary trees

BT.cardinality()

+Infinity

BT2 = BinaryTrees(2)
BT2

Binary trees of size 2

BT2.cardinality()

2

latex.eval(latex(BT2[0]))

''

latex.eval(latex(BT2[1]))

''

BT3 = BinaryTrees(3)
BT3.cardinality()

5

for bt in BinaryTrees(3):
    latex.eval(latex(bt))

''

''

''

''

''

BinaryTrees(5).cardinality()

42

BinaryTrees(11).cardinality()

58786

len(list(BinaryTrees(11)))

58786

[BinaryTrees(i).cardinality() for i in xrange(10)]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

[1/(n+1) * binomial(2*n, n) for n in xrange(10)]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

BT3.cardinality??

   File: /usr/local/sage/sage-6.5/local/lib/python2.7/site-packages/sage/combinat/binary_tree.py
   Source:
       def cardinality(self):
        """
        The cardinality of ``self``

        This is a Catalan number.

        TESTS::

            sage: BinaryTrees(0).cardinality()
            1
            sage: BinaryTrees(5).cardinality()
            42
        """
        from combinat import catalan_number
        return catalan_number(self._size)

all([len([bt for bt in BinaryTrees(n) if bt.depth() == n]) == 2^(n-1) for n in xrange(2,8)])

True

def random_binary1(size):
    return BinaryTrees(size).random_element()
    
bt1 = random_binary1(11)
bt2 = random_binary1(11)
latex.eval(latex(bt1))
latex.eval(latex(bt2))

''

''

def random_binary2(size):
    p = Permutations(size).random_element()
    return p.binary_search_tree_shape()

bt1 = random_binary2(11)
bt2 = random_binary2(11)
latex.eval(latex(bt1))
latex.eval(latex(bt2))

''

''

mean([float(random_binary1(11).depth()) for i in xrange(1000)])

7.537

mean([float(random_binary2(11).depth()) for i in xrange(1000)])

5.92

mean([float(random_binary1(100).depth()) for i in xrange(10000)])

30.0557

mean([float(random_binary2(100).depth()) for i in xrange(10000)])

13.3071